Preemptive multiprocessor task scheduling with release times and time windows

Classical scheduling theory assumed that a task may require for its processing only one processor at a time. This assumption is not obvious in the context of new parallel computer systems and parallel algorithms. In this work, we consider preemptive deterministic scheduling of multiprocessor tasks, each of which may require a set of processors at a time. In general, tasks may appear in the system in different moments of time. We will also consider the problem of scheduling such tasks in time windows on particular processors. The existence of low-order polynomial time algorithms for the above problems with C-max and L-max criteria will be analyzed. The general case of the problem can be solved using a linear programming approach.