A note on -hardness of preemptive mean flow-time scheduling for parallel machines
Bellenguez Morineau Odile
Journal of Scheduling, 2015, 18(3): 299-304.
In the paper "The complexity of mean flow time scheduling problems with release times", by Baptiste, Brucker, Chrobak, Durr, Kravchenko and Sourd, the authors claimed to prove strong -hardness of the scheduling problem , 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 -hardness for this problem.
Scheduling; Complexity; Identical machines; Preemptive problems