Article ID: | iaor20043076 |
Country: | Netherlands |
Volume: | 149 |
Issue: | 2 |
Start Page Number: | 377 |
End Page Number: | 389 |
Publication Date: | Sep 2003 |
Journal: | European Journal of Operational Research |
Authors: | Drozdowski Maciej, Dell'Olmo Paolo, Baewicz Jacek, Przemysaw Mczka |
In this work we consider the problem of scheduling multiprocessor tasks on parallel processors available only in restricted intervals of time called time windows. The multiprocessor task model applies to modern production systems and parallel applications in which several processors can be utilized in parallel. Preemptable tasks are considered. Polynomial time algorithms are given in three cases: the case of maximum lateness criterion and a fixed number of processors, the case of schedule length criterion when tasks have various ready times and require either one or all processors, and in case of schedule length criterion when the sizes of the tasks are powers of 2.