Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper
Minimizing the sum of weighted completion times is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on identical parallel machines it is harder still, so the…