Alix Munier Kordon
LIP6, Université Paris 12 Val de Marne

Minimizing the makespan for a UET bipartite graph on a single
processor with an integer precedence delay

Single and multiprocessors scheduling problems have been extensively
studied in the literature. Scheduling problems with precedence delays 
arise independently in several important applications and many 
theoretical studies were devoted to these problems: this class of 
problems was considered for resource-constrained scheduling problem. 
It was also studied as a relaxation for the job-shop problem. For 
computer systems, it corresponds to the basic pipelines scheduling 
problems.

An instance of a scheduling problem with precedence delays is usually
defined by a set of tasks T={1,..., n} with durations p_i, i in T, an 
oriented precedence graph G=(T,E) and integer delays d_ij >= 0, (i,j) 
in E. For every arc (i,j) in E, task j can be executed at least d_ij 
time units after the completion time of i. The number of processors 
is limited. The problem is to find a schedule minimizing the makespan, 
or other regular criteria. Using standard notations, the minimization 
of the makespan is denoted by Pm |prec, d_ij |Cmax.

In this talk, we suppose that the graph G is bipartite. We also consider 
that there is only one processor, that the duration of tasks is one and 
that the delays are the same for every arc. This problem is noted 
1|bipartite, d_ij=d, p_i=1|Cmax.

The complexity of this problem is a challenging question.
We proved that it is NP-Hard using a reduction from VERTEX SEPARATION. 
Then, we develop a non trivial polynomial algorithm if the degree of 
the tasks from one of the two sets is exactly $2$. Lastly, we provide an 
approximation algorithm for the problem with a performance ration equal 
to 3/2.