Séminaire en format hybride au local 4488 du GERAD ou Zoom.
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)