Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control

Abstract: We consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. The slack of a job is equal to the gap between its release time and the last possible time at which it may be started while still meeting its deadline. When no restrictions are placed on either the length or slack of any job, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee any constant bound on the competitiveness of a resulting schedule. We examine a natural restriction in which each job must offer slack at least proportional to the job's processing time. Specifically, we will say that a problem instance has patience κ, if any job of length |J| has a slack of at least κ · |J|. We show that for any κ>0 a simple greedy algorithm is (2+1/κ)-competitive even when arbitrary job lengths are allowed. We give lower bounds showing that this is the best possible result for a deterministic algorithm even if all jobs have one of three distinct lengths. In the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ>0 is exactly 1+1/(⌊κ⌋+1). We also give tight bounds for the case where jobs have one of two distinct lengths.

Citation:

Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control

Michael H. Goldwasser

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, Maryland, Jan. 1999, pp. 396-405.

DOI:10.1145/314500.314592

Download as: [ pdf, pdf.gz, ps, ps.Z, ps.gz ]

Complete version later appeared in:

Journal of Scheduling, 6(2):183-211, 2003.

DOI:10.1023/A:1022994010777

Download as: [ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]