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 non-preemptive scheduling problems 1 | r_j | Σ w_jF_j (weighted flow time), | r_j | Σ T_j (total tardiness), the broadcast version, of 1 | r_j | Σ w_jF_j, an O(1)-speed, 1-approximation for 1 | r_j | ΣŪ_j (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1 | r _j | Σ w_j T_j (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.