TY - GEN

T1 - Non-preemptive min-sum scheduling with resource augmentation

AU - Bansal, Nikhil

AU - Chan, Ho Leung

AU - Khandekar, Rohit

AU - Pruhs, Kirk

AU - Schieber, Baruch

AU - Stein, Cliff

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2007

Y1 - 2007

N2 - 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 | rj | Σ wjFj (weighted flow time), | rj | Σ Tj (total tardiness), the broadcast version, of 1 | rj | Σ wjFj, an O(1)-speed, 1-approximation for 1 | rj | ΣŪj (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1 | r j | Σ wj Tj (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.

AB - 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 | rj | Σ wjFj (weighted flow time), | rj | Σ Tj (total tardiness), the broadcast version, of 1 | rj | Σ wjFj, an O(1)-speed, 1-approximation for 1 | rj | ΣŪj (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1 | r j | Σ wj Tj (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.

UR - http://www.scopus.com/inward/record.url?scp=46749116805&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46749116805&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2007.4389530

DO - 10.1109/FOCS.2007.4389530

M3 - Conference contribution

AN - SCOPUS:46749116805

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 614

EP - 624

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -