Treffer: Non-Preemptive Min-Sum Scheduling with Resource Augmentation

We give the first O(1)-speed O(1)-approximation polynomial-time algorithms for several nonpreemptive minsum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(1)-speed O(1)-approximations for the nonpreemptive scheduling problems • 1 | rj | � wjFj (weighted flow time), • 1 | rj | � Tj (total tardiness), • the broadcast version of 1 | rj | � wjFj, an O(1)-speed, 1-approximation for • 1 | rj | � U j (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for • 1 | rj | � wjTj (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.