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

2014/04/22 by Bellenguez-Morineau, Odile, Chrobak, Marek, Dürr, Christoph +1
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1404.5424

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 NP-hardness of the scheduling problem P|pmtn,r_j|∑ 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.

Related

• The Complexity of Mean Flow Time Scheduling Problems with Release Times
• Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time
• A note on the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner [2010]
• Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
• Faster Minimization of Total Weighted Completion Time on Parallel Machines