Complexity and approximation results for scheduling multiprocessor tasks on a ring

We studya multiprocessor task scheduling problem, in which each task requires a set of \mu processors with consecutiveness constraints to be executed. This occurs, for example, when multiple processors are interconnected bycommunication means, and the minimization of communication time mayrequire the processors to be physicallyadjacent and each multiprocessor task to use onlyone subset of adjacent processors. In particular, we consider the case in which we have m processors arranged in a ring, and we want to :nd a schedule with minimum makespan. We investigate problem complexity, showing that the problem is NP-hard in almost all the possible cases, and provide an approximation algorithm that :nds a feasible schedule whose makespan is not greater than two times the optimal value.