Title: Online scheduling of equal-length jobs with hard deadlines
Speaker:  Guochuan Zhang
Zhejiang University

Date: Friday, March 14, 2008
Time 11-12PM
Venue: Room 3501, HKUST


Abstract:
We consider on-line scheduling of equal-length jobs on parallel
machines, where jobs arrive over time. Each job has a deadline which
becomes available upon its arrival. The goal is to maximize the number
of early jobs. Our main result is an algorithm with competitive ratio
decreasing to $e/(e-1)\approx 1.58$ as the number of machine
increases. This is the first algorithm with a competitive ratio better
than 2 for $m\geq 3$.

Our algorithm has an additional property called immediate decision: at
each time, it is immediately decided for each newly released job if it
will be scheduled, and if so, then also the time interval and machine
where it is scheduled is fixed and cannot be changed later. We show
that for two machines, no deterministic algorithm with immediate
decision is better than $1.8$-competitive; this lower bound shows that
our algorithm is optimal for $m=2$ in this restricted model.

Joint work with J. Ding, T. Ebenlendr, and J. Sgall