Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput

by David P. Bunde and Michael H. Goldwasser

Abstract:

We consider online, nonpreemptive scheduling of equal-length jobs on parallel machines. Jobs have arbitrary release times and deadlines and a scheduler's goal is to maximize the number of completed jobs. This problem has been previously studied under two distinct models. In the first, a scheduler must provide immediate notification to a released job as to whether it is accepted into the system. In a stricter model, a scheduler must provide an immediate decision for an accepted job, selecting both the time interval and machine on which it will run. We examine an intermediate model in which a scheduler immediately dispatches an accepted job to a machine, but without committing it to a specific time interval. We present a natural algorithm that is optimally competitive for m=2. For the special case of unit-length jobs, it achieves competitive ratios for m ≥ 2 that are strictly better than lower bounds for the immediate decsion model.


Citation:
Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput
David P. Bunde and Michael H. Goldwasser
Proceedings of the Twelfth Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Bergen, Norway, volume 6139 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), Jun. 2010, pp. 346-358.
Download as: [ pdf ]


Michael Goldwasser