New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

On the identical coupled task scheduling problem

SpeakerGerd Finke

Co-authorNadia Brauner, Vassilissa Lehoux-Lebacque, G-SCOP, University Joseph Fourier, Grenoble, France

In the identical coupled task scheduling problem, multiple copies of a two-operation task, where the two operations are separated by a fixed distance, are to be processed on a single machine. The objective is to minimize the makespan in the finite case or the throughput rate in the cyclic case. We have recently established the polynomial complexity of the cyclic case, using as a compact representation of a schedule the concept of profiles. Then the optimal solutions can be described by only two different profile types, called type 1 (small idle) and type 2 (large idle).
We carry over this concept to the finite case, whose complexity status is unknown. We illustrate the increased combinatorics of this problem, where several profiles are now required for the description of the solutions. Then we give our motivation to conjecture that type 1 (small idle) problems are difficult to solve, whereas we show that type 2 (large idle) problems are polynomially solvable.