nach oben

Neural Computing and Applications

Erschienen in:

28.08.2020 | Original Article

Automatic design of dispatching rules for static scheduling conditions

verfasst von: Marko Ðurasević, Domagoj Jakobović

Erschienen in: Neural Computing and Applications | Ausgabe 10/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Dispatching rules (DRs) represent heuristic methods designed for solving various scheduling problems. Since it is hard to manually design new DRs, genetic programming is used to design them automatically. Most DRs are designed in a way that they can be applied under dynamic conditions. On the other hand, static problems are usually solved using various metaheuristic methods. However, situations exist in which metaheuristics might not be the best choice for static problems. Such situations can occur when the schedule needs to be constructed quickly so that the system starts executing as soon as possible, or when it is possible that certain changes happen during the execution of the system. For these cases, DRs are more suitable since they execute faster and can adapt to dynamic changes in the system. However, as most research is focused on developing DRs for dynamic conditions, they would perform poorly under static conditions, since they would not use all the information that is available. Therefore, there is a need to enable automatic development of DRs suitable for static and offline conditions. The objective of this paper is to analyse several methods by which automatically generated DRs can be adapted for static and offline scheduling conditions. In addition to look-ahead and iterative DRs which were studied previously, this paper proposes new terminal nodes, as well as the application of the rollout algorithm to adapt DRs for static conditions. The performance and execution time of all methods are compared with the results achieved by automatically generated DRs for dynamic conditions and genetic algorithms. The tested methods obtain a wide range of results and prove to be competitive both in their performance and execution speed with other approaches. As such, they are a viable alternative to metaheuristics since they can be used in situations where metaheuristics could not, but can offer either a better execution time or even competitive results.

Vorheriger Artikel Coronavirus herd immunity optimizer (CHIO)

Nächster Artikel Skills prediction based on multi-label resume classification using CNN with model predictions explanation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Cheng V, Crawford L, Menon P (1999) Air traffic control using genetic search techniques. In: Proceedings of the 1999 IEEE international conference on control applications, vol 1, pp 249–254. https://doi.org/10.1109/CCA.1999.806209

Hansen JV (2004) Genetic search methods in air traffic control. Comput Oper Res 31(3):445–459. https://doi.org/10.1016/S0305-0548(02)00228-9MathSciNetCrossRefMATH

Dimopoulos C, Zalzala A (2000) Recent developments in evolutionary computation for manufacturing optimization: problems, solutions, and comparisons. IEEE Trans Evol Comput 4(2):93–113. https://doi.org/10.1109/4235.850651CrossRef

Pfund ME, Mason SJ, Fowler JW (2006) Semiconductor manufacturing scheduling and dispatching. In: Herrmann JW (ed) Handbook of production scheduling. Kluwer, Boston, pp 213–241. https://doi.org/10.1007/0-387-33117-4_9CrossRefMATH

Sarin SC, Varadarajan A, Wang L (2011) A survey of dispatching rules for operational control in wafer fabrication. Prod Plan Control 22(1):4–24. https://doi.org/10.1080/09537287.2010.490014CrossRef

Kofler M, Wagner S, Beham A, Kronberger G, Affenzeller M (2009) Priority rule generation with a genetic algorithm to minimize sequence dependent setup costs. In: Computer aided systems theory, Las Palmas de Gran Canaria, Spain, February 15–20, pp 817–824, Springer. https://doi.org/10.1007/978-3-642-04772-5_105

Singh S, Chana I (2016) A survey on resource scheduling in cloud computing: issues and challenges. J Grid Comput 14(2):217–264. https://doi.org/10.1007/s10723-015-9359-2CrossRef

Ernst A, Jiang H, Krishnamoorthy M, Sier D (2004) Staff scheduling and rostering: a review of applications, methods and models. Eur J Oper Res 153(1):3–27. https://doi.org/10.1016/s0377-2217(03)00095-xMathSciNetCrossRefMATH

Hou E, Ansari N, Ren H (1994) A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2):113–120. https://doi.org/10.1109/71.265940CrossRef

10.

Petrovic S, Castro E (2011) A genetic algorithm for radiotherapy pre-treatment scheduling. In: Applications of evolutionary computation: EvoApplications 2011, Torino, Italy, April 27–29, , pp 454–463. Springer, Berlin. https://doi.org/10.1007/978-3-642-20520-0_46

11.

Pinedo ML (2012) Scheduling: theory, algorithms, and systems, vol 9781461423614, 4th edn. Springer, Boston. https://doi.org/10.1007/978-1-4614-2361-4CrossRefMATH

12.

Yaseen ZM, Sulaiman SO, Deo RC, Chau KW (2019) An enhanced extreme learning machine model for river flow forecasting: state-of-the-art, practical applications in water resource engineering area and future research direction. J Hydrol 569:387–408. https://doi.org/10.1016/j.jhydrol.2018.11.069CrossRef

13.

Najafi B, Ardabili SF, Shamshirband S, wing Chau K, Rabczuk T (2018) Application of ANNs, ANFIS and RSM to estimating and optimizing the parameters that affect the yield and cost of biodiesel production. Eng Appl Comput Fluid Mech 12(1):611–624. https://doi.org/10.1080/19942060.2018.1502688CrossRef

14.

Fotovatikhah F, Herrera M, Shamshirband S, wing Chau K, Ardabili SF, Piran MJ (2018) Survey of computational intelligence as basis to big flood management: challenges, research directions and future work. Eng Appl Comput Fluid Mech 12(1):411–437. https://doi.org/10.1080/19942060.2018.1448896CrossRef

15.

Cheng CT, Lin JY, Sun YG, Chau K (2005) Long-term prediction of discharges in manwan hydropower using adaptive-network-based fuzzy inference systems models. In: Wang L, Chen K, Ong YS (eds) Adv Nat Comput. Springer, Berlin, pp 1152–1161

16.

Wang W, Chau K, Qiu L, Chen Y (2015) Improving forecasting accuracy of medium and long-term runoff using artificial neural network based on eemd decomposition. Environ Res 139:46–54. https://doi.org/10.1016/j.envres.2015.02.002CrossRef

17.

Moazenzadeh R, Mohammadi B, Shamshirband S, wing Chau K (2018) Coupling a firefly algorithm with support vector regression to predict evaporation in northern Iran. Eng Appl Comput Fluid Mech 12(1):584–597. https://doi.org/10.1080/19942060.2018.1482476CrossRef

18.

Picek S, Cupic M, Rotim L (2016) A new cost function for evolution of s-boxes. Evol Comput 24(4):695–718. https://doi.org/10.1162/EVCO_a_00191CrossRef

19.

Picek S, Jakobovic D, Miller JF, Batina L, Cupic M (2016) Cryptographic boolean functions: one output, many design criteria. Appl Soft Comput 40:635–653. https://doi.org/10.1016/j.asoc.2015.10.066CrossRef

20.

Gogna A, Tayal A (2013) Metaheuristics: review and application. J Exp Theor Artif Intell 25(4):503–526. https://doi.org/10.1080/0952813X.2013.782347CrossRef

21.

Cheng R, Gen M, Tsujimura Y (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms—i. representation. Comput Ind Eng 30(4):983–997. https://doi.org/10.1016/0360-8352(96)00047-2CrossRef

22.

Cheng R, Gen M, Tsujimura Y (1999) A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Comput Ind Eng 36(2):343–364. https://doi.org/10.1016/s0360-8352(99)00136-9CrossRef

23.

Zhou H, Feng Y, Han L (2001) The hybrid heuristic genetic algorithm for job shop scheduling. Comput Ind Eng 40(3):191–200. https://doi.org/10.1016/s0360-8352(01)00017-1CrossRef

24.

Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2):204–223. https://doi.org/10.1109/tevc.2003.810752CrossRef

25.

Hart E, Ross P, Corne D (2005) Evolutionary scheduling: a review. Genet Program Evolvable Mach 6(2):191–220. https://doi.org/10.1007/s10710-005-7580-7CrossRef

26.

Gao J, Gen M, Sun L, Zhao X (2007) A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Comput Ind Eng 53(1):149–162. https://doi.org/10.1016/j.cie.2007.04.010CrossRef

27.

Lin CW, Lin YK, Hsieh HT (2013) Ant colony optimization for unrelated parallel machine scheduling. Int J Adv Manuf Technol 67(1–4):35–45. https://doi.org/10.1007/s00170-013-4766-7CrossRef

28.

Lee JH, Yu JM, Lee DH (2013) A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness. Int J Adv Manuf Technol 69(9–12):2081–2089. https://doi.org/10.1007/s00170-013-5192-6CrossRef

29.

Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freund RF (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distrib Comput 59(2):107–131. https://doi.org/10.1006/jpdc.1999.1581CrossRef

30.

Braun TD, Siegel HJ, Beck N, Bölöni LL, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B, Hensgen D, Freund RF (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61(6):810–837. https://doi.org/10.1006/jpdc.2000.1714CrossRefMATH

31.

Yang-Kuei L, Chi-Wei L (2013) Dispatching rules for unrelated parallel machine scheduling with release dates. Int J Adv Manuf Technol 67(1–4):269–279. https://doi.org/10.1007/s00170-013-4773-8CrossRef

32.

Đurasević M, Jakobović D (2018) A survey of dispatching rules for the dynamic unrelated machines environment. Expert Syst Appl 113:555–569. https://doi.org/10.1016/j.eswa.2018.06.053CrossRef

33.

Koza JR (1990) Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems. Technical Report, Stanford, CA, USA

34.

Poli R, Langdon WB, McPhee NF (2008) A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk

35.

Koza JR (2010) Human-competitive results produced by genetic programming. Genet Program Evolvable Mach 11(3–4):251–284. https://doi.org/10.1007/s10710-010-9112-3CrossRef

36.

Miyashita K (2000) Job-shop scheduling with genetic programming. In: Proceedings of the 2nd annual conference on genetic and evolutionary computation, GECCO’00, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp 505–512. http://dl.acm.org/citation.cfm?id=2933718.2933809

37.

Geiger CD, Uzsoy R, Aytuğ H (2006) Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. J Sched 9(1):7–34. https://doi.org/10.1007/s10951-006-5591-8CrossRefMATH

38.

Jakobović D, Budin L (2006) Dynamic scheduling with genetic programming. In: Genetic programming: 9th European conference, EuroGP 2006, Budapest, Hungary, April 10–12, Proceedings, pp 73–84. Springer, Berlin. https://doi.org/10.1007/11729976_7

39.

Nie L, Gao L, Li P, Zhang L (2011) Application of gene expression programming on dynamic job shop scheduling problem. In: Proceedings of the 2011 15th international conference on computer supported cooperative work in design (CSCWD), IEEE, pp 291–295. https://doi.org/10.1109/CSCWD.2011.5960088

40.

Jakobović D, Marasović K (2012) Evolving priority scheduling heuristics with genetic programming. Appl Soft Comput 12(9):2781–2789. https://doi.org/10.1016/j.asoc.2012.03.065CrossRef

41.

Nguyen S, Zhang M, Johnston M, Tan KC (2013) Dynamic multi-objective job shop scheduling: A genetic programming approach. In: Automated scheduling and planning: from theory to practice, pp 251–282. Springer, Berlin. https://doi.org/10.1007/978-3-642-39304-4_10

42.

Nguyen S, Zhang M, Tan KC (2015) Enhancing genetic programming based hyper-heuristics for dynamic multi-objective job shop scheduling problems. In: 2015 IEEE congress on evolutionary computation (CEC), IEEE, pp 2781–2788. https://doi.org/10.1109/CEC.2015.7257234

43.

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), IEEE, pp 209–216. https://doi.org/10.1109/CEC.2016.7743797

44.

Karunakaran D, Chen G, Zhang M (2016) Parallel multi-objective job shop scheduling using genetic programming. In: Artificial life and computational intelligence: second Australasian conference, ACALCI 2016, Canberra, Australia, February 2–5, Proceedings, pp 234–245. Springer. https://doi.org/10.1007/978-3-319-28270-1_20

45.

Đurasević M, Jakobović D (2018) Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment. Genet Program Evolvable Mach 19(1):9–51. https://doi.org/10.1007/s10710-017-9310-3CrossRef

46.

Park J, Nguyen S, Zhang M, Johnston M (2015) Evolving ensembles of dispatching rules using genetic programming for job shop scheduling. In: Genetic programming: 18th European conference, EuroGP 2015, Copenhagen, Denmark, April 8–10, pp 92–104. Springer. https://doi.org/10.1007/978-3-319-16501-1_8

47.

Hart E, Sim K (2016) A hyper-heuristic ensemble method for static job-shop scheduling. Evol Comput 24(4):609–635. https://doi.org/10.1162/EVCO_a_00183CrossRef

48.

Đurasević M, Jakobović D (2018) Comparison of ensemble learning methods for creating ensembles of dispatching rules for the unrelated machines environment. Genet Program Evolvable Mach 19(1):53–92. https://doi.org/10.1007/s10710-017-9302-3CrossRef

49.

Nguyen S, Zhang M, Johnston M, Tan KC (2013) A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Trans Evol Comput 17(5):621–639. https://doi.org/10.1109/TEVC.2012.2227326CrossRef

50.

Branke J, Hildebrandt T, Scholz-Reiter B (2015) Hyper-heuristic evolution of dispatching rules: a comparison of rule representations. Evol Comput 23(2):249–277. https://doi.org/10.1162/EVCO_a_00131CrossRef

51.

Đurasević M, Jakobović D, Knežević K (2016) Adaptive scheduling on unrelated machines with genetic programming. Appl Soft Comput 48:419–430. https://doi.org/10.1016/j.asoc.2016.07.025CrossRef

52.

Ingimundardottir H, Runarsson TP (2011) Supervised learning linear priority dispatch rules for job-shop scheduling. In: Coello CAC (ed) Learning and intelligent optimization: 5th international conference, LION 5, Rome, Italy, January 17–21, 2011. Selected Papers, pp 263–277. Springer. https://doi.org/10.1007/978-3-642-25566-3_20

53.

Li X, Olafsson S (2005) Discovering dispatching rules using data mining. J Sched 8(6):515–527. https://doi.org/10.1007/s10951-005-4781-0MathSciNetCrossRefMATH

54.

Đurasević M, Jakobović D (2019) Creating dispatching rules by simple ensemble combination. J Heuristics 25(6):959–1013. https://doi.org/10.1007/s10732-019-09416-xCrossRef

55.

Branke J, Nguyen S, Pickardt CW, Zhang M (2016) Automated design of production scheduling heuristics: a review. IEEE Trans Evol Comput 20(1):110–124. https://doi.org/10.1109/TEVC.2015.2429314CrossRef

56.

Nguyen S, Mei Y, Zhang M (2017) Genetic programming for production scheduling: a survey with a unified framework. Complex Intell Syst 3(1):41–66. https://doi.org/10.1007/s40747-017-0036-xCrossRef

57.

Pfund M, Fowler JW, Gadkari A, Chen Y (2008) Scheduling jobs on parallel machines with setup times and ready times. Comput Ind Eng 54(4):764–782. https://doi.org/10.1016/j.cie.2007.08.011CrossRef

58.

Adyanthaya S, Geilen M, Basten T, Schiffelers R, Theelen B, Voeten J (2013) Fast multiprocessor scheduling with fixed task binding of large scale industrial cyber physical systems. In: Proceedings of the Euromicro conference on digital system design 2013, 4–6 September 2013, Los Alamitos, California, Institute of Electrical and Electronics Engineers, United States, pp 979–988. https://doi.org/10.1109/DSD.2013.111

59.

Morton TE, Pentico DW (1993) Heuristic scheduling systems. Wiley, New York

60.

Hildebrandt T, Heger J, Scholz-Reiter B (2010) Towards improved dispatching rules for complex shop floor scenarios. In: Proceedings of the 12th annual conference on genetic and evolutionary computation—GECCO ’10, ACM Press, New York, New York, USA, p 257. https://doi.org/10.1145/1830483.1830530

61.

Nguyen S, Zhang M, Johnston M, Tan KC (2013) Learning iterative dispatching rules for job shop scheduling with genetic programming. Int J Adv Manuf Technol 67(1–4):85–100. https://doi.org/10.1007/s00170-013-4756-9CrossRef

62.

Ferreira C (2001) Gene expression programming: a new adaptive algorithm for solving problems. Complex Syst 13(2):87–129MathSciNetMATH

63.

Keijzer M, Babovic V (1999) Dimensionally aware genetic programming. Proc Genet Evol Comput Conf 2:1069–1076

64.

Miller JF, Thomson P (2000) Cartesian genetic programming. Lect Notes Comput Sci 1802:121–132. https://doi.org/10.1007/978-3-540-46239-2_9 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)CrossRef

65.

Bertsekas DP, Castanon DA (1999) Rollout algorithms for stochastic scheduling problems. J Heuristics 5(1):89–108. https://doi.org/10.1023/A:1009634810396CrossRefMATH

66.

Bertsekas DP (2013) Rollout algorithms for discrete optimization: a survey. Springer, New York, pp 2989–3013. https://doi.org/10.1007/978-1-4419-7997-1_8CrossRef

67.

Dimopoulos C, Zalzala AM (2001) Investigating the use of genetic programming for a classic one-machine scheduling problem. Adv Eng Softw 32(6):489–498CrossRef

68.

Dimopoulos C, Zalzala AM (1999) A genetic programming heuristic for the one-machine total tardiness problem. In: Proceedings of the 1999 congress on evolutionary computation, 1999. CEC 99, vol 3. IEEE

69.

Lee YH, Bhaskaran K, Pinedo M (1997) A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Trans 29(1):45–52CrossRef

70.

Pfund M, Fowler JW, Gadkari A, Chen Y (2008) Scheduling jobs on parallel machines with setup times and ready times. Comput Ind Eng 54(4):764–782CrossRef

Titel: Automatic design of dispatching rules for static scheduling conditions
verfasst von: Marko Ðurasević
Domagoj Jakobović
Publikationsdatum: 28.08.2020
Verlag: Springer London
Erschienen in: Neural Computing and Applications / Ausgabe 10/2021
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-020-05292-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 10/2021

Identifying crop water stress using deep learning models

Spatial division networks for weakly supervised detection

Boosting attention fusion generative adversarial network for image denoising

A novel two-model local search algorithm with a self-adaptive parameter for clique partitioning problem

Modified semi-supervised affinity propagation clustering with fuzzy density fruit fly optimization

Copy-move forgery detection technique based on discrete cosine transform blocks features