Complexity and approximation results for scheduling multiprocessor tasks on a ring

We study a multiprocessor task scheduling problem, in which each task requires a set of P processors with consecutiveness constraints to be executed. This occurs, for example, when multiple processors are interconnected by communication means, and the minimization of communication time may require the processors to be physically adjacent and each multiprocessor task to use only one subset of adjacent processors. In particular, we consider the case in which we have m processors arranged in a ring, and we want to find a schedule with minimum makespan. We investigate problem complexity, showing that the problem is N P-hard in almost all the possible cases, and provide an approximation algorithm that finds a feasible schedule whose makespan is not greater than two times the optimal value. (C) 2003 Elsevier B.V. All rights reserved.