Two Strategies Based on Meta-Heuristic Algorithms for Parallel Row Ordering Problem (PROP)

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Damghan University.Damghan, Iran

2 School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

3 Department of Industrial Engineering, Damghan University, Damghan, Iran

Abstract

Proper arrangement of facility layout is a key issue in management that influences efficiency and the profitability of the manufacturing systems. Parallel Row Ordering Problem (PROP) is a special case of facility layout problem and consists of looking for the best location of n facilities while similar facilities (facilities which has some characteristics in common) should be arranged in a row and dissimilar facilities should be arranged in a parallel row. As PROP is a new introduced NP-hard problem, only a mixed integer programming model is developed to formulate this problem. So to solve large scale instances of this problem, heuristic and meta-heuristic algorithms can be useful. In this paper, two strategies based on genetic algorithm (GA) and a novel population based simulated annealing algorithm (PSA) to solve medium and large instances of PROP are proposed. Also several test problems of PROP in two groups with different sizes that have been extracted from the literature are solved to evaluate the proposed algorithms in terms of objective function value and computational time. According to the results, in the first group of instances, both algorithms almost have equal performances, and in the second group PSA shows better performance by increasing the size of test problems.

Keywords

Main Subjects

References

Ahonen, H., Gomes de Alvarenga, A., & Amaral, A. (2014). Simulated annealing and tabu search approaches for the corridor allocation problem. European Journal of Operational Research, 232(1), 221-233.
Akbari, M., & Maadi, M. (2011). Imperialist competitive algorithm for solving single row facility layout problem. Paper presented at the 4th International Conference of Iranian Operations Research Society, (In Persian).
Amaral, A. R. (2006). On the exact solution of a facility layout problem. European Journal of Operational Research, 173(2), 508-518.
Amaral, A. R. (2008). An exact approach to the one-dimensional facility layout problem. Operations Research, 56(4), 1026-1033.
Amaral, A. R. (2009). A new lower bound for the single row facility layout problem. Discrete Applied Mathematics, 157(1), 183-190.
Amaral, A. R. (2012). The corridor allocation problem. Computers & Operations Research, 39(12), 3325-3330.
Amaral, A. R. (2013a). Optimal solutions for the double row layout problem. Optimization Letters, 7(2), 407–413.
Amaral, A. R. (2013b). A parallel ordering problem in facilities layout. Computers & Operations Research, 40(12), 2930-2939.
Amaral, A. R., & Letchford, A. N. (2013). A polyhedral approach to the single row facility layout problem. Mathematical programming, 141(1-2), 453-477.
Anjos, M. F., Fischer, A., & Hungerländer, P. (2016). Solution approaches for the double-row equidistant facility layout problem. In Operations Research Proceedings (pp. 17-23). Springer.
Anjos, M. F., Kennings, A., & Vannelli, A. (2005). A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Discrete Optimization, 2(2), 113-122.
Anjos, M. F., & Vannelli, A. (2008). Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS Journal on Computing, 20(4), 611-617.
Anjos, M. F., & Yen, G. (2009). Provably near-optimal solutions for very large single-row facility layout problems. Optimization Methods & Software, 24(4-5), 805-817
Bahrami, F., Safari, H., Tavakkoli-Moghaddam, R., & Modarres Yazdi, M. (2017). On modelling door-to-door parcel delivery services in Iran. Iranian Journal of Management Studies, 9(4), 883-906.
Braglia, M. (1996). Optimisation of a simulated-annealing-based heuristic for single row machine layout problem by genetic algorithm. International Transactions in Operational Research, 3(1), 37-49.
Chung, J., & Tanchoco, J. (2010). The double row layout problem. International Journal of Production Research, 48(3), 709-727.
Datta, D., Amaral, A. R., & Figueira, J. R. (2011). Single row facility layout problem using a permutation-based genetic algorithm. European Journal of Operational Research, 213(2), 388-394.
Deb, K., & Kalyanmoy, D. (2001). Multi-objective optimization using evolutionary algorithms. New York, NY: John Wiley & Sons, Inc.
Djellab, H., & Gourgand, M. (2001). A new heuristic procedure for the single-row facility layout problem. International Journal of Computer Integrated Manufacturing, 14(3), 270-280.
Drira, A., Pierreval, H., & Hajri-Gabouj, S. (2007). Facility layout problems: A survey. Annual Reviews in Control, 31(2), 255-267.
Ficko, M., Brezocnik, M., & Balic, J. (2004). Designing the layout of single-and multiple-rows flexible manufacturing system by genetic algorithms. Journal of Materials Processing Technology, 157, 150-158.
Ghosh, D., & Kothari, R. (2012). Population heuristics for the corridor allocation problem. Indian Institute of Management Ahmedabad (IIMA), Research and Publication Department.
Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine Learning, 3(2), 95-99.
Gomes de Alvarenga, A., Negreiros-Gomes, F. J., & Mestria, M. R. (2000). Metaheuristic methods for a class of the facility layout problem. Journal of Intelligent Manufacturing, 11(4), 421-430.
Guan, J., & Lin, G. (2016). Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem. European Journal of Operational Research, 248(3), 899-909.
Heragu, S. S., & Alfa, A. S. (1992). Experimental analysis of simulated annealing based algorithms for the layout problem. European Journal of Operational Research, 57(2), 190-202.
Heragu, S. S., & Kusiak, A. (1988). Machine layout problem in flexible manufacturing systems. Operations Research, 36(2), 258-268.
Heragu, S. S., & Kusiak, A. (1991). Efficient models for the facility layout problem. European Journal of Operational Research, 53(1), 1-13.
Hosseini-Nasab, H., & Emami, L. (2013). A hybrid particle swarm optimisation for dynamic facility layout problem. International Journal of Production Research, 51(14), 4325-4335.
Hsu, C.-M. (2012). Improving the lighting performance of a 3535 packaged hi-power LED using genetic programming, quality loss functions and particle swarm optimization. Applied Soft Computing, 12(9), 2933-2947.
Hungerländer, P., & Rendl, F. (2013). Semidefinite relaxations of ordering problems. Mathematical Programming, 140(1), 77-97.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Kothari, R., & Ghosh, D. (2012a). Path relinking for single row facility layout. Indian Institute of Management, Ahmedabad.
Kothari, R., & Ghosh, D. (2013b). Insertion based Lin–Kernighan heuristic for single row facility layout. Computers & Operations Research, 40(1), 129-136.
Kothari, R., & Ghosh, D. (2013bc). Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods. European Journal of Operational Research, 224(1), 93-100.
Kothari, R., & Ghosh, D. (2014a). An efficient genetic algorithm for single row facility layout. Optimization Letters, 8(2), 679-690.
Kothari, R., & Ghosh, D. (2014b). A scatter search algorithm for the single row facility layout problem. Journal of Heuristics, 20(2), 125-142.
Kouvelis, P., & Chiang, W.-C. (1996). Optimal and heuristic procedures for row layout problems in automated manufacturing systems. Journal of the Operational Research Society, 47(6), 803-816.
Kumar, K. R., Hadjinicola, G. C., & Lin, T.-L. (1995). A heuristic procedure for the single-row facility layout problem. European Journal of Operational Research, 87(1), 65-73.
Kunlei, L., Chaoyong, Z., Liang, G., & Xinyu, S. (2011). Single row facility layout problem using an imperialist competitive algorithm. Proceedings from the 41st International Conference on Computers & Industrial Engineering.
Love, R., & Wong, J. (1976). On solving a one-dimensional space allocation problem with integer programming. INFOR: Information Systems and Operational Research, 14(2), 139-143.
Maadi, M., Javidnia, M., & Ghasemi, M. (2016). Applications of two new algorithms of cuckoo optimization (CO) and forest optimization (FO) for solving single row facility layout problem (SRFLP). Journal of Artificial Intelligence and Data Mining, 4(1), 35-48.
Murray, C. C., Smith, A. E., & Zhang, Z. (2013). An efficient local search heuristic for the double row layout problem with asymmetric material flow. International Journal of Production Research, 51(20), 6129-6139.
Orand, S. M., Mirzazadeh, A., Ahmadzadeh, F., & Talebloo, F. (2015). Optimization of the inflationary inventory control model under stochastic conditions with Simpson Approximation: Particle swarm optimization approach. Iranian Journal of Management Studies, 8(2), 203.
Ozcelik, F. (2012). A hybrid genetic algorithm for the single row layout problem. International Journal of Production Research, 50(20), 5872-5886.
Palubeckis, G. (2015). Fast local search for single row facility layout. European Journal of Operational research, 246(3), 800-814.
Palubeckis, G. (2017). Single row facility layout using multi-start simulated annealing. Computers & Industrial Engineering, 103, 1-16.
Phadke, M. S. (1989). Quality Engineering Using Robust Design. NJ, US: Prentice Hall.
Picard, J.-C., & Queyranne, M. (1981). On the one-dimensional space allocation problem. Operations Research, 29(2), 371-391.
Romero, D., & Sánchez-Flores, A. (1990). Methods for the one-dimensional space allocation problem. Computers & Operations Research, 17(5), 465-473.
Samarghandi, H., & Eshghi, K. (2010). An efficient tabu algorithm for the single row facility layout problem. European Journal of Operational Research, 205(1), 98-105.
Samarghandi, H., Taabayan, P., & Jahantigh, F. F. (2010). A particle swarm optimization for the single row facility layout problem. Computers & Industrial Engineering, 58(4), 529-534.
Satheesh Kumar, R., Asokan, P., Kumanan, S., & Varma, B. (2008). Scatter search algorithm for single row layout problem in FMS. Advances in Production Engineering & Management, 3, 193-204.
Simmons, D. M. (1969). One-dimensional space allocation: An ordering algorithm. Operations Research, 17(5), 812-826.
Solimanpur, M., Vrat, P., & Shankar, R. (2005). An ant algorithm for the single row layout problem in flexible manufacturing systems. Computers & Operations Research, 32(3), 583-598.
Tang, C.-Y., Wu, Y.-L., & Peng, C.-C. (2012). Fundamental matrix estimation by multiobjective genetic algorithm with Taguchi's method. Applied Soft Computing, 12(1), 553-558.
Teo, Y. T., & Ponnambalam, S. (2008). A hybrid ACO/PSO heuristic to solve single row layout problem. Proceedings from CASE 2008: 4th IEEE International Conference on the Automation Science and Engineering, Washington, DC.
Van Laarhoven, P. J., & Aarts, E. H. (1987). Simulated annealing: Theory and applications. NY: Springer, 7-15.
Yadegari, E., Najmi, H., Ghomi-Avili, M., & Zandieh, M. (2015). A flexible integrated forward/reverse logistics model with random path-based memetic algorithm. Iranian Journal of Management Studies, 8(2), 287.
Zareei, M., & Hassan-Pour, H. A. (2015). A multi-objective resource-constrained optimization of time-cost trade-off problems in scheduling project. Iranian Journal of Management Studies, 8(4), 653-685.
Zhang, Z., & Murray, C. C. (2012). A corrected formulation for the double row layout problem. International Journal of Production Research, 50(15), 4220-4223.
Zuo, X., Murray, C. C., & Smith, A. E. (2014). Solving an extended double row layout problem using multiobjective tabu search and linear programming. IEEE Transactions on Automation Science and Engineering, 11(4), 1122-1132.
Interdisciplinary Journal of Management Studies (Formerly known as Iranian Journal of Management Studies)
Volume 10, Issue 2
April 2017
Pages 467-498

Files

Share

How to cite

Statistics