Job shop scheduling with genetic algorithm-based hyperheuristic approach

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.

Keywords

• Dispatching rules
• GA-based hyperheuristics
• Genetic algorithms
• Hyperheuristics
• Job shop scheduling

References

1. 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. 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. 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. 4. Johnson, S., Optimal two- and three-stage production schedules with setup times included. Nav. Res. Logist. Q., 1954. 1: p. 61–68.
5. 5. Jackson, J., An extension of Johnson’s result on job-lot scheduling. Nav. Res. Logist. Q., 1956. 3(3): p. 201–204.
6. 6. Roy, B. and B. Sussmann, Les problemes d’ordonnancement avec contraintes disjonctives. Note ds, 1964. 9.
7. 7. Balas, E., Machine scheduling via disjunctive graphs: An implicit enumeration algorithm. Oper. Res.,1969. 17: p. 941–957.
8. 8. Kovalev, M. Y., et al., Approximation scheduling algorithms: A survey. Optimization, 1989. 20(6): p. 859–878.

9. 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. 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. 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. 12. Chakhlevitch, K. and P. Cowling, Hyperheuristics: Recent developments in Adaptive and Multilevel Metaheuristics, 2008, Springer. p. 3–29.
13. 13. Burke, E. K., et al., A classification of hyper-heuristic approaches, in Handbook of Metaheuristics, 2010, Springer. p. 449–468.
14. 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. 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. 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. 17. Sim, K. and E. Hart, A novel heuristic generator for JSSP using a tree-based representation of dispatching rules, in Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, 2015. p. 1485–1486.
18. 18. Hart, E. and K. Sim, A hyper-heuristic ensemble method for static job-shop scheduling. Evol. Comput., 2016. 24(4): p. 609–635.
19. 19. Branke, J., et al., Automated design of production scheduling heuristics: A review. IEEE Trans. Evol. Comput., 2016. 20(1): p. 110–124.
20. 20. Yenisey, M. M. and M. Şevkli, Atölye tipi çizelgeleme problemleri için parçacık sürü optimizasyonu yöntemi. İTÜDERGİSİ/d, 2006. 5(2): p. 58–68.
21. 21. Pinedo, M. L., Scheduling: Theory, algorithms and systems. 2008, New Jersey: Prentice-Hall.
22. 22. Lenstra, J. K. and A. R. Kan, Computational complexity of discrete optimization problems. Ann. Discret. Math., 1979. 4: p. 121–140.
23. 23. Mellor, P., A Review of Job Shop Scheduling. J. Oper. Res. Soc., 1966. 17(2): p. 161–171.
24. 24. Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with application to biology, control, and artificial intelligence. 1975, Ann Arbor (MI): The University of Michigan Press.
25. 25. Park, B. J., H. R. Choi, and H. S. Kim, A hybrid genetic algorithm for the job shop scheduling problems. Comput. Ind. Eng., 2003. 45(4): p. 597–613.
26. 26. Dao, S. D., K. Abhary, and R. Marian, A bibliometric analysis of Genetic Algorithms throughout the history. Comput. Ind. Eng., 2017. 110: p. 395–403.
27. 27. Davis, L., Job shop scheduling with genetic algorithms, in Proceedings of an international conference on genetic algorithms and their applications, 1985.
28. 28. Gen, M. and R. Cheng, Genetic algorithms and engineering optimization. 2000, John Wiley & Sons.
29. 29. Zhong, T. X. and J. C. Chen, A hybrid-coded genetic algorithm based optimisation of non-productive paths in CNC machining. Int. J. Adv. Manuf. Technol., 2002. 20(3): p. 163–168.
30. 30. Wang, Y. M., H. L. Yin, and J. Wang, Genetic algorithm with new encoding scheme for job shop scheduling. Int. J. Adv. Manuf. Technol., 2009. 44(9–10): p. 977–984.
31. 31. Dao, S. D., K. Abhary, and R. Marian, Optimisation of partner selection and collaborative transportation scheduling in virtual enterprises using GA. Expert Syst. Appl., 2014. 41(15): p. 6701–6717.
32. 32. Qing-dao-er-ji, R. and Y. Wang, A new hybrid genetic algorithm for job shop scheduling problem. Comput. Oper. Res., 2012. 39(10): p. 2291–2299.
33. 33. Tang, P.-H. and M.-H. Tseng, Adaptive directed mutation for real-coded genetic algorithms. Appl. Soft Comput., 2013. 13(1): p. 600–614.
34. 34. Wu, X., et al., A genetic algorithm for cellular manufacturing design and layout. Eur. J. Oper. Res., 2007. 181(1): p. 156–167.
35. 35. Šetinc, M., M. Gradišar, and L. Tomat, Optimization of a highway project planning using a modified genetic algorithm. Optimization, 2015. 64(3): p. 687–707.
36. 36. Cheung, W. and H. Zhou, Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Ann. Oper. Res., 2001. 107(1–4): p. 65–81.
37. 37. Wang, L. and D. Zheng, An effective hybrid optimization strategy for job-shop scheduling problems. Comput. Oper. Res., 2001. 28(6): p. 585–596.
38. 38. Zhou, H., Y. Feng, and L. Han, The hybrid heuristic genetic algorithm for job shop scheduling. Comput. Ind. Eng., 2001. 40(3): p. 191–200.
39. 39. Gao, J., L. Sun, and M. Gen, A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput. Oper. Res., 2008. 35(9): p. 2892–2907.
40. 40. Gere, W. S., Heuristics in job shop scheduling. Manage. Sci., 1966. 13(3): p. 167–190.
41. 41. Panwalkar, S. S. and W. Iskander, A survey of scheduling rules. Oper. Res., 1977. 25(1): p. 45–61.
42. 42. Burke, E. et al., Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc., 2013. 64(12): p. 1695–1724.
43. 43. Dorndorf, U. and E. Pesch, Evolution based learning in a job shop scheduling environment. Comput. Oper. Res., 1995. 22(1): p. 25–40.
44. 44. Hart, E. and P. Ross, A heuristic combination method for solving job-shop scheduling problems, in International Conference on Parallel Problem Solving from Nature, 1998. p. 845–854.
45. 45. Fang, H., P. Ross, and D. Corne, A promising hybrid GA/heuristic approach for open-shop scheduling problems, in Proceedings of 11th European Conference on Artificial Intelligence, 1994. p. 590–594.
46. 46. Norenkov, I. P. and E. D. Goodman, Solving scheduling problems via evolutionary methods for rule sequence optimization, in Soft computing in engineering design and manufacturing, 1998, Springer. p. 350–355.
47. 47. Vázquez-Rodríguez, J. A. and S. Petrovic, A new dispatching rule based genetic algorithm for the multi-objective job shop problem. J. Heuristics, 2010. 16(6): p. 771–793.
48. 48. Hart, E., P. Ross, and J. A. D. Nelson, Scheduling chicken catching – An investigation into the success of a genetic algorithm on a real-world scheduling problem. Ann. Oper. Res., 1999. 92: p. 363–380.
49. 49. Cowling, P., G. Kendall, and L. Han, An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem, in the IEEE Congress on Evolutionary Computation (IEEE CEC02), 2002.
50. 50. Ahmed Bacha, S. Z., et al., A New Hyper-Heuristic to Generate Effective Instance GA for the Permutation Flow Shop Problem. Procedia Comput. Sci., 2019. 159: p. 1365–1374.
51. 51. Ross, P., et al., Learning a procedure that can solve hard bin-packing problems: A new ga-based approach to hyper-heuristics, in Genetic and Evolutionary Computation Conference, 2003. p. 1295–1306.
52. 52. Thomas, J. and N. S. Chaudhari, Design of efficient packing system using genetic algorithm based on hyper heuristic approach. Adv. Eng. Softw., 2014. 73: p. 45–52.
53. 53. Zhang, S., Y. Xu, and W. Zhang, Multitask-oriented manufacturing service composition in an uncertain environment using a hyper-heuristic algorithm. J. Manuf. Syst., 2021. 60: p. 138–151.
54. 54. Pang, L. M., H. Ishibuchi, and K. Shang, Using a Genetic Algorithm-based Hyper-heuristic to Tune MOEA/D for a Set of Various Test Problems, in IEEE Congress on Evolutionary Computation (CEC), 2021. p. 1486–1494.
55. 55. Haupt, R., A survey of priority rule-based scheduling. OR Spectr., 1989. 11(1): p. 3–16.
56. 56. Cheng, R., M. Gen, and Y. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation. Comput. Ind. Eng., 1996. 30(4): p. 983–997.
57. 57. Sastry, K., D. E. Goldberg, and G. Kendall, Genetic algorithms, in Search methodologies, 2005, Springer. p. 97–125.
58. 58. Beasley, J. E., OR-Library, 1990. [cited 2017 20 Nov]; Available from: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html.
59. 59. Jayamohan, M. S. and C. Rajendran, New dispatching rules for shop scheduling : A step forward. Int. J. Prod. Res., 2000. 38(3): p. 563–586.
60. 60. Rajendran, C. and O. Holthaus, Efficient jobshop dispatching rules: Further developments. Prod. Plan. Control Manag. Oper., 2000. 11(2): p. 171–178.