Non-Preemptive Min-Sum Scheduling with Resource Augmentation
Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk R. Pruhs, Baruch Schieber, Clifford Stein · 2007
We give the first O(l)-speed O(l) approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(l)-speed O(l)-approximations for the non-preemptive scheduling problems; l|rj| SigmawjFj(weighted flow time), l |rj| SigmaTj(total tardiness), the broadcast version of 1 |rj| SigmawjFj, an O(I)-speed, 1-approximation for l |rj| Sigma U macrj(throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |rj| SigmawjTj(weighted tardiness). Our main contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.