Minimizing Makespan in a Permutation Flow Shop Environment: Comparison of Scatter Search, Genetic Algorithm and Greedy Randomized Adaptive Search Procedures

Abstract

Solving scheduling problems enables more efficient use of production capacity. It involves defining the sequence of operations, determining the capacity of resources, and balancing workloads. Different methods, especially metaheuristics, have been used to solve these problems. This study presents the application of Scatter Search (SS), Genetic Algorithm (GA), and Greedy Randomized Adaptive Search Procedures (GRASP) for minimizing makespan in a permutation flow shop environment. In this study, the performances of these methods are compared through various test problems in the literature and a real-life problem of a company operating in the automotive sector. Study comprises 48 jobs that must be planned within a day for eight consecutive operations. In cellular manufacturing, the sequence in which each job is processed in eight operations is the same. In solving permutation flow shop scheduling problems (PFSP), one of the NP-hard problems, meta-heuristic methods are widely applied due to their successful results. From this point of view, SS, GA, and GRASP are employed in this study, and their performances are compared.

Keywords

• Scheduling
• Permutation Flow Shop Scheduling Problem
• Makespan
• Scatter Search
• Genetic Algorithm
• GRASP

References

1. Allahverdi, A. (2003). The two and m-machine flow shop scheduling problem with bi-criteria of makespan and mean flow time. European Journal of Operational Research, 147: 373–396.
2. Arroyo, J.E.C. and de Souza Pereira, A. A. (2011). A GRASP heuristic for the multi-objective permutation flowshop scheduling problem. International Journal of Advanced Manufacturing Technology, 55(5): 741-753.
3. Babaei, M., Mohammadi, M., Ghomi, S. M. T. F. and Sobhanallahi, M. A. (2012). Two parameter-tuned metaheuristic algorithms for the multi-level lot sizing and scheduling problem. International Journal of Industrial Engineering Computations, 3(5): 751–766.
4. Bautista, J., Cano, A., Companys, R., & Ribas, I. (2012). Solving the Fm∣ block∣ Cmax problem using bounded dynamic programming. Engineering Applications of Artificial Intelligence, 25(6), 1235-1245.
5. Ben-Daya, M. and Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, l09, 88-95.
6. Borovska, P. (2006, June). Solving the travelling salesman problem in parallel by genetic algorithm on multicomputer cluster. In International Conference on Computer Systems and Technologies-CompSysTech (Vol. 6, No. 2.11).
7. Bozejko, W. and Wodecki, M. (2008). Parallel Scatter Search Algorithm for the Flow Shop Sequencing Problem. Wyrzykowski, R., Dongarra, J., Karczewski K. and Wasniewski, J. (Eds.). Parallel Processing and Applied Mathematics (pp.180-188). Springer-Verlag Berlin Heidelberg.
8. Campbell, H. G., Dudek, R. A. and Smith, M. L. (1970). A Heuristic Algorithm for the n job, m Machine Sequencing Problem. Management Science, 16(10): B630-B637.

9. Çiçekli, U. G. and Bozkurt, S. (2015). Permütasyon Akış Tipi Çizelgeleme Probleminin Dağınık Arama İle Optimizasyonu. 15. Üretim Araştırmaları Sempozyumu, pp: 443-452, İzmir, 14-16 Ekim, 2015.
10. Çiçekli, U. G. and Kaymaz, Y. (2016). A Genetic Algorithm For The Allocation of Dangerous Goods Containers In A Storage Yard For Freight Villages and Dry Ports. Gazi University Journal of Faculty of Economics and Administrative Sciences, 18(1): 264-282.
11. Feo, T. and Resende, M.G.C. (1995). Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6: 109–134.
12. Festa, P. and Resende, M. G. (2002). GRASP: An annotated bibliography. In Essays and surveys in metaheuristics (pp. 325-367). Springer, Boston, MA.
13. Goldberg D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, USA.
14. Gupta, J. (1972). Heuristic algorithms for multistage flowshop scheduling problem. AIIE Transactions, 4(1):11–18.
15. Haq, A..N., Saravanan, M., Vivekraj A. R. and Prasad T. (2007). A Scatter Search Approach for General Flowshop Scheduling Problem. The International Journal of Advanced Manufacturing Technology, 31(7-8): 731–736.
16. Huang, M. W., Hsieh, C. C. and Arora, J. S. (1997). A genetic algorithm for sequencing type problems in engineering design. International Journal for Numerical Methods in Engineering, 40(17), 3105-3115.
17. Johnson, S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1): 61-68.
18. Shahul Hamid Khan, B. S. H., Prabhaharan, G. and Asokan, P. (2007). A Grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. International Journal of Computer Mathematics, 84(12): 1731-1741.
19. Kocamaz, M. and Çiçekli, G. (2010). Paralel Makinaların Genetik Algoritma İle Çizelgelenmesinde Mutasyon Oranının Etkinliği [Efficiency of Mutation Rate for Parallel Machine Scheduling with Genetic Algorithm]. Ege Academic Review, 10(1): 199-210.
20. Kocamaz, M., Cicekli, U. G. and Soyuer, H. (2009, July). A developed encoding method for parallel machine scheduling with permutation genetic algorithm. In European and Mediterranean Conference on Information Systems EMCIS.
21. Laguna, M. and Marti, R. (2003). Scatter search: methodology and implementations in C. Springer Science & Business Media.
22. Michalewicz, Z. (1992). Genetic algorithms + data structures = evolution programs, Berlin: Springer.
23. Molina-Sánchez, L. and González-Neira, E. (2016). GRASP to minimize total weighted tardiness in a permutation flow shop environment. International Journal of Industrial Engineering Computations, 7(1), 161-176.
24. Nawaz, M., Enscore Jr., E.E. and Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11(1): 91–95.
25. Nowicki, E. and Smutnicki, C. (2006). Some aspects of scatter search in the flow-shop problem. European Journal of Operational Research, 169 (2): 654–666.
26. Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & operations research, 22(1), 5-13.
27. Resende, M. G. and Ribeiro, C. C. (2014). GRASP: Greedy randomized adaptive search procedures. In Search methodologies (pp. 287-312). Springer, Boston, MA.
28. Ruiz, R. and Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165: 479–494.
29. Ruiz, R., Maroto, C. and Alcara, J. (2005). Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. European Journal of Operational Research, 165: 34–54.
30. Schaller, J. and Valente, J. M.S. (2013). A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. International Journal of Production Research, 51(3): 772-779.
31. Shahsavari Pour, N., Tavakkoli-Moghaddam, R. and Asadi, H. (2013). Optimizing a multi-objectives flow shop scheduling problem by a novel genetic algorithm. International Journal of Industrial Engineering Computations, 4(3): 345–354.
32. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
33. Vallada, E. and Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega, 38(1-2): 57-67.
34. Widmer, M., Hertz, A. and Costa, D. (2008). Metaheuristics and Scheduling, in Production Scheduling (eds P. Lopez and F. Roubellat), ISTE, London, UK. doi: 10.1002/9780470611050.ch3
35. Yenisey, M. M., & Yagmahan, B. (2014). Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45, 119-135.
36. Zhang, L. and Wu, J. (2014). A PSO-Based Hybrid Metaheuristic for Permutation Flowshop Scheduling Problems. Hindawi Publishing Corporation The Scientific World Journal, 1-8.