Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling. (English) Zbl 1518.90036
Summary: Dispatching rules represent a simple heuristic for finding good solutions for job shop scheduling problems. Due to their fast applicability and easy handling, they are often used in manufacturing companies to create appropriate production schedules. It has been shown that dispatching rules that are specifically designed for the requirements of a particular environment improve the performance of schedules. Hyper-heuristics based on genetic programming can be used for the automated generation of such dispatching rules. Evolutionary algorithms search the space of dispatching rule components for the most effective priority function to optimize the performance of the resulting schedule. Various studies have highlighted the advantages in the single-objective case, which made it possible to derive a large number of new dispatching rules that exceeded previous benchmark rules. Because it is usually necessary to consider more than one objective simultaneously to ensure effective creation of schedules, the need for a multi-objective optimization method arises. In this paper, we propose an interactive multi-objective optimization method, namely the reference point method, implemented in a hyper-heuristic genetic programming framework. A decision support system has also been developed and implemented in a web-based application to facilitate interaction with the user. Incorporating preferences into the solution process aims to efficiently evolve a dispatching rule that meets the expectations of a decision-maker. A fictitious experiment was carried out in a benchmark job shop environment. The results show that the final solution selected by the decision-maker can produce schedules achieving a desired compromise between the makespan, total tardiness, and total waiting time. Testing the evolved dispatching rule on an independent set of instances and comparing its performance with other benchmark dispatching rules revealed that the proposed method successfully finds dispatching rules that meet the decision-maker’s expectations and are capable of reproducing similar compromise schedules for unseen problems in the same environment.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multi-objective optimization; job shop scheduling; decision support system; hyper-heuristic; genetic programmingReferences:
| [1] | Abednego, L., & Hendratmo, D. (2011). Genetic programming hyper-heuristic for solving dynamic production scheduling problem. In Proceedings of the 2011 international conference on electrical engineering and informatics (p. 1-4). doi:10.1109/ICEEI.2011.6021768. |
| [2] | Bäck, T., Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms (1996), Oxford, NY: Oxford University Press, Oxford, NY · Zbl 0877.68060 · doi:10.1093/oso/9780195099713.001.0001 |
| [3] | Baker, KR, Sequencing rules and duedate assignments in a job shop, Management Science, 30, 9, 1093-1104 (1984) · doi:10.1287/mnsc.30.9.1093 |
| [4] | Blackstone, JH; Phillips, DT; Hogg, GL, A state-of-the-art survey of dispatching rules for manufacturing job shop operations, International Journal of Production Research, 20, 1, 27-45 (1982) · doi:10.1080/00207548208947745 |
| [5] | Branke, J.; Nguyen, S.; Pickardt, CW; Zhang, M., Automated design of production scheduling heuristics: A review, IEEE Transactions on Evolutionary Computation, 20, 1, 110-124 (2016) · doi:10.1109/TEVC.2015.2429314 |
| [6] | Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S. (2003). Hyper-heuristics: An emerging direction in modern search technology. F. Glover & G.A. Kochenberger (Eds.), Handbook of metaheuristics (pp. 457-474). Boston, MA: Springer US. doi:10.1007/0-306-48056-5_16. · Zbl 1102.90377 |
| [7] | Burke, EK; Gendreau, M.; Hyde, M.; Kendall, G.; Ochoa, G.; Özcan, E.; Qu, R., Hyper-heuristics: A survey of the state of the art, Journal of the Operational Research Society, 64, 12, 1695-1724 (2013) · doi:10.1057/jors.2013.71 |
| [8] | Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J. R. (2009). Exploring hyper-heuristic methodologies with genetic programming. In C. L. Mumford & L. C. Jain (Eds.), Computational intelligence: Collaboration, fusion and emergence (pp. 177-201). Berlin, Heidelberg: Springer.doi:10.1007/978-3-642-01799-5_6. · Zbl 1184.68207 |
| [9] | Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Özcan, E., Woodward, J. R. (2019). A classification of hyper-heuristic approaches: Revisited. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of metaheuristics (pp. 453-477). Cham: Springer. doi:10.1007/978-3-319-91086-4_14. |
| [10] | Demirkol, E.; Mehta, S.; Uzsoy, R., Benchmarks for shop scheduling problems, European Journal of Operational Research, 109, 1, 137-141 (1998) · Zbl 0951.90022 · doi:10.1016/S0377-2217(97)00019-2 |
| [11] | Dimopoulos, C.; Zalzala, A., Investigating the use of genetic programming for a classic one-machine scheduling problem, Advances in Engineering Software, 32, 6, 489-498 (2001) · Zbl 1003.68577 · doi:10.1016/S0965-9978(00)00109-5 |
| [12] | Dorndorf, U., & Pesch, E. (1995). Evolution based learning in a job shop scheduling environment. Computers & Operations Research, 22(1), 25-40. (Genetic Algorithms) doi:10.1016/0305-0548(93)E0016-M. · Zbl 0815.90089 |
| [13] | Drake, JH; Kheiri, A.; Özcan, E.; Burke, EK, Recent advances in selection hyperheuristics, European Journal of Operational Research, 285, 2, 405-428 (2020) · Zbl 1441.90183 · doi:10.1016/j.ejor.2019.07.073 |
| [14] | Eiben, A. E., & Smith, J. E. (2015). Introduction to evolutionary computing (2nd ed. 2015 ed.). Berlin, Heidelberg: Springer. · Zbl 1327.68003 |
| [15] | Figueira, J.; Liefooghe, A.; Talbi, E-G; Wierzbicki, A., A parallel multiple reference point approach for multi-objective optimization, European Journal of Operational Research, 205, 2, 390-400 (2010) · Zbl 1188.90237 · doi:10.1016/j.ejor.2009.12.027 |
| [16] | Fisher, H., & Thompson, G. L. (1963). Probabilistic learning combinations of local job-shop scheduling rules. Industrial scheduling, 225-251. |
| [17] | Fortin, F-A; De Rainville, F-M; Gardner, M.; Parizeau, M.; Gagné, C., DEAP: Evolutionary algorithms made easy, Journal of Machine Learning Research, 13, 2171-2175 (2012) |
| [18] | Garey, MR; Johnson, DS; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 2, 117-129 (1976) · Zbl 0396.90041 · doi:10.1287/moor.1.2.117 |
| [19] | Geiger, CD; Uzsoy, R.; Aytuğ, H., Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach, Journal of Scheduling, 9, 1, 7-34 (2006) · Zbl 1154.90451 · doi:10.1007/s10951-006-5591-8 |
| [20] | Graham, R., Lawler, E., Lenstra, J., Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. In P. Hammer, E. Johnson, & B. Korte (Eds.), Discrete optimization II (Vol. 5, p. 287-326). Elsevier. doi:10.1016/S0167-5060(08)70356-X. · Zbl 0411.90044 |
| [21] | Hart, E., & Ross, P. (1998). A heuristic combination method for solving job-shop scheduling problems. In A. E. Eiben, T. Bäck, M. Schoenauer, & H.-P. Schwefel (Eds.), Parallel problem solving from nature – ppsn v (pp. 845-854). Berlin, Heidelberg: Springer. doi:10.1007/BFb0056926. |
| [22] | Ho, N. B., & Tay, J. C. (2005). Evolving dispatching rules for solving the flexible jobshop problem. In 2005 IEEE congress on evolutionary computation (vol. 3, pp. 2848-2855). doi:10.1109/CEC.2005.1555052. |
| [23] | Hunt, R., Johnston, M., Zhang, M. (2014). Evolving “less-myopic” scheduling rules for dynamic job shop scheduling with genetic programming. In Proceedings of the 2014 annual conference on genetic and evolutionary computation (pp. 927-934). New York, NY: Association for Computing Machinery. doi:10.1145/2576768.2598224. |
| [24] | Jakobović, D., Jelenković, L., Budin, L. (2007). Genetic programming heuristics for multiple machine scheduling. In M. Ebner, M. O’Neill, A. Ekárt, L. Vanneschi, & A.I. Esparcia- Alcázar (Eds.), Genetic programming (pp. 321-330). Berlin, Heidelberg: Springer. doi:10.1007/978-3-540-71605-1_30. |
| [25] | Koza, JR, Genetic programming: On the programming of computers by means of natural selection (1992), Cambridge, MA: MIT Press, Cambridge, MA · Zbl 0850.68161 |
| [26] | Koza, JR, Genetic programming II: Automatic discovery of reusable programs (1994), Cambridge, MA: MIT Press, Cambridge, MA · Zbl 0850.68160 |
| [27] | Koza, JR; Andre, D.; Keane, MA; Bennett, FH, Genetic programming III: Darwinian invention and problem solving (1999), San Francisco, CA: Morgan Kaufmann, San Francisco, CA · Zbl 1012.68663 |
| [28] | Koza, JR; Keane, MA; Streeter, MJ; Mydlowec, W.; Yu, J.; Lanza, G., Genetic programming IV: Routine humancompetitive machine intelligence (2005), New York: Springer, New York · Zbl 1090.68088 · doi:10.1007/b137549 |
| [29] | Kreipl, S., A large step random walk for minimizing total weighted tardiness in a job shop, Journal of Scheduling, 3, 125-138 (2000) · Zbl 0969.90045 · doi:10.1002/(SICI)1099-1425(200005/06)3:33.0.CO;2-C |
| [30] | Lin, J.; Wang, Z-J; Li, X., A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem, Swarm and Evolutionary Computation, 36, 124-135 (2017) · doi:10.1016/j.swevo.2017.04.007 |
| [31] | Masood, A., Mei, Y., Chen, G., Zhang, M. (2016). Many-objective genetic programming for job-shop scheduling. In 2016 IEEE congress on evolutionary computation (CEC) (pp. 209-216). doi:10.1109/CEC.2016.7743797. |
| [32] | Masood, A., Mei, Y., Chen, G., Zhang, M. (2017). A pso-based reference point adaption method for genetic programming hyper-heuristic in many-objective job shop scheduling. In M. Wagner, X. Li, & T. Hendtlass (Eds.), Artificial life and computational intelligence (pp. 326-338). Cham: Springer. doi:10.1007/978-3-319-51691-2_28. |
| [33] | Miettinen, K. (2008). Introduction to multiobjective optimization: Noninteractive approaches. In J. Branke, K. Deb, K. Miettinen, & R. Słowiński (Eds.), Multiobjective optimization: Interactive and evolutionary approaches (pp. 1-26). Berlin, Heidelberg: Springer. doi:10.1007/978-3-540-88908-3_1. · Zbl 1147.68304 |
| [34] | Miettinen, K., Ruiz, F., Wierzbicki, A. P. (2008). Introduction to multiobjective optimization: Interactive approaches. In J. Branke, K. Deb, K. Miettinen, & R. Słowiński (Eds.), Multiobjective optimization: Interactive and evolutionary approaches (pp. 27-57). Berlin, Heidelberg: Springer. doi:10.1007/978-3-540-88908-3_2. · Zbl 1147.68304 |
| [35] | Nguyen, S.; Mei, Y.; Zhang, M., Genetic programming for production scheduling: A survey with a unified framework, Complex (2017) · doi:10.1007/s40747-017-0036-x |
| [36] | Norenkov, I. P., & Goodma, E. D. (1998). Solving scheduling problems via evolutionary methods for rule sequence optimization. In P. K. Chawdhry, R. Roy, & R. K. Pant (Eds.), Soft computing in engineering design and manufacturing (pp. 350-355). London: Springer. doi:10.1007/978-1-4471-0427-8_38. |
| [37] | Ochoa, G., Vazquez-Rodriguez, J. A., Petrovic, S., Burke, E. (2009). Dispatching rules for production scheduling: A hyper-heuristic landscape analysis. In 2009 IEEE congress on evolutionary computation (pp. 1873-1880). doi:10.1109/CEC.2009.4983169. |
| [38] | Panwalkar, SS; Iskander, W., A survey of scheduling rules, Operations Research, 25, 1, 45-61 (1977) · Zbl 0369.90054 · doi:10.1287/opre.25.1.45 |
| [39] | Park, J.; Mei, Y.; Nguyen, S.; Chen, G.; Zhang, M., An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling, Applied Soft Computing, 63, 72-86 (2018) · doi:10.1016/j.asoc.2017.11.020 |
| [40] | Pickardt, CW; Hildebrandt, T.; Branke, J.; Heger, J.; Scholz-Reiter, B., Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems, International Journal of Production Economics, 145, 1, 67-77 (2013) · doi:10.1016/j.ijpe.2012.10.016 |
| [41] | Pinedo, M. (2012). Scheduling: Theory, algorithms, and systems (4th ed. ed.). New York: Springer.doi:10.1007/978-1-4614-2361-4. · Zbl 1239.90002 |
| [42] | Rajendran, C., & Holthaus, O. (1999). A comparative study of dispatching rules in dynamic flowshops and jobshops. European Journal of Operational Research,116(1), 156-170. doi:10.1016/S0377-2217(98)00023-X · Zbl 1009.90038 |
| [43] | Riquelme, N., Von Lücken, C., Baran, B. (2015). Performance metrics in multi-objective optimization. In 2015 latin American computing conference (clei) (pp. 1-11).doi:10.1109/CLEI.2015.7360024. |
| [44] | Rodríguez, J.A.V., & Salhi, A. (2007). A robust meta-hyper-heuristic approach to hybrid flow-shop scheduling. In K. P. Dahal, K. C. Tan, & P. I. Cowling (Eds.), Evolutionary scheduling (pp. 125-142). Berlin, Heidelberg: Springer. doi:10.1007/978-3-540-48584-1_5. · Zbl 1200.90091 |
| [45] | Ross, P. (2005). Hyper-heuristics. In E. K. Burke and G. Kendall (Eds.), Search methodologies: Introductory tutorials in optimization and decision support techniques (pp. 529-556). Boston, MA: Springer.doi:10.1007/0-387-28356-0_17. |
| [46] | Song, H-B; Lin, J., A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times, Swarm and Evolutionary Computation, 60 (2021) · doi:10.1016/j.swevo.2020.100807 |
| [47] | Steuer, RE, Multiple criteria optimization: Theory, computation, and application (1986), New York: Wiley, New York · Zbl 0663.90085 |
| [48] | Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 2, 278-285 (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M |
| [49] | Tay, JC; Ho, NB, Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems, Computers & Industrial Engineering, 54, 3, 453-473 (2008) · doi:10.1016/j.cie.2007.08.008 |
| [50] | Teixeira, T., Treuille, A., et al. (2018). Streamlit. GitHub. Retrieved from https://github.com/streamlit/streamlit |
| [51] | Vázquez-Rodíguez, JA; Petrovic, S., A new dispatching rule based genetic algorithm for the multi-objective job shop problem, Journal of Heuristics, 16, 6, 771-793 (2010) · Zbl 1198.90213 · doi:10.1007/s10732-009-9120-8 |
| [52] | Vazquez Rodriguez, J. A., Petrovic, S., Salhi, A. (2007). An investigation of hyperheuristic search spaces. In 2007 IEEE congress on evolutionary computation (pp. 3776-3783). doi:10.1109/CEC.2007.4424962. |
| [53] | Wierzbicki, A. P. (1980). The use of reference objectives in multiobjective optimization. In G. Fandel & T. Gal (Eds.), Multiple criteria decision making theory and application (pp. 468-486). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-48782-8_32. · Zbl 0435.90098 |
| [54] | Yu, C.; Andreotti, P.; Semeraro, Q., Multi-objective scheduling in hybrid flow shop: Evolutionary algorithms using multidecoding framework, Computers & Industrial Engineering, 147 (2020) · doi:10.1016/j.cie.2020.106570 |
| [55] | Zeiträg, Y., Figueira, J. R., Horta, N., & Neves, R. (2022). Surrogate-assisted automatic evolving of dispatching rules for multi-objective dynamic job shop scheduling using genetic programming. Expert Systems with Applications,209, 118194. doi:10.1016/j.eswa.2022.118194 |
| [56] | Zeiträg, Y., Figueira, J. R., Pereira, M. A. (2021). A web-based interactive decision support system for a multi-objective lot-sizing and production scheduling model. Manuscript submitted for publication. |
| [57] | Zhou, H., Cheung, W., & Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research,194(3), 637-649. doi:10.1016/j.ejor.2007.10.063 · Zbl 1163.90004 |
| [58] | Zhou, Y., & Yang, J.-j. (2019). Automatic design of scheduling policies for dynamic flexible job shop scheduling by multiobjective genetic programming based hyperheuristic. Procedia CIRP, 79, 439-444. (12th CIRP Conference on Intelligent Computation in Manufacturing Engineering, 18-20 July 2018, Gulf of Naples, Italy) doi:10.1016/j.procir.2019.02.118. |
| [59] | Zhou, Y.; Yang, J-J; Huang, Z., Automatic design of scheduling policies for dynamic flexible job shop scheduling via surrogate-assisted cooperative co-evolution genetic programming, International Journal of Production Research, 58, 9, 2561-2580 (2020) · doi:10.1080/00207543.2019.1620362 |
| [60] | Zhou, Y., Yang, J.-J., & Zheng, L.-Y. (2019). Hyperheuristic coevolution of machine assignment and job sequencing rules for multi-objective dynamic flexible job shop scheduling. IEEE Access,7, 68-88. doi:10.1109/ACCESS.2018.2883802 |
| [61] | Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., & Da Fonseca, V. G. (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on evolutionary computation,7(2), 117-132. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
