nach oben

Journal of Combinatorial Optimization

Erschienen in:

12.07.2016

Minimizing the number of tardy jobs in two-machine settings with common due date

verfasst von: Federico Della Croce, Christos Koulamas, Vincent T’kindt

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.

Vorheriger Artikel Modified linear programming and class 0 bounds for graph pebbling

Nächster Artikel On minimally 2-connected graphs with generalized connectivity

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

Bar-Noy A, Guha S, Naor J, Schieber B (2001) Approximating the throughput of multiple machines in real-time scheduling. SIAM J Comput 31:331–352MathSciNetCrossRefMATH

Coffman EG, Leung JY-T, Ting DW (1978) Bin packing: maximizing the number of pieces packed. Acta Inform 9:263–271MathSciNetCrossRefMATH

Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287–326MathSciNetCrossRefMATH

Jozefowska J, Jurisch B, Kubiak W (1994) Scheduling shops to minimize the weighted number of late jobs. Oper Res Lett 16:277–283MathSciNetCrossRefMATH

Koulamas C, Kyparisis GJ (1998) Open shop scheduling to minimize late jobs. Nav Res Logist 45:525–532MathSciNetCrossRefMATH

Lin BMT, Kononov AV (2007) Customer order scheduling to minimize the number of late jobs. Eur J Oper Res 183:944–948CrossRefMATH

Lenté C, Liedloff M, Soukhal A, T’kindt V (2013) On an extension of the sort & search method with application to scheduling theory. Theor Comput Sci 511:13–22MathSciNetCrossRefMATH

Martello S, Toth P (2003) An exact algorithm for the two-constraint 0/1 knapsack problem. Oper Res 51:826–835MathSciNetCrossRefMATH

Megiddo N, Tamir A (1993) Linear time algorithms for some separable quadratic programming problems. Oper Res Lett 13:203–211MathSciNetCrossRefMATH

Murty KG (1976) Linear and combinatorial programming. Wiley, New YorkMATH

Woeginger GJ (2003) Exact algorithms for \(NP\)-hard problems: a survey. In: Juenger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization—Eureka! You shrink! (Lecture Notes in Computer Science), vol 2570, p 185–207

Titel: Minimizing the number of tardy jobs in two-machine settings with common due date
verfasst von: Federico Della Croce
Christos Koulamas
Vincent T’kindt
Publikationsdatum: 12.07.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0054-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 1/2017

Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields

Approximation algorithms for k-level stochastic facility location problems

Local ratio method on partial set multi-cover

An exact semidefinite programming approach for the max-mean dispersion problem

The minimum value of geometric-arithmetic index of graphs with minimum degree 2

A faster strongly polynomial time algorithm to solve the minimum cost tension problem