We consider the problem of scheduling a single resource non-preemptively in order to maximize its utilization. The delay of a job is equal to the gap between its arrival time and the last possible time at which it may be started while still meeting its deadline. We introduce an additional restriction that each job must be willing to accept a delay proportional to its job length. That is, we assume there is some constant w, such that any job of length |J| allows a delay of at least w|J|. This restriction is quite natural for admission control, as it seems reasonable that a job requesting 5 minutes of a resource might be willing to wait at least 10 seconds before beginning if necessary, whereas a job requesting 5 hours of time should be willing to handle a wait of 10 minutes instead.
Our results show that this additional requirement has dramatic effects
on the competitiveness of online algorithms. Without this
restriction, previous lower bounds show that no algorithm,
deterministic or randomized, can achieve any bounded competitiveness
for the problem when arbitrarily job lengths are allowed. We show
that for any w>0 a simple greedy algorithm is (2 + 1/w)-competitive,
and we give lower bounds showing that this is the best possible result
for a deterministic algorithm, even when all jobs have one of three
distinct lengths. In the special case where all jobs have the same
length, previous results give a tight bound of 2 on the
competitiveness for deterministic algorithms without a minimum delay.
We generalize these results, showing that the competitiveness for any
w>0 is exactly 1 + 1/(floor(w)+1). We also give tight bounds for
the case where jobs have one of two distinct lengths.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-10.ps.gz
DIMACS Home Page