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

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)$$ ( 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 $$ P | M j ( t y p e ) , p r e c , r i , d i | ⋆ . Several parameters are considered: the pathwidth pw(I) of the interval graph I associated with the time intervals $$(r_i, d_i)$$ ( r i , d i ) , the maximum processing time of a task $$p_{\max }$$ p max and the maximum slack of a task $$s\ell _{\max }$$ s ℓ max . This paper establishes that the problem is para- $$\textsf{NP}$$ 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 })$$ 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\vert \mathcal{M}_j(type),prec,r_i,d_i\vert C_{\max }$$ P | M j ( t y p e ) , p r e c , r i , d i | C max and $$P\vert \mathcal{M}_j(type),prec,r_i\vert L_{\max }$$ P | M j ( t y p e ) , p r e c , r i | L max are then derived using a binary search.