SavedAdd your journal

Journals / Gazi University Journal of Science / 2022 / Cilt: 35 - Sayı: 1

Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems

Oğuzhan Ahmet ARIK
Pages
92–111
Publication Date
2022-11-08
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:In this paper, permutation flow shop scheduling problems (PFSS) are investigated with a genetic algorithm.
📊
Key Findings & Data:The most common performance criterion in the literature is the makespan for permutation scheduling problems.
💡
Conclusion & Impact: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.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Genetic algorithm · Permutation flow shop · Scheduling

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.

🔖

Cite This Article

ARIK, O. A. (2022). Genetic Algorithm Application for Permutation Flow Shop Scheduling Problems. Gazi University Journal of Science, Cilt: 35 - Sayı: 1, 92–111. https://ajindex.com/articles/650862

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (14)

  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,” Eur. J. Oper. Res., 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,” Int. J. Prod. Res., 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,” J. Oper. Res. Soc., 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,” Eur. J. Oper. Res., 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,” Eur. J. Oper. Res., 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,” Appl. Soft Comput. J., 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 Comput., 18(11): 2271–2282, (2014)
  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. 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. Ahmadizar, F., “A new ant colony algorithm for makespan minimization in permutation flow shops,” Comput. Ind. Eng., 63(2): 355–361, (2012)
  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. 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., 1