Article ID: | iaor20083762 |
Country: | United Kingdom |
Volume: | 10 |
Issue: | 6 |
Start Page Number: | 407 |
End Page Number: | 413 |
Publication Date: | Dec 2007 |
Journal: | Journal of Scheduling |
Authors: | Zhang Guochuan, Ye Deshi |
Keywords: | computational analysis: parallel computers |
We study an on-line parallel job scheduling problem, where jobs arrive one by one. A parallel job may require a number of machines for its processing at the same time. Upon arrival of a job, its processing time and the number of requested machines become known, and it must be scheduled immediately without any knowledge of future jobs. We present a 7-competitive on-line algorithm, which improves the previous upper bound of 12 by Johannes. Furthermore, we investigate a special case in which the largest processing time is known beforehand.