Top

Journal of Scheduling

Published in:

01-06-2015

A note on \({\mathbb {NP}}\)-hardness of preemptive mean flow-time scheduling for parallel machines

Authors: Odile Bellenguez-Morineau, Marek Chrobak, Christoph Dürr, Damien Prot

Published in: Journal of Scheduling | Issue 3/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 \({\mathbb {NP}}\)-hardness of the scheduling problem \(P|{\textit{pmtn}},r_j|\sum C_j\), 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 \({\mathbb {NP}}\)-hardness for this problem.

previous article Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization

next article Trading off due-date tightness and job tardiness in a basic scheduling model

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley.

Baptiste, P., Brucker, P., Chrobak, M., Dürr, C., Kravchenko, S. A., & Sourd, F. (2007). The complexity of mean flow time scheduling problems with release times. Journal of Scheduling, 10, 139–146.CrossRef

Brucker, P., & Kravchenko, S. A. (2004). Complexity of mean flow time scheduling problems with release dates. Technical report, Universität Osnabrück, Fachbereich Mathematik/Informatik, OSM Reihe P, Heft 251.

Du, J., Leung, J. Y.-T., & Young, G. H. (1990). Minimizing mean flow time with release time constraint. Theoretical Computer Science, 75, 347–355.CrossRef

McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6, 1–12.CrossRef

Title: A note on -hardness of preemptive mean flow-time scheduling for parallel machines
Authors: Odile Bellenguez-Morineau
Marek Chrobak
Christoph Dürr
Damien Prot
Publication date: 01-06-2015
Publisher: Springer US
Published in: Journal of Scheduling / Issue 3/2015
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-014-0380-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2015

Erratum to: Flow shops with WIP and value added costs

Trading off due-date tightness and job tardiness in a basic scheduling model

The impact of core precedences in a cyclic RCPSP with precedence delays

A note on the Coffman–Sethi bound for LPT scheduling

Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization

Energetic reasoning for energy-constrained scheduling with a continuous resource