A Faster FPTAS for Weighted Completion Time SchedulingResearch Paper
Minimizing the total weighted completion time on parallel identical machines, written in three-field notation, is one of the basic objectives of scheduling theory. For a single machine, Smith's rule (1956) solves it exactly by ordering jobs by non-increasing ratio . Already for machines the problem is NP-hard (Bruno, Coffman and…