Non-preemptive min-sum scheduling with resource augmentation

N. Bansal, H.L. Chan, R. Khandekar, K.R. Pruhs, C. Stein, B. Schieber

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    19 Citations (Scopus)

    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 languageEnglish
    Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07, Providence RI, USA, October 20-23, 2007)
    PublisherIEEE Computer Society
    Pages614-624
    ISBN (Print)0-7695-3010-9
    Publication statusPublished - 2007

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

    Cite this