Advances in Production Engineering & Management Volume 11 | Number 4 | December 2016 | pp 259-270 http://dx.doi.Org/10.14743/apem2016.4.225 ISSN 1854-6250 Journal home: apem-journal.org Original scientific paper A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem Xiao, Y.J.ab, Zheng, Y.c, Zhang, L.M.d*, Kuo, Y.H.e aJiangsu Key Laboratory of Modern Logistics, School of Marketing and Logistic Management, Nanjing University of Finance and Economics, Nanjing , China bBusiness school, Nanjing University, Nanjing, China cCollege of Automobile and Traffic Engineering, Nanjing Forestry University, Nanjing, China dSchool of Management and Engineering, Nanjing University, Nanjing, China eStanley Ho Big Data Decision Analytics Research Centre, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong A B S T R A C T A R T I C L E I N F O Facility layout problem (FLP) is one of well-known NP-hard problems and has been demonstrated to be useful in enhancing the productivity of manufacturing systems in practice. This paper focuses on the unequal-area FLP (UA-FLP) whose goal is to locate departments with different areas within a given facility so as to minimize the total material handling cost. A novel approach, which we call a combined zone-linear programming (zone-LP) and simulated annealing algorithm, is developed for solving the UA-FLP. The zone-LP approach is a layout construction technique for the unequal-area departments and consists of two phases. In the first phase, a zoning algorithm is implemented to determine the relative positions between the departments. In this algorithm, for the sake of problem simplification and computational efficiency, each department is treated as a rectangle with an allowable aspect ratio and the area of the facility is assumed to be unbounded. In the second phase, by using the relative positions obtained in the first phase as input, a linear programming (LP) model is developed to identify the exact locations and dimensions of departments within the facility with specified sizes while satisfying their maximum aspect ratio requirement and the shape constraints. We also design a simulated annealing algorithm to improve the placing sequence. Finally, our computational results suggest that our proposed algorithm is efficient compared with the best existing approach in the literature. © 2016 PEI, University of Maribor. All rights reserved. Keywords: Facility layout problem Unequal area Zone-LP approach Simulated annealing *Corresponding author: zhanglm@nju.edu.cn (Zhang, L.M.) Article history: Received 10 August 2016 Revised 9 October 2016 Accepted 15 October 2016 1. Introduction As the competition among the global marketplaces increases rapidly, the provision of high-quality products or services at low cost to customers becomes more and more crucial for companies to capture the mass market. Facilities planning "determines how an activity's tangible fixed assets best support achieving the activity objectives" [1] and thus plays an important role in the cost reduction and productivity gain in industrial firms. Facility planning consists of facilities location, facility system design, facility layout design and handling system design As a crucial part of facilities planning, facility layout design is to arrange departments interacting with each other within a facility so as to minimize the total material handling cost The layout design of a facility significantly impacts manufacturing cost and the productivity and efficiency of the system. According to [1], material handling cost ac- 259 Xiao, Zheng, Zhang, Kuo counts for 20 % to 50 % of the total manufacturing cost; an effective planning of facilities can reduce such cost by at least 10 % to 30 %. It is essential to design an efficient layout before manufacturing system design since future rearrangement of departments can result in a considerable expense. For these reasons, facility layout problem (FLP) has been studied extensively for over three decades [2-10]. There have been numerous studies adopting mathematical programming approaches to obtain optimal solutions for FLP. Montreuil [11] proposed the first mixed integer programming (MIP) model for solving the UA-FLP. However, their proposed MIP model can be solved for the problems with no more than six departments. Meller et al. [12] improved the formulation of the MIP model of Montreuil [11] by introducing a tightened department area constraint and several classes of valid inequalities. By their enhancement, the number of departments of the solvable problems increased to eight. Motivated by Meller et al. [12], Sherali et al. [13] further improved the accuracy for approximating the department areas by using a polyhedral outer approximation scheme. Moreover, Sherali et al. [13] investigated the effectiveness of the classes of valid inequalities proposed by Meller et al. [12] and reported that the MIP model was solved most efficiently by incorporating only two inequalities among them into the formulation. With this finding, the problems with up to nine departments could be optimally solved. Recently, Meller et al. [14] developed a new mathematical formulation for UA-FLP based on a sequence-pair representation. In this formulation, the feasible region of the problem was tightened such that the number of departments of the solvable problems has become eleven. Exact solution methods such as mathematical programming approaches are not applicable to obtain optimal solutions for large-scale problems since FLP is NP-hard [2]. Hence, heuristic approaches based on MIP models have been designed to construct layout solutions of high quality efficiently [15-17]. One of the well-known algorithms for solving FLP is based on the use of a slicing tree [18, 19], which is a binary tree used to form a subdivision of a rectangle by recursive computations. In the slicing tree, each inner node contains a guillotine cut operator (which cuts the area horizontally or vertically), and each leaf node represents a department. A layout can be generated according to a slicing tree by applying a set of guillotine cuts. Liu and Meller [20] developed a sequence-pair approach, where a pair of sequences is used to determine the relative locations between departments. By employing those relative locations, a reduced MIP model is utilized to construct the layout solutions. Both of above method are primarily proposed in the VLSI (very large Scale Integration) design. Similarly, Bozer and Wang [21] presented a graph-pair technique to fix the relative locations between departments and then a linear program (LP) is solved to obtain the layout solutions. This paper proposes a novel approach, which we call a combined zone-LP and simulated annealing (SA) algorithm, to solve the problem efficiently. The zone-LP approach is a layout construction technique for the UA-FLP and consists of two phases. In the first phase, the zone algorithm is implemented to determine the relative positions between departments. In this algorithm, for the sake of problem simplification and computational efficiency, each department is considered to be a rectangle with an allowable aspect ratio and the area of the facility is assumed to be unbounded. In the second phase, by using the relative positions obtained in the first phase as input, an LP is solved to determine the exact locations and dimensions of departments within the facility with specified sizes while satisfying their maximum aspect ratio requirement and the shape constraints. Furthermore, we also develop an SA algorithm to improve the solution quality. Finally, we conduct a computational study to examine the performance of our proposed algorithm and compare it with other existing solution approaches in the literature. Our paper is organized as follows. In the next section, we will describe the problem of UA-FLP. Section 3 will present our proposed solution methodology. In Section 4, we conduct computational experiments to study the performance of our proposed algorithm. Section 5 concludes our paper. 2. Problem description In UA-FLP, the areas of the departments are given and their dimensions are limited by a maximum aspect ratio (MAR), which is defined as the largest allowable ratio of the longest side to the 260 Advances in Production Engineering & Management 11(4) 2016 A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem shortest side of the department. The aspect ratio of a department ranges from 1/MAR to MAR. Furthermore, material flow quantities and the location of input/output (I/O) points are given. In the problem, the I/O points are assumed to be located at the centroids of departments. During the manufacturing process, materials are transferred between I/O points for each pair of departments. The objective is to minimize the total travel distance (TTD), which is the sum product of the distances between departments and their material flow quantities. For simplicity, the distance between departments is defined as the rectilinear distance between the input point and the output point. Table 1 provides an example of a setting of six departments with their required areas (am) and maximum aspect ratio (MARm) and the material flow quantities between each pair of the departments. Table 1 An example of a setting of six departments with their required areas (am) and maximum aspect ratio (MARm) and the material flow quantities between each pair of the departments m Material flow quantities 6 am MAR, 1 16 4 4 16 4 6 25 4 4 36 4 3 36 4 — 9 4 1 — 4 2 5 7 2 — — 4 3 3 3 — — — 2 2 4 7 6 — — — — — 3. Solution methodology It is well-known that UA-FLP is NP-hard. For this reason, we develop a heuristic algorithm to solve UA-FLP of large size. One complicating factor of UA-FLP is to determine the relative positions between the departments subject to the condition that their areas do not overlap. To circumvent this difficulty, we propose a solution methodology that integrates the zone-LP approach and an SA algorithm to obtain good-quality solutions. The zone-LP approach is a newly proposed layout construction technique based on an improved zone algorithm and the solution for an LP. When an initial solution is obtained from the previous stage, SA is employed to search within the solution space and acts to avoid the search procedure being trapped at a local optimum. 3.1 Zone-LP approach The zone-LP approach consists of two phases. In the first phase, for the simplification of the problem and more efficient computations, we consider the shape of each department as a rectangle with an allowable aspect ratio. As an example, as shown in Fig. 1, the six departments in Table 1 are treated as squares. Given the allowable aspect ratios of the departments, we develop an improved zone algorithm to determine their relative positions. The zone concept for UA-FLP is first introduced by Xiao et al. [22] to reduce its computational complexity and has been shown to be computationally efficient In the second phase, by using the relative positions obtained in the first phase as input, we solve an LP to obtain the exact locations of the departments within the facility, and their dimensions subject to their shape constraints are satisfied. 12 3 Fig. 1 Six departments to be located within the facility where each of them is of a fixed aspect ratio Advances in Production Engineering & Management 11(4) 2016 261 Xiao, Zheng, Zhang, Kuo 3.2 Improved zone algorithm The improved zone algorithm locates departments one by one according to a sequence such that a unique layout is generated. Given an initial sequence for locating the departments within the facility, say [1-4-2-5-3-6], we begin the algorithm by placing the first department in the sequence (i.e. Department 1) at the center of the facility. Then, four zones that are respectively on the left, above, on the right, and below this department can be identified. As an example, the four zones are shaded in the graphs of Fig. 2. The next step is to determine the zone that the following department in the sequence (i.e. Department 4) to be located. We first determine the optimal locations of this department within the four zones by using a median point (MP) method. The department will then be located at the best zone that results in the minimum total distance. Once the department is located within the facility, the set of zones will be updated for the determination of the location of the next department in the sequence. That procedure is repeated until all departments are located. For more detail about zone updating procedure, we refer the reader to Xiao etal. [22]. (a) (b) Fig 2 The four zones (shaded in grey) for the possible location of the department in our example To generalize the expressions of the zones, for i = 1, ...,N, let Ft be the i-th department in the sequence and let Z(i) = {z1l,.,zjl,.,zj1} be the set of zones that Ft can be located, where j is the index of zone. Note that Z^ consists of only one zone that is the entire rectangle facility. For each zone of Fj, Zjl is represented by where(xlj1,ylj1) and (xlj2,ylj2) are the coordinates of the bottom left corner and the top right corner of the zone, respectively. For step of determining the location of the department, the MP method is applied to obtain the optimal position of Ft within each zone in Z^. In this MP method, an ideal location of the cen-troid of Fi is first identified in such a way that the sum of rectilinear distances weighted by the flow quantities between Ft and the departments that have previously been located, denoted by the set B, is minimized. The objective function is formulated as follows: Minimize TTD{ fmn(\xi ~xn\ + \yj _yJ) (1) neB To determine the optimal location, (x*,y*), the objective function Eq. 1 is reformulated as Equations Eq. 2 and Eq. 3. Therefore, the values of x* and y* can be calculated separately. In Equations Eq. 2 and Eq. 3, TTDi(x) and TTDi(y) are piece wise linear and convex functions, where all xn (yn), for neB, are arranged in increasing order, i.e. x±'< Xt'< — W/2. Hence, the MP is x3' = 0 and x* = x3' = 0. Similarly, TTDs(y) = 2|y5-0| + 2|y5-0| + 2|y5-0| + 4|ys-4|. And Wy(1) = 2, Wy(2) = 2 + 2 = 4, Wy(3) = 2 + 2+ 2 = 6> W/2 . Hence, the MP in y -direction is y3' = 0 and yl = y-i' = 0. Therefore, the optimal location of Department 3 is (0, 0), which is marked by the dashed rectangle in Fig. 3. |B| ,|B| Fig. 3 Optimal location of Department 3 (represented by a dotted square) Nevertheless, this optimal location determined for Department 3, in fact, is infeasible because it overlaps with the other departments as shown in in Fig. 3. In this case, we have to determine a new location for Department 3 to continue our UA-FLP procedure. To this end, we determine the location in each zone for Department 3 such that the location is closest to the previously determined optimal location in both x-direction and y-direction. The rationale is that such position can minimize TTD for each zone. For example, the best positions for Department 3 in those considered zones are shown in Fig. 4(a)-4(f), which are respectively the closest locations to the optimal location that was previously determined. The department is to be located at the best position that attains the minimum TTDij among those zones. In this example, Department 3 has the same TTD^ at the positions as shown in Fig. 4(b) and Fig. 4(d). Thus, this tie is broken by randomly picking one of the two positions for locating Department 3. The location of the last department in the sequence of this example is also determined in the same way. Fig. 5 shows the final layout of the facility. Advances in Production Engineering & Management 11(4) 2016 263 Xiao, Zheng, Zhang, Kuo (a) y (b) 4 2 4 5 1 -5 0 7 (e) (d) (e) (f) Fig. 4 Closest location in each zone to the optimal location y -5 Fig. 5 Layout of the six departments of fixed shapes To determine if the department can be located at the intended position, we also have to consider the dimension of each zone zf which can be measured by wjl =xlj2 and h} =ylj2 ~y)i, where wjl and h} are respectively the width and the height of the zone. Let dwm and dhm be the width and the height of the department to be located, respectively. If a zone satisfies the condi- tions that Wjl >dwm and h- >dhm, it is feasible to locate Department m in this zone; otherwise, check if the subsequent zone can accommodate Department m. The procedure of the modified zone algorithm is summarized as follows: 264 Advances in Production Engineering & Management 11(4) 2016 A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem Step 1. Set i = 1. The centroid of F( is placed at (0, 0) in the coordinate system. Step 2. Set i = i + 1. Create the zone set, Z^ = [zjl\j = 1,...,/}, by using the zone updating procedure. Determine the optimal location, (x*, y*), for F(. Let TTD* be the minimum TTDij among the zones contained in the zone set. Set j = 1, TTD* = +<». Step 3. If xlJi + dwm/2 < x* < xlJ2-dwm/2 and ylJi + dhm/2 < y* < ylJ2 -dhm/2 (i.e. F^ with its centroid located at the optimal location can fit entirely within zone zlj), go to Step 3.1; otherwise, go to Step 3.2. Step 3.1 F( is optimally located at (x*, y*). Go to Step 5. Step 3.2 If wlj ^dwm and wlj ^ dhm, locate Di at the closest possible position in Zjl to the optimal location. Calculate TTDtj. If TTDtj 2 C penalty for the violation of the floor boundary condition, c= XZfmn(w+H) m n>m wm,hm Half of width and height of Department m vxm, vym Amount of violation of the floor boundary condition for Department m in the x-direction and the y-direction , respectively Our LP model to determine the dimensions of the departments is derived from the MIP formulated by Sherali et al. [13] and presented below: Minimize TTD = ^ ^ fmni^-mn + + Vm + ^ (4) m n>m m m subject to Advances in Production Engineering & Management 11(4) 2016 265 Xiao, Zheng, Zhang, Kuo ^mn —^ji ^ ^ (6) rfmn ^yin-Vil V™ < n (7) dmn ^Yn-ym Vm0 Vm (17) ^mrn^inn — 0 Vm < n (18) Objective function Eq. 4 consists of two terms: TTD between departments and the penalty for violation of the floor boundary condition. Constraints Eq. 5 to Eq. 8 determine the TTD between departments. Constraints Eq. 9 and Eq. 10 measure the violation of the floor boundary condition (in x-direction and y-direction, respectively), if it is infeasible to locate all the departments within the facility. Constraints Eq. 11 and Eq. 12 impose the bounds on the width and height for each department, where the upper bounds ub^ = min{W, ^Jamam}, ub^ = min{7/, ^Jamam}, and lower bounds lb^ = am/ublb^ = am/ubxm. Constraints Eq. 13 and Eq. 14 ensure that the departments do not overlap with each other. Constraints Eq. 15 is the polyhedral outer approximation for the area function, at = 4wmhm, with the number of tangential support points equal to A. The value of the tangential support points x is given in Eq. (16). As an example, with the relative positions of the departments obtained by the improved zone algorithm (as shown in Fig. 5), the final facility layout for locating the six departments with the exact dimensions can now be obtained by the LP. Their positions and dimensions are shown in Fig. 6. y 266 Fig. 6 Layout solution of the six departments with their dimensions determined Advances in Production Engineering & Management 11(4) 2016 A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem 3.4 SA algorithm With the facility layout solution obtained by the zone-LP approach, we implement an SA algorithm to improve the quality of the solution. The SA algorithm that we adopt is the same as the procedure proposed in Xiao et al. [22]. For the detail of the algorithm, we refer the reader to Xiao et al. [22]. 4. Computational experiments In this section, we conduct computational experiments to evaluate the performance of our proposed solution methodology for UA-FLP - an integrated method of zone-LP approach and SA algorithm. We use a set of widely tested instances in the literature to examine the efficiency of the solution methodology. There are five instances of different problem sizes included in the computational experiments: Problems 07 (with 7 departments), 08 (with 8 departments) and 09 (with 9 departments) from Meller et al. [12] and Two largest instances SC30 (with 30 departments) and SC35 (with 35 departments) from Liu and Meller [20]. The combined zone-LP and SA algorithm is run ten times for each computational instance. In the first phase of zone-LP algorithm, the dimensions of departments are fixed with the MAR because all departments tend to have a narrower rectangular shape to get a lower TTD. The parameter combination used in SA was T = 200 R = 0.8, and L = 1000 from Xiao et al. [21]. The results on the computational performance of our proposed approach are shown in Table 2. We present the averages and the standard deviations of the costs to examine the robustness of our proposed method. The computational results suggest that the proposed algorithm appears to be quite robust. For the three small-sized problems (07, 08, 09), the standard deviation is quite small, ranging from 0 to 0.57 (less than 0.5 % of the average). Although the magnitude of the standard deviation becomes large for the large-sized problems (SC30, SC35), its relative value is still small (less than 3 % of the average). For the computational efficiency, our proposed solution methodology can obtain the final solution within a reasonable time frame (less than 1 minute for the small-sized problems and less than 4 minutes for the large-sized problems). Given that facility layout planning is not a daily practice (is usually determined for several years), this computational time is negligible, and our method is suitable for the application in practice. Table 2 Qbjective values and the computing time obtained by the proposed algorithm Problem Best Mean Worst Standard deviation Average time (s) O7 89.25 89.25 89.25 0 33.13 O8 185.00 185.30 186.00 0.46 36.93 O9 185.00 185.45 186.5 0.57 41.80 SC30 3441.57 3663.21 3792.71 103.50 180.27 SC35 3347.94 3423.70 3555.89 69.06 225.94 Table 3 0bjective values, dimensions of the facilities, space utilizations resulting from the best solutions found by GRAPH [21] and our proposed algorithm GRAPH[21] The proposed algorithm Diff. in TTD (%) Problem TTD Layout dimension (WxH) Space utilization (%) TTD Layout dimension Space utilization (WxH) (%) O7 115.93 96.00 89.25 12x13.5 68.52 23.01 O8 239.00 96.00 185.00 12x16.5 74.24 22.59 O9 227.10 96.00 185.00 15x16.5 63.03 18.54 SC30 3601.20 15x12 90.56 3441.57 12.75x21.59 59.21 4.43 SC35 3351.12 16x15 80.00 3347.94 15.14x24.7 51.34 0.09 We also compare our proposed solution methodology with other existing algorithms in the literature and use them as benchmarks. We first compare the solution qualities obtained by our approach and the GRAPH algorithm [21], which attains the best known solutions for the computational instances. As shown in Table 3, our proposed outperforms GRAPH [21] in terms of TTD for all computational instances, but the space utilizations resulting from our algorithm are less than those from GRAPH. In our UA-FLPs, departments are arranged within an open-field floor Advances in Production Engineering & Management 11(4) 2016 267 Xiao, Zheng, Zhang, Kuo (as shown in Fig. 4 and Fig. 5) and the loss of consideration on space utilization in the objective function of the proposed model mainly causes the poor performance on space utilization. Therefore, a multi-objective optimization considering minimization of TTD and maximization of space utilization may be our future research topic. For reference, the best layouts solutions obtained by our proposed approach are shown in Appendix 1. The proposed algorithm also has an advantage of a shorter computing time due to its capability of searching in the restricted solution spaced. We conduct another study to examine the efficiency of our proposed methodology. In addition to GRAPH [21], we also include SEQUENCE [20] for the comparison of computational efficiencies of the different approaches. Computational results in Table 4 suggest that our algorithm takes a significantly shorter time to solve the UA-FLP. More importantly, the computing time appears to grow almost linearly as the number of departments increases. Compared with the approaches that appear to have an exponential computing time in the number of departments, our approach is apparently more suitable for problems of a larger size. The linear increase of computing time may be attributed to the proposed zone-LP algorithm which can construct the layout solution effectively. In each iteration of SA, the number of zones produced for putting departments by MP method is O (N) according to the zone algorithm. The proposed LP model is just used to determine the dimensions of departments. In general, the computing time is approximately proportional to the number of generated zones in each SA iteration and thus grows almost linearly as the number of departments increases. This further demonstrates the value of our proposed approach in advancing the computational performance for solving UA-FLP. Table 4 Average computing times of the SEQUENCE [20], GRAPH [21], and our proposed algorithm Instance Computing time (s) SEQUENCE [20] GRAPH [21] Our proposed algorithm O7 1644.0 228.0 33.13 O8 3056.0 390.0 36.93 O9 3879.0 222.0 41.80 SC30 7282.8 2442.0 180.27 SC35 9590.4 4728.0 225.94 5. Conclusion and future research This paper deals with UA-FLP and proposes a novel approach, which we call a combined zone-LP and SA algorithm, for solving large-sized UA-FLP. The zone-LP algorithm is a new layout construction method and consists of two phases. In the first phase, the shapes of departments are fixed to a rectangle with an allowable aspect ratio. Those departments of fixed shapes are then placed sequentially by using an improved zone algorithm, where an MP method is proposed to locating departments. By using relative positions of the departments obtained in this first phase, an LP is formulated to determine the exact locations and dimensions of departments. We also implement an SA algorithm to search the sequences of locating the departments within the facility and to prevent the search procedure from getting trapped at a local optimum. Computational experiments indicate that our proposed combined zone-LP and SA has a reasonably good performance, compared with existing algorithms in the literature on widely tested computational instances. We also note that there can be future directions extended from this research. In reality, departments of irregular shapes are commonplace; a future study may consider the facility layout problem with the consideration of departments with irregular shapes. Moreover, the results of computing experiments suggest that our proposed solution methodology may generate solutions leading to a low space utilization. For this case, we may adopt a multi-objective optimization approach whose goals are to minimize the material handling cost and to maximize space utilization. The trade-off between these two performance measures would also be an interesting research topic for investigation in the future. 268 Advances in Production Engineering & Management 11(4) 2016 A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem Acknowledgement The research has been supported by the National Natural Science Foundation of China (Grant No. 71501090, 71501093), the Natural Science Foundation of Jiangsu Higher Education Institutions of China (Grant No. 14KJD410001), the Natural Science Foundation of Jiangsu Province (Grant No. BK20150566), and the General Research Fund of Research Grants Council of Hong Kong (Grant No. 414313). References [1] Tompkins, J.A., White, J.A., Bozer, Y.A., Tanchoco, J.M.A. (2010). Facilities Planning, 4th edition, John Wiley & Sons, New York, USA. [2] Kusiak, A., Heragu, S.S. (1987). The facility layout problem, European Journal of Operational Research, Vol. 29, No. 3, 229-251, doi: 10.1016/0377-2217(87)90238-4. [3] Meller, R.D., Gau, K.Y. (1996). The facility layout problem: Recent and emerging trends and perspectives, Journal of Manufacturing Systems, Vol. 15, No. 5, 351-366, doi: 10.1016/0278-6125(96)84198-7. [4] Singh, S.P., Sharma, R.R.K. (2006). A review of different approaches to the facility layout problems, The International Journal of Advanced Manufacturing Technology, Vol. 30, No. 5-6,425-433, doi: 10.1007/s00170-005-0087-9. [5] Drira, A., Pierreval, H., Hajri-Gabouj, S. (2007). Facility layout problems: A survey, Annual Review in Control, Vol. 31, No. 2, 255-267, doi: 10.1016/j.arcontrol.2007.04.001. [6] Kulturel-Konak, S., Konak, A. (2011). Unequal area flexible bay facility layout using ant colony optimisation, International Journal of Production Research, Vol. 49, No.7, 1877-1902, doi: 10.1080/00207541003614371. [7] Jolai, F., Tavakkoli-Moghaddam, R., Taghipour, M. (2012). A multi-objective particle swarm optimisation algorithm for unequal sized dynamic facility layout problem with pickup/drop-off locations, International Journal of Production Research, Vol. 50, No. 15, 4279-4293, doi: 10.1080/00207543.2011.613863. [8] Navidi, H., Bashiri, M., Bidgoli, M.M. (2012). A heuristic approach on the facility layout problem based on game theory, International Journal of Production Research, Vol. 50, No. 6, 1512-1527, doi: 10.1080/00207543.2010. 550638. [9] Ficko, M., Palcic, I. (2013). Designing a layout using the modified triangle method, and genetic algorithms, International Journal of Simulation Modelling, Vol. 12, No. 4, 237-251, doi: 10.2507/IISIMM12(4)3.244. [10] Ficko, M., Brezovnik, S., Klancnik, S., Balic, J., Brezocnik, M., Pahole, I. (2010). Intelligent design of an unconstrained layout for a flexible manufacturing system, Neurocomputing, Vol. 73, No. 4-6, 639-647, doi: 10.1016/ j.neucom.2009.06.019. [11] Montreuil, B., 1991. A modelling framework for integrating layout design and flow network design, Progress in Materials Handling Research, Vol. 2, 95-115, doi: 10.1007/978-3-642-84356-3 8. [12] Meller, R.D., Narayanan, V., Vance, P.H. (1998). Optimal facility layout design, Operations Research Letters, Vol. 23, No. 3-5, 117-127, doi: 10.1016/S0167-6377(98)00024-8. [13] Sherail, H.D., Fraticelli, B.M.P., Meller, R.D. (2003). Enhanced model formulations for optimal facility layout, Operations Research, Vol. 51, No. 4, 629-644, doi: 10.1287/opre.51.4.629.16096. [14] Meller, R.D., Chen, W., Sherali, H.D. (2007). Applying the sequence-pair representation to optimal facility layout design, Operations Research Letters, Vol. 35, No. 5, 651-659, doi: 10.1016/j.orl.2006.10.007. [15] Kim, J.G., Kim, Y.D. (2000). Layout planning for facilities with fixed shapes and input and output points, International Journal of Production Research, Vol. 38, No. 18, 4635-4653, doi: 10.1080/00207540050205550. [16] Das, S.K. (1993). A facility layout method for flexible manufacturing systems, International Journal of Production Research, Vol. 31, No. 2, 279-297, doi: 10.1080/00207549308956725. [17] Rajasekharan, M., Peters, B.A., Yang, T. (1998). A genetic algorithm for facility layout design in flexible manufacturing systems, International Journal of Production Research, Vol. 36, No. 1, 95-110, doi: 10.1080/00207549 8193958. [18] Scholz, D., Petrick, A., Domschke, W. (2009). STaTS: A Slicing Tree and Tabu Search based heuristic for unequal area faciltiy layout problem, European Journal of Operational Research, Vol. 197, No. 1, 166-178, doi: 10.1016/ j.ejor.2008.06.028. [19] Komarudin, Wong, K.Y. (2010). Applying ant system for solving unequal area facility layout problems, European Journal of Operational Research, Vol. 202, No. 3, 730-746, doi: 10.1016/j.ejor.2009.06.016. [20] Liu, Q., Meller, R.D. (2007). A sequence-pair representation and MIP model based heuristic for the facility layout problem with rectangular departments, IIE Transactions, Vol. 39, No. 4, 337-394, doi: 10.1080/07408170600 844108. [21] Bozer, Y.A., Wang, C.T. (2012). A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem, European Journal of Operational Research, Vol. 218, No. 2, 382-391, doi: 10.1016/ j.ejor.2011.10.052. [22] Xiao, Y., Seo, Y., Seo, M. (2013). A two-step heuristic algorithm for layout design of unequal-sized facilities with input/output points, International Journal of Production Research, Vol. 51, No. 14, 4200-4222, doi: 10.1080/ 00207543.2012.752589. Advances in Production Engineering & Management 11(4) 2016 269 Xiao, Zheng, Zhang, Kuo Appendix 1 The best layouts obtained by our proposed algorithm for the experimental instances from Meller et al. [10] and Liu and Meller [19]. Layout with seven departments Layout with eight departments Layout with nine departments 25 r 15 a 20 19 23 zn ii i 13 3 29 27 26 0 2 4 6 8 10 12 14 Layout with 30 departments 16 1D "26 2« 19 £IE 15 13 14 32 12 H 20 30 29 22 34 27 35 ! 4 6 8 10 12 14 Layout with 35 departments 270 Advances in Production Engineering & Management 11(4) 2016