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 \(\ell _{max}\) , and we complement the landscape of results in this field.
We prove that several special cases of the problem with either exact or minimum delays are para- \(\textsf{NP}\) -complete or \(\textsf{XNLP}\) -hard with respect to \(\ell _{max}\) . In particular, in the case of precedence chains and unit processing times, we establish that the problem is para- \(\textsf{NP}\) -complete with exact delays and \(\textsf{XNLP}\) -hard with minimum delays, while it is polynomial-time solvable with maximum delays. We then investigate the combination of \(\ell _{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 \(\textsf{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 \(\textsf{XNLP}\) -complete, even for unit processing time and equal delays, whereas it is in \(\textsf{FPT}\) for exact delays. Finally we consider problems with time windows, and propose a fixed-parameter tractable algorithm for problems with unbounded processing times, a general precedence graph and all types of delays, with respect to parameters \(\ell _{max}\) combined with the maximum slack of a task.
