Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Swarm and Evolutionary Computation Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Genetic Programming for Job Shop Scheduling

verfasst von : Su Nguyen, Mengjie Zhang, Mark Johnston, Kay Chen Tan

Erschienen in: Evolutionary and Swarm Intelligence Algorithms

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Designing effective scheduling rules or heuristics for a manufacturing system such as job shops is not a trivial task. In the early stage, scheduling experts rely on their experiences to develop dispatching rules and further improve them through trials-and-errors, sometimes with the help of computer simulations. In recent years, automated design approaches have been applied to develop effective dispatching rules for job shop scheduling (JSS). Genetic programming (GP) is currently the most popular approach for this task. The goal of this chapter is to summarise existing studies in this field to provide an overall picture to interested researchers. Then, we demonstrate some recent ideas to enhance the effectiveness of GP for JSS and discuss interesting research topics for future studies.

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

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

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"

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
Vorheriges Kapitel Genetic Programming for Classification and Feature Selection
Nächstes Kapitel Evolutionary Fuzzy Systems: A Case Study for Intrusion Detection Systems
Literatur
1.
Asano, M., Ohta, H.: A heuristic for job shop scheduling to minimize total weighted tardiness. Comput. Ind. Eng. 42, 137–147 (2002)CrossRef
2.
Balas, E., Vazacopoulos, A.: Guided local search with shifting bottleneck for job shop scheduling. Manage. Sci. 44, 262–275 (1998)CrossRef
3.
Banzhaf, W., Nordin, P., Keller, R., Francone, F.: Genetic Programming: An Introduction. Morgan Kaufmann, San Francisco (1998)CrossRef
4.
5.
6.
7.
Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.R.: Exploring hyper-heuristic methodologies with genetic programming. In: Mumford, C., Jain, L. (eds.) Computational Intelligence, Intelligent Systems Reference Library, vol. 1, pp. 177–201. Springer, Berlin, Heidelberg (2009)
8.
Cheng, V.H.L., Crawford, L.S., Menon, P.K.: Air traffic control using genetic search techniques. In: McClamroch, N.H., Sano, A., Gruebel, G. (eds.) In: Proceedings of the 1999 IEEE International Conference on Control Applications, vol. 1, pp. 249–254. IEEE Press, Piscataway, NJ (1999)
9.
Chiang, T.C., Shen, Y.S., Fu, L.C.: A new paradigm for rule-based scheduling in the wafer probe centre. Int. J. Prod. Res. 46(15), 4111–4133 (2008)CrossRef
10.
Dimopoulos, C., Zalzala, A.M.S.: Investigating the use of genetic programming for a classic one-machine scheduling problem. Adv. Eng. Softw. 32(6), 489–498 (2001)CrossRef
11.
El-Bouri, A., Balakrishnan, S., Popplewell, N.: Sequencing jobs on a single machine: a neural network approach. Eur. J. Oper. Res. 126(3), 474–490 (2000)MathSciNetCrossRef
12.
Essafi, I., Mati, Y., Dauzère-Pérès, S.: A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput. Oper. Res. 35(8), 2599–2616 (2008)MathSciNetCrossRef
13.
Ferreira, C.: Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence, 2nd edn. Springer, Germany (2006)MATH
14.
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1976)MathSciNetCrossRef
15.
Geiger, C.D., Uzsoy, R., Aytuğ, H.: Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. J. Sched. 9(1), 7–34 (2006)CrossRef
16.
Giffler, B., Thompson, G.L.: Algorithms for solving production-scheduling problems. Oper. Res. 8(4), 487–503 (1960)MathSciNetCrossRef
17.
Goncalves, J.F., de Magalhaes Mendes, J.J., Resende, M.G.C.: A hybrid genetic algorithm for the job shop scheduling problem. Eur. J. Oper. Res. 167(1), 77–95 (2005)MathSciNetCrossRef
18.
Hildebrandt, T., Heger, J., Scholz-Reiter, B.: Towards improved dispatching rules for complex shop floor scenarios—a genetic programming approach. In: Pelikan, M., Branke, J. (eds.) In: GECCO’10: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 257–264. ACM Press, New York (2010)
19.
Hildebrandt, T., Branke, J.: On using surrogates with genetic programming. Technical Report, Warwick Business School (2014)
20.
Holthaus, O., Rajendran, C.: Efficient jobshop dispatching rules: further developments. Prod. Plann. Control 11(2), 171–178 (2000)CrossRef
21.
Hunt, R., Johnston, M., Zhang, M.: Evolving “less-myopic” scheduling rules for dynamic job shop scheduling with genetic programming. In: GECCO’14: Proceedings of Genetic and Evolutionary Computation Conference (2014) (to appear)
22.
Ingimundardottir, H., Runarsson, T.P.: Supervised learning linear priority dispatch rules for job-shop scheduling. In: Coello Coello, C.A. (ed.) Learning and Intelligent Optimization, LNCS, vol. 6683, pp. 263–277. Springer, Berlin, Heidelberg (2011)CrossRef
23.
Jakobović, D., Budin, L.: Dynamic scheduling with genetic programming. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) Genetic Programming, LNCS, vol. 3905, pp. 73–84. Springer, Berlin, Heidelberg (2006)CrossRef
24.
Jakobović, D., Marasović, K.: Evolving priority scheduling heuristics with genetic programming. Appl. Soft Comput. 12(9), 2781–2789 (2012)CrossRef
25.
Jayamohan, M.S., Rajendran, C.: New dispatching rules for shop scheduling: a step forward. Int. J. Prod. Res. 38, 563–586 (2000)CrossRef
26.
Jayamohan, M.S., Rajendran, C.: Development and analysis of cost-based dispatching rules for job shop scheduling. Eur. J. Oper. Res. 157(2), 307–321 (2004)CrossRef
27.
Jedrzejowicz, P., Ratajczak-Ropel, E.: Agent-based gene expression programming for solving the RCPSP/max problem. In: Kolehmainen, M., Toivanen, P., Beliczynski, B. (eds.) Adaptive and Natural Computing Algorithms. Lecture Notes in Computer Science, vol. 5495, pp. 203–212. Springer, Berlin, Heidelberg (2009)CrossRef
28.
Johnston, M., Liddle, T., Zhang, M.: A relaxed approach to simplification in genetic programming. In: Esparcia-Alcázar, A.I., Ekárt, A., Silva, S., Dignum, S., Şima Uyar, A. (eds.) Genetic Programming, LNCS, vol. 6021, pp. 110–121. Springer, Berlin, Heidelberg (2010)CrossRef
29.
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA (1992)MATH
30.
Kreipl, S.: A large step random walk for minimizing total weighted tardiness in a job shop. J. Sched. 3, 125–138 (2000)MathSciNetCrossRef
31.
Kuczapski, A.M., Micea, M.V., Maniu, L.A., Cretu, V.I.: Efficient generation of near optimal initial populations to enhance genetic algorithms for job-shop scheduling. Inf. Technol. Control 39(1), 32–37 (2010)
32.
van Laarhoven, P.J.M., Aarts, E.H.L., Lenstra, J.K.: Job shop scheduling by simulated annealing. Oper. Res. 40(1), 113–125 (1992)MathSciNetCrossRef
33.
Lourenco, H.R.: Job-shop scheduling: computational study of local search and large-step optimization methods. Eur. J. Oper. Res. 83(2), 347–364 (1995)CrossRef
34.
McKay, K.N., Safayeni, F.R., Buzacott, J.A.: Job-shop scheduling theory: what is relevant? Interfaces 18, 84–90 (1988)CrossRef
35.
Miyashita, K.: Job-shop scheduling with genetic programming. In: Whitley, D., Goldberg, D., Cantu-Paz, E., Spector, L., Parmee, I., Beyer, H.G. (eds.) In: GECCO 2000: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 505–512. Morgan Kaufmann, San Francisco (2000)
36.
Nguyen, S., Zhang, M., Johnston, M., Tan, K.: Learning iterative dispatching rules for job shop scheduling with genetic programming. Int. J. Adv. Manuf. Technol. 67(1–4), 85–100 (2013)CrossRef
37.
Nguyen, S., Zhang, M., Johnston, M., Tan, K.C.: 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 (2013)CrossRef
38.
Nguyen, S., Zhang, M., Johnston, M., Tan, K.C.: Dynamic multi-objective job shop scheduling: a genetic programming approach. In: Etaner-Uyar, A.Ş., Özcan, E., Urquhart, N. (eds.) Automated Scheduling and Planning, Studies in Computational Intelligence, vol. 505, pp. 251–282. Springer, Berlin, Heidelberg (2013)CrossRef
39.
Nguyen, S., Zhang, M., Johnston, M., Tan, K.C.: Learning reusable initial solutions for multi-objective order acceptance and scheduling problems with genetic programming. In: Krawiec, K., Moraglio, A., Hu, T., Etaner-Uyar, A.Ş., Hu, B. (eds.) Genetic Programming, LNCS, vol. 7831, pp. 157–168. Springer, Berlin, Heidelberg (2013)CrossRef
40.
Nguyen, S., Zhang, M., Johnston, M., Tan, K.C.: Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. IEEE Trans. Evol. Comput. 18(2), 193–208 (2014)CrossRef
41.
Nguyen, S.: Automatic design of dispatching rules for job shop scheduling with genetic programming. Ph.D. thesis, Victoria University of Wellington (2013)
42.
Nie, L., Gao, L., Li, P., Li, X.: A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates. J. Intell. Manuf. 24(4), 763–774 (2013)CrossRef
43.
Nie, L., Shao, X., Gao, L., Li, W.: Evolving scheduling rules with gene expression programming for dynamic single-machine scheduling problems. Int. J. Adv. Manuf. Technol. 50(5–8), 729–747 (2010)CrossRef
44.
Nie, L., Bai, Y., Wang, X., Liu, K.: Discover scheduling strategies with gene expression programming for dynamic flexible job shop scheduling problem. In: Tan, Y., Shi, Y., Ji, Z. (eds.) Adv. Swarm Intell. 7332, 383–390 (2012)
45.
Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop problem. Manage. Sci. 42, 797–813 (1996)CrossRef
46.
Ouelhadj, D., Petrovic, S.: A survey of dynamic scheduling in manufacturing systems. J. Sched. 12(4), 417–431 (2009)MathSciNetCrossRef
47.
Petrovic, S., Fayad, C., Petrovic, D., Burke, E., Kendall, G.: Fuzzy job shop scheduling with lot-sizing. Ann. Oper. Res. 159, 275–292 (2008)MathSciNetCrossRef
48.
Pickardt, C.W., Hildebrandt, T., Branke, J., Heger, J., Scholz-Reiter, B.: Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems. Int. J. Prod. Econ. 145(1), 67–77 (2013)CrossRef
49.
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 3rd edn. Springer, New York (2008)MATH
50.
Pinedo, M., Singer, M.: A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Res. Logistics 46(1), 1–17 (1999)MathSciNetCrossRef
51.
Ponnambalam, S.G., Ramkumar, V., Jawahar, N.: A multiobjective genetic algorithm for job shop scheduling. Prod. Plann. Control 12(8) (2001)CrossRef
52.
53.
Sels, V., Gheysen, N., Vanhoucke, M.: A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions. Int. J. Prod. Res. 50(15), 4255–4270 (2011)CrossRef
54.
Sha, D., Hsu, C.Y.: A hybrid particle swarm optimization for job shop scheduling problem. Comput. Ind. Eng. 51(4), 791–808 (2006)CrossRef
55.
Tay, J.C., Ho, N.B.: Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput. Ind. Eng. 54(3), 453–473 (2008)CrossRef
56.
Wong, P., Zhang, M.: Algebraic simplification of gp programs during evolution. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. pp. 927–934. GECCO’06 (2006)
57.
Xing, L.N., Chen, Y.W., Wang, P., Zhao, Q.S., Xiong, J.: A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl. Soft Comput. 10(3), 888–896 (2010)CrossRef
58.
Yamada, T., Nakano, R.: A genetic algorithm with multi-step crossover for job-shop scheduling problems. In: GALESIA: First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. pp. 146–151 (1995)
59.
Yin, W.J., Liu, M., Wu, C.: Learning single-machine scheduling heuristics subject to machine breakdowns with genetic programming. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.C., McKay, B., Essam, D., Gedeon, T. (eds.) In: The 2003 Congress on Evolutionary Computation (CEC 2003), vol. 2, pp. 1050–1055. IEEE Press, Piscataway, NJ (2003)
Metadaten
Titel
Genetic Programming for Job Shop Scheduling
verfasst von
Su Nguyen
Mengjie Zhang
Mark Johnston
Kay Chen Tan
Copyright-Jahr
2019
Buch
Evolutionary and Swarm Intelligence Algorithms

Print ISBN: 978-3-319-91339-1

Electronic ISBN: 978-3-319-91341-4

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-319-91341-4_8

Premium Partner

    Bildnachweise