Skip to main content
Erschienen in: OR Spectrum 3/2018

30.04.2018 | Regular Article

Flow shop scheduling with flexible processing times

verfasst von: Matthias Bultmann, Sigrid Knust, Stefan Waldherr

Erschienen in: OR Spectrum | Ausgabe 3/2018

Einloggen

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

search-config
loading …

Abstract

In numerous flow shop variants, the processing times of the operations are not fixed in advance, but may be distributed with some flexibility among the machines. In this paper, we introduce a general model which is expressive enough to cover several models from the literature. While in most cases it is \(\mathcal {NP}\)-hard to find a job permutation and a corresponding distribution of processing times minimizing the makespan, we show that for a fixed job permutation a best processing time distribution can be calculated in polynomial time by linear programming. Based on this, we propose a tabu search procedure using the set of all job permutations as search space. In a computational study, we show the power of the new model. Besides the classical permutation flow shop environment, we study variants with blocking, no-wait and synchronous movement constraints.

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!

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!

Literatur
Zurück zum Zitat Bolat A (1994) Sequencing jobs on an automobile assembly line: objectives and procedures. Int J Prod Res 32(5):1219–1236CrossRef Bolat A (1994) Sequencing jobs on an automobile assembly line: objectives and procedures. Int J Prod Res 32(5):1219–1236CrossRef
Zurück zum Zitat Burdett RL, Kozan E (2001) Sequencing and scheduling in flowshops with task redistribution. J Oper Res Soc 52(12):1379–1389CrossRef Burdett RL, Kozan E (2001) Sequencing and scheduling in flowshops with task redistribution. J Oper Res Soc 52(12):1379–1389CrossRef
Zurück zum Zitat Emmons H, Vairaktarakis G (2012) Flow shop scheduling: theoretical results, algorithms, and applications, vol 182. Springer, New York Emmons H, Vairaktarakis G (2012) Flow shop scheduling: theoretical results, algorithms, and applications, vol 182. Springer, New York
Zurück zum Zitat Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129CrossRef Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129CrossRef
Zurück zum Zitat Gilmore PC, Gomory RE (1964) Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper Res 12(5):655–679CrossRef Gilmore PC, Gomory RE (1964) Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper Res 12(5):655–679CrossRef
Zurück zum Zitat Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(2):287–326CrossRef Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(2):287–326CrossRef
Zurück zum Zitat Gupta JND, Stafford EF (2006) Flowshop scheduling research after five decades. Eur J Oper Res 169:699–711CrossRef Gupta JND, Stafford EF (2006) Flowshop scheduling research after five decades. Eur J Oper Res 169:699–711CrossRef
Zurück zum Zitat Gupta JND, Koulamas CP, Kyparisis GJ, Potts CN, Strusevich VA (2004) Scheduling three-operation jobs in a two-machine flow shop to minimize makespan. Ann Oper Res 129(1–4):171–185CrossRef Gupta JND, Koulamas CP, Kyparisis GJ, Potts CN, Strusevich VA (2004) Scheduling three-operation jobs in a two-machine flow shop to minimize makespan. Ann Oper Res 129(1–4):171–185CrossRef
Zurück zum Zitat Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510–525CrossRef Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510–525CrossRef
Zurück zum Zitat Huang K-L (2008) Flow shop scheduling with synchronous and asynchronous transportation times. Ph.D. thesis, The Pennsylvania State University Huang K-L (2008) Flow shop scheduling with synchronous and asynchronous transportation times. Ph.D. thesis, The Pennsylvania State University
Zurück zum Zitat Janiak A (1988) General flow-shop scheduling with resource constraints. Int J Prod Res 26(6):1089–1103CrossRef Janiak A (1988) General flow-shop scheduling with resource constraints. Int J Prod Res 26(6):1089–1103CrossRef
Zurück zum Zitat Johnson SM (1954) Optimal two-and three-stage production schedules with setup times included. Nav Res Logist Q 1(1):61–68CrossRef Johnson SM (1954) Optimal two-and three-stage production schedules with setup times included. Nav Res Logist Q 1(1):61–68CrossRef
Zurück zum Zitat Knust S, Shakhlevich NV, Waldherr S, Weiß C (2017) Shop scheduling problems with pliable jobs. Technical report, University of Osnabrück Knust S, Shakhlevich NV, Waldherr S, Weiß C (2017) Shop scheduling problems with pliable jobs. Technical report, University of Osnabrück
Zurück zum Zitat Kouvelis P, Karabati S (1999) Cyclic scheduling in synchronous production lines. IIE Trans 31(8):709–719 Kouvelis P, Karabati S (1999) Cyclic scheduling in synchronous production lines. IIE Trans 31(8):709–719
Zurück zum Zitat Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem. Omega 11(1):91–95CrossRef Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem. Omega 11(1):91–95CrossRef
Zurück zum Zitat Néron E, Tercinet F, Eloudou Biloa A (2000) An exact method for a farming problem. In: Informs conference, San Antonio, Texas (USA) Néron E, Tercinet F, Eloudou Biloa A (2000) An exact method for a farming problem. In: Informs conference, San Antonio, Texas (USA)
Zurück zum Zitat Nowicki E, Zdrzałka S (1988) A two-machine flow shop scheduling problem with controllable job processing times. Eur J Oper Res 34(2):208–220CrossRef Nowicki E, Zdrzałka S (1988) A two-machine flow shop scheduling problem with controllable job processing times. Eur J Oper Res 34(2):208–220CrossRef
Zurück zum Zitat Nowicki E, Zdrzałka S (1990) A survey of results for sequencing problems with controllable processing times. Discrete Appl Math 26(2):271–287CrossRef Nowicki E, Zdrzałka S (1990) A survey of results for sequencing problems with controllable processing times. Discrete Appl Math 26(2):271–287CrossRef
Zurück zum Zitat Röck H (1984) The three-machine no-wait flow shop is NP-complete. J ACM 31(2):336–345CrossRef Röck H (1984) The three-machine no-wait flow shop is NP-complete. J ACM 31(2):336–345CrossRef
Zurück zum Zitat Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discrete Appl Math 155(13):1643–1666CrossRef Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discrete Appl Math 155(13):1643–1666CrossRef
Zurück zum Zitat Soylu B, Kirca Ö, Azizoğlu M (2007) Flow shop-sequencing problem with synchronous transfers and makespan minimization. Int J Prod Res 45(15):3311–3331CrossRef Soylu B, Kirca Ö, Azizoğlu M (2007) Flow shop-sequencing problem with synchronous transfers and makespan minimization. Int J Prod Res 45(15):3311–3331CrossRef
Zurück zum Zitat Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285CrossRef Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285CrossRef
Zurück zum Zitat Waldherr S (2015) Scheduling of flow shops with synchronous movement. Ph.D. thesis, Department of Mathematics and Computer Science, University of Osnabrück Waldherr S (2015) Scheduling of flow shops with synchronous movement. Ph.D. thesis, Department of Mathematics and Computer Science, University of Osnabrück
Zurück zum Zitat Waldherr S, Knust S (2015) Complexity results for flow shop problems with synchronous movement. Eur J Oper Res 242(1):34–44CrossRef Waldherr S, Knust S (2015) Complexity results for flow shop problems with synchronous movement. Eur J Oper Res 242(1):34–44CrossRef
Zurück zum Zitat Yenisey MM, Yagmahan B (2014) Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega 45:119–135CrossRef Yenisey MM, Yagmahan B (2014) Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega 45:119–135CrossRef
Metadaten
Titel
Flow shop scheduling with flexible processing times
verfasst von
Matthias Bultmann
Sigrid Knust
Stefan Waldherr
Publikationsdatum
30.04.2018
Verlag
Springer Berlin Heidelberg
Erschienen in
OR Spectrum / Ausgabe 3/2018
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI
https://doi.org/10.1007/s00291-018-0520-8

Weitere Artikel der Ausgabe 3/2018

OR Spectrum 3/2018 Zur Ausgabe