Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems

Arık, Oğuzhan Ahmet

doi:10.35378/gujs.682388

Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems

Oğuzhan Ahmet ARIK (Nuh Naci Yazgan Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Kayseri, Türkiye)

Gazi University Journal of Science

8 5

Yıl: 2022 Cilt: 35 Sayı: 1 Sayfa Aralığı: 92 - 111 Metin Dili: İngilizce DOI: 10.35378/gujs.682388 İndeks Tarihi: 08-11-2022

Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems

Öz:

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.

Anahtar Kelime: Genetic algorithm Permutation flow shop Scheduling Makespans

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[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] Taillard, E., “Benchmarks for basic scheduling problems”, European Journal of Operational Research, 64(2): 278-285, (1993).
[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] Hejazi, S. R., Saghafian, S., “Flowshop-scheduling problems with makespan criterion: A review”, International Journal of Production Research, 43(14): 2895–2929, (2005).
[5] Framinan, J. M., Gupta, J. N. D., Leisten, R., “A review and classification of heuristics for permutation flow-shop scheduling with makespan objective”, Journal of the Operational Research Society, 55(12): 1243–1255, (2004).
[6] Framinan, J. M., Leisten, R., Ruiz-Usano, R., “Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation”, European Journal of Operational Research, 141(3): 559–569, (2002).
[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”, European Journal of Operational Research, 177(3): 1930–1947, (2007).
[8] Wang, X., Tang, L., “A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking”, Applied Soft Computing, 12(2): 652–662, (2012).
[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 Computing, 18(11): 2271–2282, (2014).
[10] Li, D., Deng, N., “Solving Permutation Flow Shop Scheduling Problem with a cooperative multi- swarm PSO algorithm”, Journal of Information and Computational Science, 9(4): 977–987, (2012).
[11] Rajendran, C., Ziegler, H., “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs”, European Journal of Operational Research, 155(2): 426–438, (2004).
[12] Ahmadizar, F., “A new ant colony algorithm for makespan minimization in permutation flow shops”, Computers & Industrial Engineering, 63(2): 355–361, (2012).
[13] Ruiz, R., Stützle, T., “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem”, European Journal of Operational Research, 177(3): 2033–2049, (2007).
[14] Ruiz, R., Stützle, T., “An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives”, European Journal of Operational Research, 187(3): 1143–1159, (2008).
[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] Minella, G., Ruiz, R., Ciavotta, M., “Restarted Iterated Pareto Greedy algorithm for multi- objective flowshop scheduling problems”, Computers & Operations Research, 38(11): 1521– 1533, (2011).
[17] Grabowski, J., Wodecki, M., “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion”, Computers & Operations Research, 31(11): 1891–1909, (2004).
[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”, European Journal of Operational Research, 167(3): 772–795, (2005).
[19] Grabowski, J., Pempera, J., “The permutation flow shop problem with blocking. A tabu search approach”, Omega, 35(3): 302–311, (2007).
[20] Zobolas, G. I., Tarantilis, C. D., Ioannou, G., “Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm”, Computers & Operations Research, 36(4): 1249–1267, (2009).
[21] Tseng, L.-Y., Lin, Y.-T., “A hybrid genetic local search algorithm for the permutation flowshop scheduling problem”, European Journal of Operational Research, 198(1): 84–92, (2009).
[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”, International Journal of Advanced Manufacturing Technology, 27(7–8): 804–815, (2006).
[23] Chen, S.-H., Chang, P.-C., Cheng, T. C. E., Zhang, Q., “A Self-guided Genetic Algorithm for permutation flowshop scheduling problems”, Computers & Operations Research, 39(7): 1450– 1457, (2012).
[24] Haq, A. N., Ramanan, T. R., Shashikant, K. S., Sridharan, R., “A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling”, International Journal of Production Research, 48(14): 4217–4231, (2010).
[25] Nagano, M. S., Ruiz, R., Lorena, L. A. N., “A Constructive Genetic Algorithm for permutation flowshop scheduling”, Computers and Industrial Engineering, 55(1): 195–207, (2008).
[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] Dong, X., Huang, H., Chen, P., “An improved NEH-based heuristic for the permutation flowshop problem”, Computers & Operations Research, 35(12): 3962–3968, (2008).
[28] Kalczynski, P. J., Kamburowski, J., “An improved NEH heuristic to minimize makespan in permutation flow shops”, Computers & Operations Research, 35(9): 3001–3008, (2008).
[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”, Journal of the Operational Research Society, 62(2): 381–396, (2011).
[30] Dubois-Lacoste, J., Lpez-Ibez, M., Sttzle, T., “A hybrid TP+PLS algorithm for bi-objective flow- shop scheduling problems”, Computers & Operations Research, 38(8): 1219–1236, (2011).
[31] Chiang, T.-C., Cheng, H.-C., Fu, L.-C., “NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems”, Expert Systems with Applications, 38(5): 5986–5999, (2011).
[32] Zheng, T., Yamashiro, M., “Solving flow shop scheduling problems by quantum differential evolutionary algorithm”, The International Journal of Advanced Manufacturing Technology, 49(5–8): 643–662, (2010).
[33] Vallada, E., Ruiz, R., “Cooperative metaheuristics for the permutation flowshop scheduling problem”, European Journal of Operational Research, 193(2): 365–376, (2009).
[34] Lin, S.-W., Ying, K.-C., “Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm”, Computers & Operations Research, 40(6): 1625–1647, (2013).
[35] Ribas, I., Companys, R., Tort-Martorell, X., “Comparing three-step heuristics for the permutation flow shop problem”, Computers & Operations Research, 37(12): 2062–2070, (2010).
[36] Laha, D., Chakraborty, U. K., “An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling”, The International Journal of Advanced Manufacturing Technology, 44(5–6): 559–569, (2009).
[37] Saravanan, M., Noorul, H. A., Vivekraj, A. R., Prasad, T., “Performance evaluation of the scatter search method for permutation flowshop sequencing problems”, The International Journal of Advanced Manufacturing Technology, 37(11–12): 1200–1208, (2008).
[38] Tzeng, Y.-R., Chen, C.-L., “A hybrid EDA with ACS for solving permutation flow shop scheduling”, International Journal of Advanced Manufacturing Technology, 60(9–12): 1139– 1147, (2012).
[39] Dasgupta, P., Das, S., “A discrete inter-species cuckoo search for flowshop scheduling problems”, Computers & Operations Research, 60: 111–120, (2015).
[40] Chen, C.-L., Tzeng, Y.-R., Chen, C.-L., “A new heuristic based on local best solution for permutation flow shop scheduling”, Applied Soft Computing, 29: 75–81, (2015).
[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”, Computers & Operations Research, 52: 260–268, (2014).
[42] Rajendran, S., Rajendran, C., Leisten, R., “Heuristic rules for tie-breaking in the implementation of the NEH heuristic for permutation flow-shop scheduling”, International Journal of Operational Research, 28(1): 87–97, (2017).
[43] Fernandez-Viagas, V., Framinan, J. M., “On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem”, Computers & Operations Research, 45: 60–67, (2014).
[44] Dubois-Lacoste, J., Pagnozzi, F., Stützle, T., “An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem”, Computers & Operations Research, 81: 160–166, (2017).
[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”, Future Generation Computer Systems, 85: 129–145, (2018).
[46] Benavides, A. J., Ritt, M., “Fast heuristics for minimizing the makespan in non-permutation flow shops”, Computers & Operations Research, 100: 230–243, (2018).
[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”, International Journal of Production Research, 58(19): 5945-5963, (2020).
[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] Fernandez-Viagas, V., Framinan, J. M., “A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective”, Computers & Operations Research, 112, (2019).
[50] Arık, O. A., “Artificial bee colony algorithm including some components of iterated greedy algorithm for permutation flow shop scheduling problems”, Neural Computing and Applications, 33: 3469–3486, (2021).
[51] Gmys, J., Mezmaz, M., Melab, N., Tuyttens, D., “A computationally efficient Branch-and- Bound algorithm for the permutation flow-shop scheduling problem”, European Journal of Operational Research, 284(3): 814–833, (2020).
[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 Computing, 25(2): 1501–1518, (2021).
[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

APA	Arık O (2022). Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. , 92 - 111. 10.35378/gujs.682388
Chicago	Arık Oğuzhan Ahmet Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. (2022): 92 - 111. 10.35378/gujs.682388
MLA	Arık Oğuzhan Ahmet Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. , 2022, ss.92 - 111. 10.35378/gujs.682388
AMA	Arık O Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. . 2022; 92 - 111. 10.35378/gujs.682388
Vancouver	Arık O Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. . 2022; 92 - 111. 10.35378/gujs.682388
IEEE	Arık O "Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems." , ss.92 - 111, 2022. 10.35378/gujs.682388
ISNAD	Arık, Oğuzhan Ahmet. "Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems". (2022), 92-111. https://doi.org/10.35378/gujs.682388

APA	Arık O (2022). Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science, 35(1), 92 - 111. 10.35378/gujs.682388
Chicago	Arık Oğuzhan Ahmet Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science 35, no.1 (2022): 92 - 111. 10.35378/gujs.682388
MLA	Arık Oğuzhan Ahmet Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science, vol.35, no.1, 2022, ss.92 - 111. 10.35378/gujs.682388
AMA	Arık O Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science. 2022; 35(1): 92 - 111. 10.35378/gujs.682388
Vancouver	Arık O Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science. 2022; 35(1): 92 - 111. 10.35378/gujs.682388
IEEE	Arık O "Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems." Gazi University Journal of Science, 35, ss.92 - 111, 2022. 10.35378/gujs.682388
ISNAD	Arık, Oğuzhan Ahmet. "Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems". Gazi University Journal of Science 35/1 (2022), 92-111. https://doi.org/10.35378/gujs.682388