A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows

This paper proves that the existence of a feasible schedule for a set of dependent tasks of unit execution times with release dates and deadlines on a limited number of processors is a fixed-parameter tractable problem. The parameter considered is the pathwidth of the interval graph associated with the time windows of the tasks. A fixed-parameter algorithm based on a dynamic programming approach is developed and proved to solve this decision problem. Fixed-parameter algorithms for the two classical problems P vertical bar prec, p(i) = 1, r(i)vertical bar C-max and P vertical bar prec, p(i) = 1, r(i)vertical bar L-max are then derived using a binary search. They are, as far as we know, the first fixed-parameter algorithms for these scheduling problems. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper proves that the feasible scheduling problem for dependent tasks is fixed-parameter tractable, with the pathwidth of the interval graph associated with the tasks' time windows as the considered parameter. A fixed-parameter algorithm based on dynamic programming is developed, and fixed-parameter algorithms for two classical scheduling problems are derived using binary search.