The single-row layout problem (SRLP), also known as the one-dimensional layout problem, deals with arranging a number of rectangular machines/departments with equal or varying dimensions on a straight line. Since the problem is proved to be NP-hard, there are several heuristics developed to solve the problem. This study introduces both a Clonal Selection Algorithm (CSA) and a Bacterial Foraging Algorithm (BFA) for SRLP. The performance of the algorithms is assessed by using three (small, medium, and large sized) well known test problems available in the literature. The promising results illustrated that both algorithms had generated the best known solutions so far for most of the problems or provided better results for a number of problems. 1. Introduction The objective in SRLP is to minimize the total material handling costs (MHC) and to find the optimum layout for machines in one dimension. The SRLP is also known as one-dimensional layout and usually refereed as Linear Ordering Problem, where all machines have unit length. Braglia [1] pointed that the problem is widely implemented in the configuration of manufacturing systems. Kusiak and Heragu [2] stated that the type of material handling device in Flexible Manufacturing System determines the pattern to be used for the layout of machines. Therefore, the design problem that is related with material handling devices such as handling robots and Automated Guided Vehicles (AGV) is usually considered as an SRLP. Further, the problem has applications in real-life applications such as the room arrangement problem along the corridor (i.e., hotels and hospitals) [3]; the arrangement of books on a shelf in a library; the assignment of disk cylinders to files [4]. Suresh and Sahu [5] have identified the problem that has wide application areas, as an NP-complete type. Therefore, several heuristics have been proposed to solve this problem in the literature. The pioneering studies include Karp and Held [6], Nugent et al. [7], Simmons [3], and Hall [8]. Neghabat [9] introduced a procedure where a complete solution is obtained by inserting one machine at a time to the end of the solution yet obtained. Love and Wong [10] presented a linear mixed integer-programming model for the single row layout problem and solved it using the mixed integer-programming algorithm. Drezner [11] introduced a heuristic that is based on the eigenvectors of a transformed flow matrix. Heragu and Kusiak [12] proposed the heuristic where a pair of facilities with the largest adjusted flow is initially laid; and then the partial order is
References
[1]
M. Braglia, “Heuristics for single-row layout problems in flexible manufacturing systems,” Production Planning and Control, vol. 8, no. 6, pp. 558–567, 1997.
[2]
A. Kusiak and S. S. Heragu, “The facility layout problem,” European Journal of Operational Research, vol. 29, no. 3, pp. 229–251, 1987.
[3]
D. M. Simmons, “One dimensional space allocation, an ordering algorithm,” Operations Research, vol. 17, no. 5, pp. 812–826, 1969.
[4]
J. C. Picard and M. Queyranne, “On the one-dimensional space allocation problem,” Operations Research, vol. 29, no. 2, pp. 371–391, 1981.
[5]
G. Suresh and S. Sahu, “Multiobjective facility layout using simulated annealing,” International Journal of Production Economics, vol. 32, no. 2, pp. 239–254, 1993.
[6]
R. M. Karp and M. Held, “Finite-state process and dynamic programming,” SIAM Journal of Applied Mathematics, vol. 15, pp. 201–211, 1967.
[7]
C. E. Nugent, T. E. Vollman, and J. Ruml, “An experimental comparison of techniques for the assignment of facilities to locations,” Operations Research, vol. 16, pp. 150–173, 1968.
[8]
H. K. Hall, “An r-dimensional quadratic placement algorithm,” Management Science, vol. 17, no. 3, pp. 219–229, 1970.
[9]
F. Neghabat, “An efficient equipment layout algorithm,” Operations Research, vol. 22, no. 3, pp. 622–628, 1974.
[10]
R. F. Love and J. Y. Wong, “On solving a one-dimensional space allocation problem with integer programming,” INFOR Journal, vol. 14, no. 2, pp. 139–143, 1976.
[11]
Z. Drezner, “A heuristic procedure for the layout of a large number of facilities,” Management Science, vol. 33, no. 7, pp. 907–915, 1987.
[12]
S. S. Heragu and A. Kusiak, “Machine layout problem in flexible manufacturing systems,” Operations Research, vol. 36, no. 2, pp. 258–268, 1988.
[13]
S. S. Heragu and A. Kusiak, “Efficient models for the facility layout problem,” European Journal of Operational Research, vol. 53, no. 1, pp. 1–13, 1991.
[14]
D. Romero and A. Sánchez-Flores, “Methods for the one-dimensional space allocation problem,” Computers and Operations Research, vol. 17, no. 5, pp. 465–473, 1990.
[15]
S. S. Heragu and A. S. Alfa, “Experimental analysis of simulated annealing based algorithms for the layout problem,” European Journal of Operational Research, vol. 57, no. 2, pp. 190–202, 1992.
[16]
P. Kouvelis and W. C. Chiang, “Simulated annealing procedure for single row layout problems in flexible manufacturing systems,” International Journal of Production Research, vol. 30, no. 4, pp. 717–732, 1992.
[17]
K. R. Kumar, G. C. Hadjinicola, and T. L. Lin, “A heuristic procedure for the single-row facility layout problem,” European Journal of Operational Research, vol. 87, no. 1, pp. 65–73, 1995.
[18]
M. Braglia, “Optimization of a simulated-annealing-based heuristic for single row machine layout problem by genetic algorithm,” International Transactions in Operational Research, vol. 3, no. 1, pp. 37–49, 1996.
[19]
Y. C. Ho and C. L. Moodie, “Machine layout with a linear single-row flow path in an automated manufacturing system,” Journal of Manufacturing Systems, vol. 17, no. 1, pp. 1–22, 1998.
[20]
H. Djellab and M. Gourgand, “A new heuristic procedure for the single-row facility layout problem,” International Journal of Computer Integrated Manufacturing, vol. 14, no. 3, pp. 270–280, 2001.
[21]
D. S. Chen, Q. Wang, and H. C. Chen, “Linear sequencing for machine layouts by a modified simulated annealing,” International Journal of Production Research, vol. 39, no. 8, pp. 1721–1732, 2001.
[22]
M. Ficko, M. Brezocnik, and J. Balic, “Designing the layout of single- and multiple-rows flexible manufacturing system by genetic algorithms,” Journal of Materials Processing Technology, vol. 157-158, pp. 150–158, 2004.
[23]
M. Solimanpur, P. Vrat, and R. Shankar, “An ant algorithm for the single row layout problem in flexible manufacturing systems,” Computers and Operations Research, vol. 32, no. 3, pp. 583–598, 2005.
[24]
M. F. Anjos, A. Kennings, and A. Vannelli, “A semidefinite optimization approach for the single-row layout problem with unequal dimensions,” Discrete Optimization, vol. 2, no. 2, pp. 113–122, 2005.
[25]
A. R. S. Amaral, A. Camatta, and M. Wright, “Subset moves based simulated annealing applied to the one-dimensional layout problem,” in Proceedings of the 6th Metaheuristics International Conference, Vienna, Austria, August 2005.
[26]
S. G. Ponnambalam, R. Venkataraman, H. H. Sudhan, and P. V. Chatlerjee, “Hybrid search algorithms for a single-row layout in automated manufacturing systems,” International Journal of Industrial Engineering, vol. 12, no. 2, pp. 117–126, 2005.
[27]
A. R. S. Amaral, “On the exact solution of a facility layout problem,” European Journal of Operational Research, vol. 173, no. 2, pp. 508–518, 2006.
[28]
S. Kumar, P. Asokan, S. Kumanan, and B. Varma, “Scatter search algorithm for single row layout problem in FMS,” Advances in Production Engineering and Management, vol. 3, no. 4, pp. 193–204, 2008.
[29]
Y. T. Teo and S. G. Ponnambalam, “A hybrid ACO/PSO heuristic to solve single row layout problem,” in Proceedings of the 4th IEEE Conference on Automation Science and Engineering (CASE '08), pp. 597–602, Washington, DC, USA, August 2008.
[30]
M. F. Anjos and A. Vannelli, “Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes,” INFORMS Journal on Computing, vol. 20, no. 4, pp. 611–617, 2008.
[31]
A. R. S. Amaral, “A new lower bound for the single row facility layout problem,” Discrete Applied Mathematics, vol. 157, no. 1, pp. 183–190, 2009.
[32]
M. T. Lin, “The single-row machine layout problem in apparel manufacturing by hierarchical order-based genetic algorithm,” International Journal of Clothing Science and Technology, vol. 21, no. 1, pp. 31–43, 2009.
[33]
H. Samarghandi and K. Eshghi, “An efficient tabu algorithm for the single row facility layout problem,” European Journal of Operational Research, vol. 205, no. 1, pp. 98–105, 2010.
[34]
D. Datta, A. R. S. Amaral, and J. R. Figueira, “Single row facility layout problem using a permutation-based genetic algorithm,” European Journal of Operational Research, vol. 213, no. 2, pp. 388–394, 2011.
[35]
I. Boussaid, J. Lepagnot, and P. Siarry, “A survey on optimization metaheuristics,” Information Sciences, vol. 237, pp. 82–117, 2013.
[36]
F. M. Burnet, The Clonal Selection Theory of Acquired Immunity, Cambridge University Press, Cambridge, UK, 1959.
[37]
R. H. Donangelo and H. Fort, “Model for mutation in bacterial populations,” Physical Review Letters, vol. 89, no. 3, Article ID 038101, 4 pages, 2002.
[38]
R. C. Paton, C. Vlachos, Q. H. Wu, and J. R. Saunders, “Simulated bacterially-inspired problem solving—the behavioural domain,” Natural Computing, vol. 5, no. 1, pp. 43–65, 2006.
[39]
D. H. Kim, A. Abraham, and J. H. Cho, “A hybrid genetic algorithm and bacterial foraging approach for global optimization,” Information Sciences, vol. 177, no. 18, pp. 3918–3937, 2007.
[40]
T. Datta and I. S. Misra, “Improved adaptive bacteria foraging algorithm in optimization of antenna array for faster convergence,” Progress in Electromagnetics Research C, vol. 1, pp. 143–157, 2008.
[41]
B. Niu, Y. L. Zhu, X. X. He, H. Shen, and Q. H. Wu, “A lifecycle model for simulating bacterial evolution,” Neurocomputing, vol. 72, no. 1–3, pp. 142–148, 2008.
[42]
S. Das, A. Chowdhury, and A. Abraham, “A bacterial evolutionary algorithm for automatic data clustering,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '09), pp. 2403–2410, Trondheim, Norway, May 2009.
[43]
H. Chen, Y. Zhu, and K. Hu, “Cooperative bacterial foraging optimization,” Discrete Dynamics in Nature and Society, vol. 2009, Article ID 815247, 17 pages, 2009.
[44]
A. Biswas, S. Das, A. Abraham, and S. Dasgupta, “Stability analysis of the reproduction operator in bacterial foraging optimization,” Theoretical Computer Science, vol. 411, no. 21, pp. 2127–2139, 2010.
[45]
B. H. Ulutas and A. A. Islier, “Parameter setting for clonal selection algorithm in facility layout problems,” in Computational Science and Its Applications—ICCSA 2007, O. Gervasi and M. Gavrilova, Eds., vol. 4705 of Lecture Notes in Computer Science, part 1, pp. 886–899, Springer, Berlin, Germany, 2007.
[46]
O. Engin and A. D？yen, “A new approach to solve hybrid flow shop scheduling problems by artificial immune system,” Future Generation Computer Systems, vol. 20, no. 6, pp. 1083–1095, 2004.
[47]
Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, New York, NY, USA, 1996.
[48]
M. F. Anjos and G. Yen, “Provably near-optimal solutions for very large single-row facility layout problems,” Optimization Methods and Software, vol. 24, no. 4-5, pp. 805–817, 2009.
[49]
H. Samarghandi, P. Taabayan, and F. F. Jahantigh, “A particle swarm optimization for the single row facility layout problem,” Computers and Industrial Engineering, vol. 58, no. 4, pp. 529–534, 2010.
