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)) for each job i. The problem is denoted by P|M-j (type), prec, 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)), the maximum processing time of a task p(max) and the maximum slack of a task sl(max). This paper establishes that the problem is para-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), sl(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|M-j (type), prec, r(i), d(i) |Cmax and P|M-j (type), prec, r(i) |L-max are then derived using a binary search.

Automated summary

This paper investigates the feasible scheduling problem with precedence constraints and time intervals on limited resources. It shows that the problem is para-NP-complete and presents a fixed-parameter algorithm based on dynamic programming for solving the problem.