nach oben

Journal of Combinatorial Optimization

Erschienen in:

23.02.2020

Two-machine flow shop scheduling with an operator non-availability period to minimize makespan

verfasst von: Dawei Li, Xiwen Lu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we consider the two-machine flow shop scheduling with an operator non-availability period in the first stage to minimize makespan, where the operator non-availability period is an open time interval in which a job can neither start nor complete. We first prove that the problem is NP-hard, even if the length of the operator non-availability period is no more than the processing time of any job on the first machine. Then we show that Johnson’s rule is a 2-approximation algorithm and the bound is tight. Moreover, a better tight 3/2-approximation algorithm is provided.

Vorheriger Artikel Neighbour-distinguishing labellings of powers of paths and powers of cycles

Nächster Artikel Stabilizing social structure via modifying local patterns

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 "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

Brauner N, Finke G, Lehoux-Lebacque V, Rapine C, Kellerer H, Potts C, Strusevich V (2009) Operator non-availability periods. 4OR 7(3):239–253MathSciNetCrossRef

Breit J (2004) An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Inf Process Lett 90(6):273–278MathSciNetCrossRef

Chen Y, Zhang A, Tan ZY (2013) Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time. Inf Sci 251(4):150–163MathSciNetCrossRef

Cheng TCE, Wang GQ (2000) An improved heuristic for two-machine flowshop scheduling with an availability constraint. Oper Res Lett 26(5):223–229MathSciNetCrossRef

Hadda H, Dridi N, Hajri-Gabouj S (2010) An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs. 4OR 8(1):87–99MathSciNetCrossRef

Hnaien F, Yalaoui F, Mhadhbi A (2015) Makespan minimization on a two-machine flowshop with an availability constraint on the first machine. Int J Prod Econ 164(Complete):95–104CrossRef

Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist 1(1):61–68CrossRef

Kubzin MA, Potts CN, Strusevich VA (2009) Approximation results for flow shop scheduling problems with machine availability constraints. Comput Oper Res 36(2):379–390MathSciNetCrossRef

Lee CY (1997) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Oper Res Lett 20(3):129–139MathSciNetCrossRef

Lee CY (1999) Two-machine flowshop scheduling with availability constraints. Eur J Oper Res 114(2):420–429MathSciNetCrossRef

Lebacque V, Brauner N, Celse B, Finke G, Rapine C (2007) Planification d’expériences dans l’industrie chimique, Chap. 1, pp 21–32. Dans Les systèmes de production applications interdisciplinaires et mutations sous la direction de Boujut J-F, Llerena D, Brissaud D, Hermès-Lavoisier, ISBN, 978-2-7462-1819-2

Rapine C, Brauner N, Finke G, Lebacque V (2012) Single machine scheduling with small operator-non-availability periods. J Sched 15(2):127–139MathSciNetCrossRef

Wan L, Yuan JJ (2018) Single-machine scheduling with operator non-availability to minimize total weighted completion time. Inf Sci 445–446:1–5MathSciNetCrossRef

Wang XL, Cheng TCE (2007) Heuristics for two-machine flowshop scheduling with setup times and an availability constraint. Comput Oper Res 34(1):152–162MathSciNetCrossRef

Xu ZJ, Xu DH, He J, Wang Q, Liu AH, Xiao JF (2017) Mixed integer programming formulations for two-machine flow shop scheduling with an availability constraint. Arab J Sci Eng 43(3):1–12MATH

Titel: Two-machine flow shop scheduling with an operator non-availability period to minimize makespan
verfasst von: Dawei Li
Xiwen Lu
Publikationsdatum: 23.02.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00548-6

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+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2020

Maximum independent and disjoint coverage

A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice

Stabilizing social structure via modifying local patterns

Co-density and fractional edge cover packing

The quadratic cycle cover problem: special cases and efficient bounds

Local antimagic orientation of graphs