Non-preemptive min-sum scheduling with resource augmentation

Nikhil Bansal, Ho Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages614-624
Number of pages11
DOIs
StatePublished - 2007
Externally publishedYes
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Country/TerritoryUnited States
CityProvidence, RI
Period10/20/0710/23/07

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Non-preemptive min-sum scheduling with resource augmentation'. Together they form a unique fingerprint.

Cite this