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)