Presentation on YouTube.

Scheduling problems involving a set of dependent tasks with release dates and deadlines on a limited number of resources have been intensively studied. However, few parameterized complexity results exist for these problems.

The problem considered in this talk is the existence of a feasible schedule on $m$ identical machines with precedence constraints and time intervals ($r_i,d_i$) for each job $i$. The problem is denoted by $P|prec,r_i,d_i|*$.

Several parameters are considered: the path width $pw(I)$ of the interval graph associated to the time intervals ($r_i, d_i$), the maximum processing time of a task $p_{\max}$ and the maximum slack of a task $s_{\max}$. We established that the problem is para-NP-complete with respect to any of these parameters. We then provide a fixed-parameter algorithm for the problem parameterized by both parameters $pw(I)$ and $\min(p_{\max},s_{\max})$. It is based on a dynamic programming approach that builds a levelled graph which longest paths represent all the feasible solutions. Fixed-parameter algorithms for the problems $P|prec,r_i,d_i| C_{\max}$ and $P|prec,r_i\vert L_{\max}$ are then derived using a binary search.

(en collaboration avec Claire Hanen)