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\left| {rj} \right|\sum {w_j } F_j (weighted flow time), 1\left| {rj} \right|\sum {T_j } (total tardiness), the broadcast version of 1\left| {rj} \right|\sum {w_j } F_j, an O(1)-speed, 1-approximation for 1\left| {rj} \right|\sum {\bar U_j } (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1\left| {rj} \right|\sum {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.