Scheduling independent 2-processor tasks to minimize schedule length (Q796987): Difference between revisions

The problem considered in this paper is the deterministic scheduling of tasks on a set of identical processors. However, the model presented differs from the classical one by the requirement that certain tasks need more than one processor at a time for their processing. In the paper an O(n log n) algorithm is given for scheduling n preemtable tasks on m processors to minimize schedule length, when tasks are divided into two subsets. Each task from the first subset requires one processor at a time, and each task from the second subset requires two processors at a time for its processing.