THE COMPLEXITY OF SCHEDULING INDEPENDENT 2-PROCESSOR TASKS ON DEDICATED PROCESSORS

The author studies the complexity of nonpreemptive scheduling to minimize schedule length in a system in which some tasks must be processed on two dedicated processors at a time. He defined a class of two-processor tasks called W-tasks that the decision version of scheduling two-processor tasks with dedicated processors is strongly NP-complete even for the W-tasks only. Then he gives a complexity classification of subproblems by reducing the problem to an interval edge coloring and identifying its polynomially solvable subcases. Approximation algorithms that efficiently generate schedules and provide reasonable guarantees of 'near-optimality' are examined. Possible extensions of the scheduling of model are concerned.