Scheduling preemptable tasks on parallel processors with limited availability

It is well known that in the majority of cases the problem of preemptive ta sk scheduling on m parallel identical processors with the objective of mini mizing makespan can be solved in polynomial time. For example, for tree-lik e precedence constraints the algorithm of Muntz and Coffman can be applied. In this paper, this problem is generalized to cover the case of parallel p rocessors which are available in certain time intervals only. It will be sh own that this problem becomes NP-hard in the strong sense in case of trees and identical processors. If tasks form chains and are processed by identic al processors with a staircase pattern of availability, the problem can be solved in low-order polynomial time for C-max criterion, and a linear progr amming approach is required for L-max criterion. Network flow and linear pr ogramming approaches will be proposed for independent tasks scheduled on, r espectively, uniform and unrelated processors with arbitrary patterns of av ailability for schedule length and maximum lateness criteria. (C) 2000 Publ ished by Elsevier Science B.V. All rights reserved.