Online competitive algorithms for maximizing weighted throughput of unit jobs

Abstract

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e / ( e - 1 ) ≈ 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edfα, whose competitive ratio on s-bounded instances is 2 - 2 / s + o ( 1 / s ). For 3-bounded instances its ratio is φ{symbol} ≈ 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s = 2, our proof gives a lower bound of 4 - 2 sqrt(2) ≈ 1.172. Also, in the 2-uniform case, we prove a lower bound of sqrt(2) ≈ 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 / ( 1 - ( frac(m, m + 1) )m )-competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases. © 2005 Elsevier B.V. All rights reserved.