Single machine scheduling with precedence constraints and bounded maximum delay value

Overview & Synopsis

We consider single machine scheduling problems minimizing the makespan when tasks are subject to precedence constraints with minimum, exact or maximum delays. We investigate the parameterized complexity of these problems with respect to the maximum delay value ℓ max , and we complement the landscape of results in this field.We prove that several special cases of the problem with either exact of minimum delays are para-NP-complete or XNLP-hard with respect to ℓ max , in contrast with the maximum delays case which seems easier. In particular, in the case of precedence chains and unit processing times, we establish that the problem is para-NP-complete with exact delays and XNLP-hard with minimum delays, while it is polynomial-time solvable with maximum delays.We then investigate the combination of ℓ max with the width of the precedence graph, and aim for drawing the line of fixed-parameter tractability for the three types of delays. We show that for those combined parameters, the maximum delays case is polynomial-time solvable for chains, whereas for minimum delays it is proved XNLP-complete even with unit processing times and only two available delay threshold values. If a general precedence graph is assumed, we also establish that the problem with minimum delays is XNLPcomplete, even for unit processing time and equal delays, whereas it is in FPT for exact delays.