Scheduling multiprocessor tasks on parallel processors with limited availability

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. © 2002 Elsevier Science B.V. All rights reserved.