Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07, Providence RI, USA, October 20-23, 2007) |
Publisher | IEEE Computer Society |
Pages | 614-624 |
ISBN (Print) | 0-7695-3010-9 |
Publication status | Published - 2007 |