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 notificationto a released job as to whether it is accepted into the system. In a stricter model, a scheduler must provide animmediate decisionfor an accepted job, selecting both the time interval and machine on which it will run. We examine an intermediate model in which a schedulerimmediately dispatchesan 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