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
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Elektrische Antriebe und Energiesysteme 2025 | 26 + 27 März 2025

19. Internationaler MTZ-Fachkongress Zukunftsantriebe

Seien Sie bei der Konferenz dabei! Dort treffen Experten aus der Automobilindustrie, Energieerzeugung und Stromnetzbetrieb auf Vertreter aus Politik und Wissenschaft. Diskutiert werden wichtige Themen der Branche.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

41. Scheduling Heuristics

verfasst von : Rubén Ruiz

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The scheduling of operations over resources is a relevant theoretical and practical problem with applications in many fields and disciplines, including the manufacturing industry. Scheduling problems are as varied as the reality they model. Additionally, some scheduling settings are among the hardest combinatorial problems there are. This is a perfect scenario for heuristic methods where high-quality robust solutions can be obtained in a short amount of time. This chapter concentrates on heuristics for production scheduling problems and summarizes the main results that range from simple rules to advanced metaheuristics. The importance of proper scheduling in practice is first highlighted, along with its difficulty and relevance. A summary of the scheduling notation is also given. Basic scheduling techniques, dispatching rules, combined rules, advanced heuristics, and an introduction to metaheuristics are also summarized in the chapter. While necessarily brief and incomplete, this chapter serves as an introductory point to those interested readers seeking to delve in the vast and rich world of scheduling heuristics. Some pointers to fruitful future research avenues are also provided. A large list of journal articles and monographs are provided as a reference for additional details and study.

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 Particle Swarm Optimization for the Vehicle Routing Problem: A Survey and a Comparative Analysis
Nächstes Kapitel Selected String Problems
Literatur
1.
Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401
2.
Błażewicz J, Ecker KH, Pesch E, Schmidt G, Wȩglarz J (2001) Scheduling computer and manufacturing processes, 2nd edn. Springer, Berlin
3.
Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59(5):1269–1283
4.
Blackstone JH Jr, Phillips DT, Hogg GL (1982) A state-of-the-art survey of dispatching rules for manufactuing job shop operations. Int J Prod Res 20(1):27–45
5.
Briskorn D (2008) Sports leagues scheduling. Models, combinatorial properties, and optimization algorithms. Lecture notes in economics and mathematical systems, vol 603. Springer, Berlin/Heidelberg
6.
Brucker P (2007) Scheduling algorithms, 5th edn. Springer, New York
7.
Brucker P, Jurisch B, Sievers B (1994) A branch and bound algorithm for the job-shop scheduling problem. Discret Appl Math 49(1–3):107–127
8.
Cai X, Wu X, Zhou X (2014) Optimal stochastic scheduling. International series in operations research & management science, vol 207. Springer, New York
9.
Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11(1):42–47
10.
Chakraborty UK, Laha D (2007) An improved heuristic for permutation flowshop scheduling. Int J Inf Commun Technol 1(1):89–97
11.
Ciavotta M, Minella G, Ruiz R (2013) Multi-objective sequence dependent setup times flowshop scheduling: a new algorithm and a comprehensive study. Eur J Oper Res 227(2):301–313
12.
Dong XY, Huang HK, Chen P (2006) A more effective constructive algorithm for permutation flowshop problem. In: Intelligent data engineering and automated learning (IDEAL 2006). lecture notes in computer science, vol 4224. Springer, Berlin/New York (Beijing Jiaotong Univ, Sch Comp & IT, Beijing 100044, Peoples R China), pp 25–32
13.
Dong XY, Huang HK, Chen P (2008) An improved NEH-based heuristic for the permutation flowshop problem. Comput Oper Res 35(12):3962–3968
14.
Dudek RA, Panwalkar SS, Smith ML (1992) The lessons of flowshop scheduling research. Oper Res 40(1):7–13
15.
El-Ghazali T (2009) Metaheuristics: from design to implementation. Wiley, New York
16.
Fanjul-Peyro L, Ruiz R (2010) Iterated greedy local search methods for unrelated parallel machine scheduling. Eur J Oper Res 207(1):55–69
17.
Fernandez-Viagas V, Framinan JM (2014) On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Comput Oper Res 45:60–67
18.
Fernandez-Viagas V, Framinan JM (2015) A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem. Int J Prod Res 53(4):1111–1123
19.
Ford FN, Bradbard DA, Ledbetter WN, Cox JF (1987) Use of operations research in production management. Prod Invent Manag 28(3):59–62
20.
Framinan JM, Leisten R (2008) Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm. Int J Prod Res 46(22):6479–6498
21.
Framinan JM, Ruiz R (2010) Architecture of manufacturing scheduling systems: literature review and an integrated proposal. Eur J Oper Res 205(2):237–246
22.
Framinan JM, Ruiz R (2012) Guidelines for the deployment and implementation of manufacturing scheduling systems. Int J Prod Res 50(7):1799–1812
23.
Framinan JM, Leisten R, Rajendran C (2003) Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. Int J Prod Res 41(1):121–148
24.
Framinan JM, Leisten R, Ruiz R (2014) Manufacturing scheduling systems. An integrated view on models, methods and tools. Springer, New York
25.
Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416–429
26.
Graves SC (1981) A review of production scheduling. Oper Res 29(4):646–675
27.
Grosche T (2009) Computational intelligence in integrated airline scheduling. Studies in computational intelligence, vol 173. Springer, New York
28.
Haupt R (1989) A survey or priority rule-based scheduling. OR Spectr 11(1):3–16
29.
Hoos HH, Stützle T (2005) Stochastic local search: foundations and applications. Morgan Kaufmann, San Francisco
30.
Hopp WJ, Spearman ML (2011) Factory physics, 3rd edn. Waveland Press Inc., Long Grove
31.
Jayamohan MS, Rajendran C (2000) New dispatching rules for shop scheduling: a step forward. Int J Prod Res 38(3):563–586
32.
Jin F, Song SJ, Wu C (2007) An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems. IIE Trans 39(2):229–234
33.
Kalczynski PJ, Kamburowski J (2007) On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA Int J Manag Sci 35(1):53–60
34.
Kalczynski PJ, Kamburowski J (2008) An improved NEH heuristic to minimize makespan in permutation flow shops. Comput Oper Res 35(9):3001–3008
35.
Kalczynski PJ, Kamburowski J (2009) An empirical analysis of the optimality rate of flow shop heuristics. Eur J Oper Res 198(1):93–101
36.
Laporte G (2009) Fifty years of vehicle routing. Transp Sci 43(4):408–416
37.
Ledbetter WN, Cox JF (1977) Operations research in production management: an investigation of past and present utilisation. Prod Invent Manag 18(3):84–91
38.
Lee YH, Bhaskaran K, Pinedo ML (1997) A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Trans 29(1):45–52
39.
Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:343–362
40.
Lin SW, Ying KC, Huang CY (2013) Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. Int J Prod Res 51(16):5029–5038
41.
MacCarthy BL, Liu J (1993) Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. Int J Prod Res 31(1):59–79
42.
McKay KN, Wiers VCS (1999) Unifying the theory and practice of production scheduling. J Manuf Syst 18(4):241–255
43.
McKay KN, Wiers VCS (2004) Practical production control. A survival guide for planners and schedulers. J. Ross Publishing Inc., Boca Raton
44.
McKay KN, Wiers VCS (2006) The human factor in planning and scheduling, chap 2. In: Herrmann JW (ed) Handbook of production scheduling. International series in operations research & management science, vol 89. Springer, New York, pp 23–57
45.
McKay KN, Safayeni FR, Buzacott JA (1988) Job-shop scheduling theory: what is relevant? Interfaces 4(18):84–90
46.
McKay KN, Pinedo ML, Webster S (2002) Practice-focused research issues for scheduling systems. Prod Oper Manag 11(2):249–258
47.
Minella G, Ruiz R, Ciavotta M (2011) Restarted iterated pareto greedy algorithm for multi-objective flowshop scheduling problems. Comput Oper Res 38(11):1521–1533
48.
Morton TE, Pentico DW (1993) Heuristic scheduling sysmtems with applications to production systems and project management. Wiley series in engineering & technology management. Wiley, Hoboken
49.
Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA Int J Manag Sci 11(1):91–95CrossRef
50.
Olhager J, Rapp B (1995) Operations research techniques in manufacturing planning and control systems. Int Trans Oper Res 2(1):29–43CrossRef
51.
Ovacik IM, Uzsoy R (1997) Decomposition methods for complex factory scheduling problems. Springer, New YorkCrossRef
52.
Pan QK, Ruiz R (2012) Local search methods for the flowshop scheduling problem with flowtime minimization. Eur J Oper Res 222(1):31–43MathSciNetCrossRef
53.
Pan QK, Ruiz R (2014) An effective iterated Greedy algorithm for the mixed no-idle flowshop scheduling problem. OMEGA Int J Manag Sci 44(1):41–50CrossRef
54.
Pan QK, Wang L, Zhao BH (2008) An improved iterated Greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion. Int J Adv Manuf Technol 38(7–8):778–786CrossRef
55.
56.
Pinedo ML (2009) Planning and scheduling in manufacturing and services, 2nd edn. Springer, New YorkCrossRef
57.
Pinedo ML (2012) Scheduling: theory, algorithms and systems, 4th edn. Springer, New YorkCrossRef
58.
Rad SF, Ruiz R, Boroojerdian N (2009) New high performing heuristics for minimizing makespan in permutation flowshops. OMEGA Int J Manag Sci 37(2):331–345CrossRef
59.
Randolph H (ed) (2012) Handbook of healthcare system scheduling. International series in operations research & management science, vol 168. Springer, New York
60.
Reisman A, Kumar A, Motwani J (1997) Flowshop scheduling/sequencing research: a statistical review of the literature, 1952–1994. IEEE Trans Eng Manag 44(3):316–329CrossRef
61.
Ribas I, Leisten R, Framinan JM (2010) Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res 37(8):1439–1454MathSciNetCrossRef
62.
Ribas I, Companys R, Tort-Martorell X (2011) An iterated greedy algorithm for the flowshop scheduling problem with blocking. OMEGA Int J Manag Sci 39(3):293–301CrossRef
63.
Rinnooy Kan AHG (1976) Machine scheduling problems: classification, complexity and computations. Martinus Nijhoff, The Hague
64.
Ruiz R, Maroto C (2005) A comprehensive review and evaluation of permutation flowshop heuristics. Eur J Oper Res 165(2):479–494CrossRef
65.
Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177(3):2033–2049CrossRef
66.
Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur J Oper Res 187(3):1143–1159CrossRef
67.
Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flowshop scheduling problem. Eur J Oper Res 205(1):1–18CrossRef
68.
Ruiz R, Vallada E, Fernández-Martínez C (2009) Scheduling in flowshops with no-idle machines. In: Chakraborty UK (ed) Computational intelligence in flow shop and job shop scheduling. Studies in computational intelligence, vol 230. Springer, Berlin, pp 21–51CrossRef
69.
Sarin SC, Nagarajan B, Liao L (2014) Stochastic scheduling. Expectation-variance analysis of a schedule. Cambridge University Press, CambridgeMATH
70.
71.
Taillard E (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47(1):67–74MathSciNetCrossRef
72.
Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285CrossRef
73.
T’Kindt V, Billaut JC (2006) Multicriteria scheduling: theory, models and algorithms, 2nd edn. Springer, New YorkMATH
74.
Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. OMEGA Int J Manag Sci 15(1):75–78CrossRef
75.
Urlings T, Ruiz R (2007) Local search in complex scheduling problems. In: Stützle T, Birattari M, Hoos HH (eds) Engineering stochastic local search algorithms. Designing, implementing and analyzing effective heuristics. Lecture notes in computer science, vol 4638. Springer, Brussels, pp 202–206CrossRef
76.
Urlings T, Ruiz R, Sivrikaya-Şerifoğlu F (2010) Genetic algorithms for complex hybrid flexible flow line problems. International Journal of Metaheuristics 1(1):30–54CrossRef
77.
Urlings T, Ruiz R, Stützle T (2010) Shifting representation search for hybrid flexible flowline problems. European Journal of Operational Research 207(2):1086–1095MathSciNetCrossRef
78.
Vallada E, Ruiz R (2009) Cooperative metaheuristics for the permutation flowshop scheduling problem. Eur J Oper Res 193(2):365–376CrossRef
79.
Vepsalainen APJ, Morton TE (1987) Priority rules and lead time estimation for job shop scheduling with weighted tardiness costs. Manag Sci 33(8):1036–1047CrossRef
80.
Vignier A, Billaut JC, Proust C (1999) Les problèmes d’ordonnancement de type flow-shop hybride: État de l’art. RAIRO Recherche opérationnelle 33(2):117–183 (in French)MATH
81.
Weyland D (2010) A rigorous analysis of the harmony search algorithm: how the research community can be misled by a “novel” methodology. Int J Appl Metaheuristic Comput 1(2):50–60CrossRef
82.
Ying KC (2008) An iterated Greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks. IEEE Trans Evol Comput 60(6):810–817MATH
83.
Ying KC (2008) Solving non-permutation flowshop scheduling problems by an effective iterated Greedy heuristic. Int J Adv Manuf Technol 38(3–4):348–354CrossRef
Metadaten
Titel
Scheduling Heuristics
verfasst von
Rubén Ruiz
Copyright-Jahr
2018
Buch
Handbook of Heuristics

Print ISBN: 978-3-319-07123-7

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

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-07124-4_44

Premium Partner

    Bildnachweise