Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems

Abstract

In this paper, permutation flow shop scheduling problems (PFSS) are investigated with a genetic algorithm. PFSS problem is a special type of flow shop scheduling problem. In a PFSS problem, there are n jobs to be processed on m machines in series. Each job has to follow the same machine order and each machine must process jobs in the same job order. The most common performance criterion in the literature is the makespan for permutation scheduling problems. In this paper, a genetic algorithm is applied to minimize the makespan. Taillard’s instances including 20, 50, and 100 jobs with 5, 10, and 20 machines are used to define the efficiency of the proposed GA by considering lower bounds or optimal makespan values of instances. Furthermore, a sensitivity analysis is made for the parameters of the proposed GA and the sensitivity analysis shows that crossover probability does not affect solution quality and elapsed time. Supplementary to the parameter tuning of the proposed GA, we compare our GA with an existing GA in the literature for PFSS problems and our experimental study reveals that our proposed and well-tuned GA outperforms the existing GA for PFSS problems when the objective is to minimize the makespan.

Keywords

• Genetic algorithm
• Permutation flow shop
• Scheduling
• Makespans

References

1. [1] Nawaz, M., Enscore Jr., E. E., Ham, I., “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, 11(1): 91–95, (1983).
2. [2] Taillard, E., “Benchmarks for basic scheduling problems,” Eur. J. Oper. Res., 64(2): 278-285, (1993).
3. [3] Yenisey, M. M., Yagmahan, B., “Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends,” Omega, 45: 119–135, (2014).
4. [4] Hejazi, S.R., Saghafian, S., “Flowshop-scheduling problems with makespan criterion: A review,” Int. J. Prod. Res., 43(14): 2895–2929, (2005).
5. [5] Framinan, J. M., Gupta, J. N. D., Leisten, R., “A review and classification of heuristics for permutation flow-shop scheduling with makespan objective,” J. Oper. Res. Soc., 55(12): 1243–1255, (2004).
6. [6] Framinan, J. M., Leisten, R., Ruiz-Usano, R., “Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation,” Eur. J. Oper. Res., 141(3): 559–569, (2002).
7. [7] Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., Gencyilmaz, G., “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” Eur. J. Oper. Res., 177(3): 1930–1947, (2007).
8. [8] Wang, X., Tang, L., “A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking,” Appl. Soft Comput. J., 12(2): 652–662, (2012).

9. [9] Chen, C. L., Huang, S. Y., Tzeng, Y. R., Chen, C.-L., “A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem,” Soft Comput., 18(11): 2271–2282, (2014).
10. [10] Li, D., Deng, N., “Solving Permutation Flow Shop Scheduling Problem with a cooperative multi-swarm PSO algorithm,” J. Inf. Comput. Sci., 9(4): 977–987, (2012).
11. [11] Rajendran, C., Ziegler, H., “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,” Eur. J. Oper. Res., 155(2): 426–438, (2004).
12. [12] Ahmadizar, F., “A new ant colony algorithm for makespan minimization in permutation flow shops,” Comput. Ind. Eng., 63(2): 355–361, (2012).
13. [13] Ruiz, R., Stützle, T., “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., 177(3): 2033–2049, (2007).
14. [14] Ruiz, R., Stützle, T., “An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives,” Eur. J. Oper. Res., 187(3): 1143–1159, (2008).
15. [15] Ribas, I., Companys, R., Tort-Martorell, X., “An iterated greedy algorithm for the flowshop scheduling problem with blocking,” Omega, 39(3): 293–301, (2011).
16. [16] Minella, G., Ruiz, R., Ciavotta, M., “Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems,” Comput. Oper. Res., 38(11): 1521–1533, (2011).
17. [17] Grabowski, J., Wodecki, M., “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion,” Comput. Oper. Res., 31(11): 1891–1909, (2004).
18. [18] Varadharajan, T. K., Rajendran, C., “A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs,” Eur. J. Oper. Res., 167(3): 772–795, (2005).
19. [19] Grabowski, J., Pempera, J., “The permutation flow shop problem with blocking. A tabu search approach,” Omega, 35(3): 302–311, (2007).
20. [20] Zobolas, G. I., Tarantilis, C. D., Ioannou, G., “Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm,” Comput. Oper. Res., 36(4): 1249–1267, (2009).
21. [21] Tseng, L.-Y., Lin, Y.-T., “A hybrid genetic local search algorithm for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., 198(1): 84–92, (2009).
22. [22] Pasupathy, T., Rajendran, C., Suresh, R. K., “A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs,” Int. J. Adv. Manuf. Technol., 27(7–8): 804–815, (2006).
23. [23] Chen, S.-H., Chang, P.-C., Cheng, T. C. E., Zhang, Q., “A Self-guided Genetic Algorithm for permutation flowshop scheduling problems,” Comput. Oper. Res., 39(7): 1450–1457, (2012).
24. [24] Haq, A. N., Ramanan, T. R., Shashikant, K. S., Sridharan, R., “A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling,” Int. J. Prod. Res., 48(14): 4217–4231, (2010).
25. [25] Nagano, M. S., Ruiz, R., Lorena, L. A. N., “A Constructive Genetic Algorithm for permutation flowshop scheduling,” Comput. Ind. Eng., 55(1): 195–207, (2008).
26. [26] Rad, S. F., Ruiz, R., Boroojerdian, N., “New high performing heuristics for minimizing makespan in permutation flowshops,” Omega, 37(2): 331–345, (2009).
27. [27] Dong, X., Huang, H., Chen, P., “An improved NEH-based heuristic for the permutation flowshop problem,” Comput. Oper. Res., 35(12): 3962–3968, (2008).
28. [28] Kalczynski, P. J., Kamburowski, J., “An improved NEH heuristic to minimize makespan in permutation flow shops,” Comput. Oper. Res., 35(9): 3001–3008, (2008).
29. [29] Vázquez-Rodríguez, J. A., Ochoa, G., “On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming,” J. Oper. Res. Soc., 62(2): 381–396, (2011).
30. [30] Dubois-Lacoste, J., Lpez-Ibez, M., Sttzle, T., “A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems,” Comput. Oper. Res., 38(8): 1219–1236, (2011).
31. [31] Chiang, T.-C., Cheng, H.-C., Fu, L.-C., “NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems,” Expert Syst. Appl., 38(5): 5986–5999, (2011).
32. [32] Zheng, T., Yamashiro, M., “Solving flow shop scheduling problems by quantum differential evolutionary algorithm,” Int. J. Adv. Manuf. Technol., 49(5–8): 643–662, (2010).
33. [33] Vallada, E., Ruiz, R., “Cooperative metaheuristics for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., 193(2): 365–376, (2009).
34. [34] Lin, S.-W., Ying, K.-C., “Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm,” Comput. Oper. Res., 40(6): 1625–1647, (2013).
35. [35] Ribas, I., Companys, R., Tort-Martorell, X., “Comparing three-step heuristics for the permutation flow shop problem,” Comput. Oper. Res., 37(12): 2062–2070, (2010).
36. [36] Laha, D., Chakraborty, U. K., “An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling,” Int. J. Adv. Manuf. Technol., 44(5–6): 559–569, (2009).
37. [37] Saravanan, M., Noorul, H.A., Vivekraj, A. R., Prasad, T., “Performance evaluation of the scatter search method for permutation flowshop sequencing problems,” Int. J. Adv. Manuf. Technol., 37(11–12): 1200–1208, (2008).
38. [38] Tzeng, Y.-R., Chen, C.-L., “A hybrid EDA with ACS for solving permutation flow shop scheduling,” Int. J. Adv. Manuf. Technol., 60(9–12): 1139–1147, (2012).
39. [39] Dasgupta, P., Das, S., “A discrete inter-species cuckoo search for flowshop scheduling problems,” Comput. Oper. Res., 60: 111–120, (2015).
40. [40] Chen, C.-L., Tzeng, Y.-R., Chen, C.-L., “A new heuristic based on local best solution for permutation flow shop scheduling,” Appl. Soft Comput. J., 29: 75–81, (2015).
41. [41] Moslehi, G., Khorasanian, D., “A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion,” Comput. Oper. Res., 52: 260–268, (2014).
42. [42] Rajendran, S., Rajendran, C., Leisten, R., “Heuristic rules for tie-breaking in the implementation of the NEH heuristic for permutation flow-shop scheduling,” Int. J. Oper. Res., 28(1): 87–97, (2017).
43. [43] Fernandez-Viagas, V., Framinan, J. M., “On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem,” Comput. Oper. Res., 45: 60–67, (2014).
44. [44] Dubois-Lacoste, J., Pagnozzi, F., Stützle, T., “An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem,” Comput. Oper. Res., 81: 160–166, (2017).
45. [45] Abdel-Basset, M., Manogaran, G., El-Shahat, D., Mirjalili, S., “A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem,” Futur. Gener. Comput. Syst., 85: 129–145, (2018).
46. [46] Benavides, A. J., Ritt, M., “Fast heuristics for minimizing the makespan in non-permutation flow shops,” Comput. Oper. Res., 100:230–243, (2018).
47. [47] Chen, Z., Zheng, X., Zhou, S., Liu, C., Chen, H., “Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines,” Int. J. Prod. Res., 58(19): 5945-5963, (2020).
48. [48] Kizilay, D., Tasgetiren, M. F., Pan, Q.-K., Gao, L., “A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion,” Algorithms, 12:(5), (2019).
49. [49] Fernandez-Viagas, V., Framinan, J. M., “A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective,” Comput. Oper. Res., 112, (2019).
50. [50] Arık, O. A., “Artificial bee colony algorithm including some components of iterated greedy algorithm for permutation flow shop scheduling problems,” Neural Comput. Appl., 33: 3469–3486, (2021).
51. [51] Gmys, J., Mezmaz, M., Melab, N., Tuyttens, D., “A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem,” Eur. J. Oper. Res., 284(3): 814–833, (2020).
52. [52] Arık, O. A., “Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration,” Soft Comput., 25(2): 1501–1518, (2021).
53. [53] Taiilard, E., “Benchmarks for basic scheduling problems.” http://mistic.heig- vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/best_lb_up.txt. Access date: 30.03.2018