A Hybrid Clonal Selection for the Single Row Facility Layout Problem with Unequal Dimensions

ABSTRACT

The single row facility layout problem (SRFLP) is an important combinatorial optimization problem where a given set of facilities have to be arranged in a single row to minimize the weighted sum of the distances between all pairs of facil-ities. In this paper, ahybrid method for single row facility layout problem is proposed in which, the simulated annealing (SA) is embedded in the clonal selection algorithm (CSA). The performance of the proposed algorithm is tested on benchmark problems. Computational results show the efficiency of the proposed algorithm compared to other heuristics.

The single row facility layout problem (SRFLP) is an important combinatorial optimization problem where a given set of facilities have to be arranged in a single row to minimize the weighted sum of the distances between all pairs of facil-ities. In this paper, ahybrid method for single row facility layout problem is proposed in which, the simulated annealing (SA) is embedded in the clonal selection algorithm (CSA). The performance of the proposed algorithm is tested on benchmark problems. Computational results show the efficiency of the proposed algorithm compared to other heuristics.

Cite this paper

H. Hosseini-Nasab and L. Emami, "A Hybrid Clonal Selection for the Single Row Facility Layout Problem with Unequal Dimensions,"*iBusiness*, Vol. 4 No. 3, 2012, pp. 216-221. doi: 10.4236/ib.2012.43027.

H. Hosseini-Nasab and L. Emami, "A Hybrid Clonal Selection for the Single Row Facility Layout Problem with Unequal Dimensions,"

References

[1] W. Liu and A. Vannelli, “Generating Lower Bounds for the Linear Arrangement Problem,” Discrete Applied Mathematics, Vol. 59, No. 2, 1995, pp. 137-151. doi:10.1016/0166-218X(93)E0168-X

[2] J. E. Mitchell and B. Borchers, “Solving Linear Ordering Problems with a Combined Interior Point/Simplex Cutting Plane Algorithm,” High Performance Optimization, Vol. 33, 2000, pp. 349-366.

[3] E. Cela, “The Quadratic Assignment Problem, Theory and Algorithms,” Kluwer Academic Publishers, Dordrecht, 1998.

[4] S. S. Heragu and A. Kusiak, “Machine Layout Problem in Flexible Manufacturing Systems,” Operations Research, Vol. 36, No. 2, 1988, pp. 258-268. doi:10.1287/opre.36.2.258

[5] M. R. Garey and D. S. Johnson, “Computers and Intractability: An Introduction to the Theory of NP-Completeness,” Freeman, New York, 1979.

[6] D. M. Simmons, “One-Dimensional Space AllocationAn ordering algorithm,” Operations Research, Vol. 17, No. 5, 1969, pp. 812-826.

[7] D. M. Simmons, “A Further Note on One-Dimensional Space Allocation,” Operations Research, Vol. 19, No. 1, 1971, p. 249. doi:10.1287/opre.19.1.249

[8] R. M. Karp and M. Held, “Finite-State Processes and Dynamic Programming,” SIAM Journal of Applied Mathematics, Vol. 15, No. 3, 1967, pp. 693-718.

[9] J. C. Picard and M. Queyranne, “On the One-Dimensional Space Allocation Problem,” Operations Research, Vol. 29, No. 2, 1981, pp. 371-391. doi:10.1287/opre.29.2.371

[10] S. S. Heragu and A. Kusiak, “Efficient Models for the Facility Layout Problem,” European Journal of Operational Research, Vol. 53, No. 1, 1991, pp. 1-13.

[11] R. F. Love and J. Y. Wong, “On Solving a One-Dimensional Space Allocation Problem with Integer Programming,” INFOR, Vol. 14, 1976, pp. 139-143.

[12] A. R. S. Amaral, “On the Exact Solution of a Facility Layout Problem,” European Journal of Operational Research, Vol. 173, No. 2, 2006, pp. 508-518.

[13] A. R. S. Amaral, “An Exact Approach for the One-Dimensional Facility Layout Problem,” Operations Research, Vol. 56, No. 4, 2008, pp. 1026-1033. doi:10.1287/opre.1080.0548

[14] A. Amaral, “A New Lower Bound for the Single Row Facility Layout Problem,” Discrete Applied Mathematics, Vol. 157, No. 1, 2009, pp. 183-190. doi:10.1016/j.dam.2008.06.002

[15] G. Suresh and S. Sahu, “Multiobjective Facility Layout Using Simulated Annealing,” International Journal of Production Economics, Vol. 32, No. 2, 1993, pp. 239-254. doi:10.1016/0925-5273(93)90071-R

[16] F. Neghabat, “An Efficient Equipment Layout Algorithm,” Operations Research, Vol. 22, No. 3, 1974, pp. 622-628. doi:10.1287/opre.22.3.622

[17] Z. Drezner, “A Heuristic Procedure for the Layout of a Large Number of Facilities,” Management Science, Vol. 7, No. 33, 1987, pp. 907-915. doi:10.1287/mnsc.33.7.907

[18] S. S. Heragu and A. S. Alfa, “Experimental Analysis of Simulated Annealing Based Algorithms for the Facility Layout Problem,” European Journal of Operational Research, Vol. 57, No. 2, 1992, pp. 190-202. doi:10.1016/0377-2217(92)90042-8

[19] 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, 1995, 65-73. doi:10.1016/0377-2217(94)00062-H

[20] M. Braglia, “Optimization of a Simulated-Annealing-Based Heuristic for Single Row Machine Layout Problem by Genetic Algorithm,” International Transactions in Operational Research, Vol. 1, No. 3, 1996, pp. 37-49. doi:10.1111/j.1475-3995.1996.tb00034.x

[21] M. Solimanpur, P. Vrat and R. Shankar, “An Ant Algorithm for the Single Row Layout Problem in Flexible Manufacturing Systems,” Computers & Operations Research, Vol. 32, No. 3, 2005, pp. 583-598. doi:10.1016/j.cor.2003.08.005

[22] 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, 2008, pp. 611-617. doi:10.1287/ijoc.1080.0270

[23] M. F. Anjos and C. Kong, “FLP database,” 2007. http://flplib.uwaterloo.ca

[24] P. Hungerlander and F. Rendl, “A Computational Study for the Single-Row Facility Layout Problem,” 2011. http://www.optimization-nline.org/DBFILE/2011/05/ 3029.pdf.

[25] 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, 2005, pp. 113-122. doi:10.1016/j.disopt.2005.03.001

[26] S. Kumar, et al., “Scatter Search Algorithm for Single Row Layout Problem in FMS,” Advances in Production Engineering and Management, Vol. 3, No. 4, 2008, pp. 193-204.

[27] Y. T. Teo and S. G. Ponnambalam, “A Hybrid ACO/PSO Heuristic to Solve Single Row Layout Problem,” 4th IEEE Conference on Automation Science and Engineering, Washington DC, 23-26 August 2008.

[28] 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, 2009, pp. 31-43. doi:10.1108/09556220910923737

[29] 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, 2010, pp. 98-105. doi:10.1016/j.ejor.2009.11.034

[30] D. Datta, A. R. 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, 2011, pp. 388-394.

[31] D. Dasgupta, “An Overview of Artificial Immune Systems and Their Applications,” In: D. Dasgupta, Ed., Artificial Immune Systems and Their Applications, Springer-Verlag, Berlin, 1998, pp. 3-18.

[32] O. Engin and A. Doyen, “Artificial Immune Systems and Applications in Industrial Problems,” Gazi University Journal of Science, Vol. 17, No. 1, 2004, pp. 71-84.

[33] X. Wang, “Clonal Selection Algorithm in Power Filter Optimization,” Proceedings of the IEEE Mid-Summer Workshop on Soft Computing in Industrial Applications, Espoo, 28-30 June 2005, pp. 122-127.

[34] S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671-680.

[1] W. Liu and A. Vannelli, “Generating Lower Bounds for the Linear Arrangement Problem,” Discrete Applied Mathematics, Vol. 59, No. 2, 1995, pp. 137-151. doi:10.1016/0166-218X(93)E0168-X

[2] J. E. Mitchell and B. Borchers, “Solving Linear Ordering Problems with a Combined Interior Point/Simplex Cutting Plane Algorithm,” High Performance Optimization, Vol. 33, 2000, pp. 349-366.

[3] E. Cela, “The Quadratic Assignment Problem, Theory and Algorithms,” Kluwer Academic Publishers, Dordrecht, 1998.

[4] S. S. Heragu and A. Kusiak, “Machine Layout Problem in Flexible Manufacturing Systems,” Operations Research, Vol. 36, No. 2, 1988, pp. 258-268. doi:10.1287/opre.36.2.258

[5] M. R. Garey and D. S. Johnson, “Computers and Intractability: An Introduction to the Theory of NP-Completeness,” Freeman, New York, 1979.

[6] D. M. Simmons, “One-Dimensional Space AllocationAn ordering algorithm,” Operations Research, Vol. 17, No. 5, 1969, pp. 812-826.

[7] D. M. Simmons, “A Further Note on One-Dimensional Space Allocation,” Operations Research, Vol. 19, No. 1, 1971, p. 249. doi:10.1287/opre.19.1.249

[8] R. M. Karp and M. Held, “Finite-State Processes and Dynamic Programming,” SIAM Journal of Applied Mathematics, Vol. 15, No. 3, 1967, pp. 693-718.

[9] J. C. Picard and M. Queyranne, “On the One-Dimensional Space Allocation Problem,” Operations Research, Vol. 29, No. 2, 1981, pp. 371-391. doi:10.1287/opre.29.2.371

[10] S. S. Heragu and A. Kusiak, “Efficient Models for the Facility Layout Problem,” European Journal of Operational Research, Vol. 53, No. 1, 1991, pp. 1-13.

[11] R. F. Love and J. Y. Wong, “On Solving a One-Dimensional Space Allocation Problem with Integer Programming,” INFOR, Vol. 14, 1976, pp. 139-143.

[12] A. R. S. Amaral, “On the Exact Solution of a Facility Layout Problem,” European Journal of Operational Research, Vol. 173, No. 2, 2006, pp. 508-518.

[13] A. R. S. Amaral, “An Exact Approach for the One-Dimensional Facility Layout Problem,” Operations Research, Vol. 56, No. 4, 2008, pp. 1026-1033. doi:10.1287/opre.1080.0548

[14] A. Amaral, “A New Lower Bound for the Single Row Facility Layout Problem,” Discrete Applied Mathematics, Vol. 157, No. 1, 2009, pp. 183-190. doi:10.1016/j.dam.2008.06.002

[15] G. Suresh and S. Sahu, “Multiobjective Facility Layout Using Simulated Annealing,” International Journal of Production Economics, Vol. 32, No. 2, 1993, pp. 239-254. doi:10.1016/0925-5273(93)90071-R

[16] F. Neghabat, “An Efficient Equipment Layout Algorithm,” Operations Research, Vol. 22, No. 3, 1974, pp. 622-628. doi:10.1287/opre.22.3.622

[17] Z. Drezner, “A Heuristic Procedure for the Layout of a Large Number of Facilities,” Management Science, Vol. 7, No. 33, 1987, pp. 907-915. doi:10.1287/mnsc.33.7.907

[18] S. S. Heragu and A. S. Alfa, “Experimental Analysis of Simulated Annealing Based Algorithms for the Facility Layout Problem,” European Journal of Operational Research, Vol. 57, No. 2, 1992, pp. 190-202. doi:10.1016/0377-2217(92)90042-8

[19] 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, 1995, 65-73. doi:10.1016/0377-2217(94)00062-H

[20] M. Braglia, “Optimization of a Simulated-Annealing-Based Heuristic for Single Row Machine Layout Problem by Genetic Algorithm,” International Transactions in Operational Research, Vol. 1, No. 3, 1996, pp. 37-49. doi:10.1111/j.1475-3995.1996.tb00034.x

[21] M. Solimanpur, P. Vrat and R. Shankar, “An Ant Algorithm for the Single Row Layout Problem in Flexible Manufacturing Systems,” Computers & Operations Research, Vol. 32, No. 3, 2005, pp. 583-598. doi:10.1016/j.cor.2003.08.005

[22] 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, 2008, pp. 611-617. doi:10.1287/ijoc.1080.0270

[23] M. F. Anjos and C. Kong, “FLP database,” 2007. http://flplib.uwaterloo.ca

[24] P. Hungerlander and F. Rendl, “A Computational Study for the Single-Row Facility Layout Problem,” 2011. http://www.optimization-nline.org/DBFILE/2011/05/ 3029.pdf.

[25] 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, 2005, pp. 113-122. doi:10.1016/j.disopt.2005.03.001

[26] S. Kumar, et al., “Scatter Search Algorithm for Single Row Layout Problem in FMS,” Advances in Production Engineering and Management, Vol. 3, No. 4, 2008, pp. 193-204.

[27] Y. T. Teo and S. G. Ponnambalam, “A Hybrid ACO/PSO Heuristic to Solve Single Row Layout Problem,” 4th IEEE Conference on Automation Science and Engineering, Washington DC, 23-26 August 2008.

[28] 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, 2009, pp. 31-43. doi:10.1108/09556220910923737

[29] 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, 2010, pp. 98-105. doi:10.1016/j.ejor.2009.11.034

[30] D. Datta, A. R. 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, 2011, pp. 388-394.

[31] D. Dasgupta, “An Overview of Artificial Immune Systems and Their Applications,” In: D. Dasgupta, Ed., Artificial Immune Systems and Their Applications, Springer-Verlag, Berlin, 1998, pp. 3-18.

[32] O. Engin and A. Doyen, “Artificial Immune Systems and Applications in Industrial Problems,” Gazi University Journal of Science, Vol. 17, No. 1, 2004, pp. 71-84.

[33] X. Wang, “Clonal Selection Algorithm in Power Filter Optimization,” Proceedings of the IEEE Mid-Summer Workshop on Soft Computing in Industrial Applications, Espoo, 28-30 June 2005, pp. 122-127.

[34] S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671-680.