Einzeltreffer — DigiBib

International audience ; In the paper “The complexity of mean flow time scheduling problems with release times”, by Baptiste, Brucker, Chrobak, Dürr, Kravchenko and Sourd, the authors claimed to prove strong NP -hardness of the scheduling problem P|pmtn,rj|∑Cj , namely multiprocessor preemptive scheduling where the objective is to minimize the mean flow time. We point out a serious error in their proof and give a new proof of strong NP -hardness for this problem.

Titel:	A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines
Autor/in / Beteiligte Person:	Bellenguez-Morineau, Odile ; Chrobak, Marek ; Dürr, Christoph ; Prot, Damien ; Systèmes Logistiques et de Production (SLP) ; Institut de Recherche en Communications et en Cybernétique de Nantes (IRCCyN) ; Mines Nantes (Mines Nantes)-École Centrale de Nantes (ECN)-Ecole Polytechnique de l'Université de Nantes (EPUN) ; Université de Nantes (UN)-Université de Nantes (UN)-PRES Université Nantes Angers Le Mans (UNAM)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-École Centrale de Nantes (ECN)-Ecole Polytechnique de l'Université de Nantes (EPUN) ; Université de Nantes (UN)-Université de Nantes (UN)-PRES Université Nantes Angers Le Mans (UNAM)-Centre National de la Recherche Scientifique (CNRS) ; Mines Nantes (Mines Nantes) ; University of California Riverside (UC Riverside) ; University of California (UC) ; Recherche Opérationnelle (RO) ; Laboratoire d'Informatique de Paris 6 (LIP6) ; Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
Link:	https://hal.science/hal-01154423 https://doi.org/10.1007/s10951-014-0380-2
Zeitschrift:	ISSN: 1094-6136, 2015
Veröffentlichung:	HAL CCSD ; Springer Verlag, 2015
Medientyp:	academicJournal
DOI:	10.1007/s10951-014-0380-2
Schlagwort:	Preemptive problems Identical machines Complexity Scheduling [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Sonstiges:	Nachgewiesen in: BASE Sprachen: English Collection: Archives ouvertes Hal IMT Atlantique Document Type: article in journal/newspaper Language: English Relation: hal-01154423; https://hal.science/hal-01154423

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.

A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines