A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines
classification
💻 cs.CC
cs.DS
keywords
schedulingmeannp-hardnessflowpreemptiveproblemproofstrong
read the original abstract
In the paper "The complexity of mean flow time scheduling problems with release times", by Baptiste, Brucker, Chrobak, D\"urr, Kravchenko and Sourd, the authors claimed to prove strong NP-hardness of the scheduling problem $P|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 NP-hardness for this problem.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.