Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines

Abstract

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. This paper studies the existence of a feasible schedule for a typed task system with precedence constraints and time intervals $(r_i,d_i)$ for each job i. The problem is denoted by $P\vert \mathcal{M}_j(type),prec,r_i,d_i\vert \star$. Several parameters are considered: the pathwidth pw(I) of the interval graph I associated with the time intervals $(r_i, d_i)$, the maximum processing time of a task $p_{\max }$ and the maximum slack of a task $s\ell _{\max }$. This paper establishes that the problem is para-$\textsf{NP}$-complete with respect to any of these parameters. It then provides a fixed-parameter algorithm for the problem parameterized by both parameters pw(I) and $\min (p_{\max },s\ell _{\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\vert \mathcal{M}_j(type),prec,r_i,d_i\vert C_{\max }$ and $P\vert \mathcal{M}_j(type),prec,r_i\vert L_{\max }$ are then derived using a binary search.