nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.10.2016

Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval

verfasst von: Imed Kacem, Hans Kellerer, Maryam Seifaddini

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2016

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 deal with the single machine scheduling problem with one non-availability interval to minimize the maximum lateness where jobs have positive tails. Two cases are considered. In the first one, the non-availability interval is due to the machine maintenance. In the second case, the non-availability interval is related to the operator who is organizing the execution of jobs on the machine. The contribution of this paper consists in an improved fully polynomial time approximation scheme (FPTAS) for the maintenance non-availability interval case and the elaboration of the first FPTAS for the operator non-availability interval case. The two FPTASs are strongly polynomial.

Vorheriger Artikel A diagnosis algorithm by using graph-coloring under the PMC model

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

Nur mit Berechtigung zugänglich

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

Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11:42–47MathSciNetCrossRefMATH

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

Dessouky MI, Margenthaler CR (1972) The one-machine sequencing problem with early starts and due dates. AIIE Trans 4(3):214–222CrossRef

Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discret Appl Math 3:313–318CrossRefMATH

He Y, Zhong W, Gu H (2006) Improved algorithms for two single machine scheduling problems. Theor Comput Sci 363:257–265MathSciNetCrossRefMATH

Ibarra O, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22:463–468MathSciNetCrossRefMATH

Kacem I (2009) Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J Comb Optim 17(2):117–133MathSciNetCrossRefMATH

Kacem I, Kellerer H (2014) Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times. Discret Appl Math 164(1):154–160MathSciNetCrossRefMATH

Kubzin MA, Strusevich VA (2006) Planning machine maintenance in two machine shop scheduling. Oper Res 54:789–800CrossRefMATH

Lee CY (1996) Machine scheduling with an availability constraints. J Glob Optim 9:363–384CrossRef

Qi X (2007) A note on worst-case performance of heuristics for maintenance scheduling problems. Discret Appl Math 155:416–422MathSciNetCrossRefMATH

Qi X, Chen T, Tu F (1999) Scheduling the maintenance on a single machine. J Oper Res Soc 50:1071–1078CrossRefMATH

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

Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23:116–127MathSciNetCrossRefMATH

Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15MathSciNetCrossRefMATH

Yuan JJ, Shi L, Ou JW (2008) Single machine scheduling with forbidden intervals and job delivery times. Asia-Pac J Oper Res 25(3):317–325MathSciNetCrossRefMATH

Titel: Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
verfasst von: Imed Kacem
Hans Kellerer
Maryam Seifaddini
Publikationsdatum: 01.10.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9924-4

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 3/2016

Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs

On strongly planar not-all-equal 3SAT

A combinatorial proof for the circular chromatic number of Kneser graphs

First-Fit colorings of graphs with no cycles of a prescribed even length

A -choosable theorem on planar graphs

Signed total Roman domination in graphs