Our study considers a parallel machine scheduling problem defined by a set of non-preemptive jobs to be executed by identical machines. Each jobs has an integer release time, processing time and deadline. There are precedence relations between certain pairs of jobs. The objective is to find a feasible solution or to prove that no feasible solution exists. Branch-and-Bound methods are commonly considered for solving exactly scheduling problems. The Demeulemeester and Herroelen algorithm [1] is one of the most efficient Branch-and-Bound method to solve efficiently resource-constrained scheduling problem without release time and deadline. To our knowledge, there is no theoretical evaluation of the worst-case complexity of this algorithm.

This talk develops a new FPT algorithm inspired by Demeulemeester and Herroelen Branch and Bound method [1]. The idea here is to mix the efficiency in practice of this latter class of algorithms with the theoretical efficiency of FPT ones when the parameters are small. We prove that our new algorithm is a FPT with parameters i) pathwidth that is the maximum number of overlapping jobs with respect to their time windows and ii) the maximum processing time of a job.

Some experiments on random generated instances are also provided showing that the practical efficiency of our algorithm depends on the parameters but that the theoretical complexity is overestimated.

[1] Erik Demeulemeester and Willy Herroelen. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science, 38(12) :1803–1818, 1992.