Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Preemptive scheduling with rejection

Hoogeveen, H., Skutella, M., & Woeginger, G. J. (2003). Preemptive scheduling with rejection. Mathematical Programming, 94, 361-374.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DC9-4 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DCA-2
Genre: Zeitschriftenartikel

Dateien

einblenden: Dateien
ausblenden: Dateien
:
HSW-MathProg-final.pdf (Verlagsversion), 126KB
 
Datei-Permalink:
-
Name:
HSW-MathProg-final.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Hoogeveen, Han, Autor
Skutella, Martin1, Autor           
Woeginger, Gerhard J., Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We consider the problem of preemptively scheduling a set of $n$ jobs on $m$ (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the $m$ machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is \apx-hard, and we design a $1.58$-approximation algorithm for it. All other considered variants are weakly \np-hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2004-06-152003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 201885
Anderer: Local-ID: C1256428004B93B8-0DAA99A7CBBA7B62C1256E20004335BB-HoogeveenSkutellaWoeginger2003
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Mathematical Programming
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 94 Artikelnummer: - Start- / Endseite: 361 - 374 Identifikator: ISSN: 0025-5610