SavedAdd your journal

Journals / International Advanced Researches and Engineering Journal / 2022 / Cilt: 6 - Sayı: 1

Job shop scheduling with genetic algorithm-based hyperheuristic approach

Canan Hazal Akarsu
Tarık Küçükdeniz
Pages
16–25
Publication Date
2022-10-19
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)

Computational experiments show that the proposed genetic algorithm-based hyperheuristic approach finds optimal results or produces better solutions than compared methods.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Job shop scheduling problems are NP-hard problems that have been studied extensively in the literature as well as in real-life.
📊
Key Findings & Data:It is crucial to use effective production scheduling methods to reduce costs and increase productivity.
💡
Conclusion & Impact:Computational experiments show that the proposed genetic algorithm-based hyperheuristic approach finds optimal results or produces better solutions than compared methods.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Dispatching rules · GA-based hyperheuristics · Genetic algorithms

Abstract

Job shop scheduling problems are NP-hard problems that have been studied extensively in the literature as well as in real-life. Many factories all over the world produce worth millions of dollars with job shop type production systems. It is crucial to use effective production scheduling methods to reduce costs and increase productivity. Hyperheuristics are fast-implementing, low-cost, and powerful enough to deal with different problems effectively since they need limited problem-specific information. In this paper, a genetic algorithm-based hyperheuristic (GAHH) approach is proposed for job shop scheduling problems. Twenty-six dispatching rules are used as low-level heuristics. We use a set of benchmark problems from OR-Library to test the proposed algorithm. The performance of the proposed approach is compared with genetic algorithm, simulating annealing, particle swarm optimization and some of dispatching rules. Computational experiments show that the proposed genetic algorithm-based hyperheuristic approach finds optimal results or produces better solutions than compared methods.

🔖

Cite This Article

Akarsu, C. H., Küçükdeniz, T. (2022). Job shop scheduling with genetic algorithm-based hyperheuristic approach. International Advanced Researches and Engineering Journal, Cilt: 6 - Sayı: 1, 16–25. https://ajindex.com/articles/539253

📄 Full Text PDF Viewer

📄

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

References (17)

  1. Potts, C. N. and V. A. Strusevich, Fifty years of scheduling: a survey of milestones. J. Oper. Res. Soc., 2009. 60(1): p. 41–68
  2. Jones, A., L. C. Rabelo, and A. T. Sharawi, Survey of job shop scheduling techniques, in Wiley encyclopedia of electrical and electronics engineering, 1999, Wiley Online Library
  3. Jain, A. S. and S. Meeran, Deterministic job-shop scheduling: Past, present and future. Eur. J. Oper. Res., 1999. 113(2): p. 390–434
  4. Johnson, S., Optimal two- and three-stage production schedules with setup times included. Nav. Res. Logist. Q., 1954. 1: p. 61–68
  5. Jackson, J., An extension of Johnson’s result on job-lot scheduling. Nav. Res. Logist. Q., 1956. 3(3): p. 201–204
  6. Roy, B. and B. Sussmann, Les problemes d’ordonnancement avec contraintes disjonctives. Note ds, 1964. 9
  7. Balas, E., Machine scheduling via disjunctive graphs: An implicit enumeration algorithm. Oper. Res.,1969. 17: p. 941–957
  8. Kovalev, M. Y., et al., Approximation scheduling algorithms: A survey. Optimization, 1989. 20(6): p. 859–878
  9. Sharma, P. and A. Jain, A review on job shop scheduling with setup times. Proc. Inst. Mech. Eng. Part B J. Eng. Manuf., 2016. 230(3): p. 517–533
  10. Jones, D. F., S. K. Mirrazavi, and M. Tamiz, Multi-objective meta-heuristics: An overview of the current state-of-the-art. Eur. J. Oper. Res., 2002. 137(1): p. 1–9
  11. Fan, H. L., et al., Survey of the selection and evaluation for dispatching rules in dynamic job shop scheduling problem, in 2015 Chinese Automation Congress (CAC), 2015. p. 1926–193
  12. Chakhlevitch, K. and P. Cowling, Hyperheuristics: Recent developments in Adaptive and Multilevel Metaheuristics, 2008, Springer. p. 3–29
  13. Burke, E. K., et al., A classification of hyper-heuristic approaches, in Handbook of Metaheuristics, 2010, Springer. p. 449–468
  14. Cowling, P., G. Kendall, and E. Soubeiga, A hyper heuristic approach to scheduling a sales summit, in International conference on the practice and theory of automated timetabling, 2020. p.176-190
  15. Hunt, R., M. Johnston, and M. Zhang, Evolving machine-specific dispatching rules for a two-machine job shop using genetic programming, in 2014 IEEE Congress on Evolutionary Computation (CEC), 2014. p. 618–625
  16. Nguyen, S., et al., Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. IEEE Trans. Evol. Comput., 2014. 18(2): p. 193–208
  17. Sim, K. and E. Hart, A novel heuristic