# Parameterized Complexity of Single-machine Scheduling
with Precedence, Release Dates and Deadlines

Claire C. Hanen, Maher Mallem, Alix Munier-Kordon

<figure><img src="image_1.png" /></figure>

► To cite this version:

Claire C. Hanen, Maher Mallem, Alix Munier-Kordon. Parameterized Complexity of Single-machine Scheduling with Precedence, Release Dates and Deadlines. Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2021), Jun 2022, Bielle, Italy. hal-03834528

HAL Id: hal-03834528

https://hal.science/hal-03834528v1

Submitted on 19 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Parameterized Complexity of Single-machine Scheduling with Precedence, Release Dates and Deadlines

Claire Hanen * Maher Mallem (Speaker) † Alix Munier Kordon ‡

## 1 Introduction

Many scheduling problems, even seemingly basic ones such as $1|r_i|L_{max}$, have been proved strongly NP-hard [7] over the years. Upon reaching NP-hardness this quickly, it becomes difficult to establish anything deeper about these problems within the scope of classical complexity theory.

To answer this, parameterized complexity theory gives additional tools for a refined analysis of such hard scheduling problems. Given a parameter $k$ and denoting $n$ the input size, a problem is called *fixed-parameter tractable* (FPT) with respect to parameter $k$ if it can be solved in time $poly(n) \times f(k)$ with $f$ an arbitrary function [3]. The idea is to identify $k$ as the limiting property and give a polynomial time algorithm for all instances with a bounded value of $k$. When the studied problem is believed to not be FPT, the para-NP class is used as a parameterized version of NP: a problem is in para-NP with respect to parameter $k$ if there is a non-deterministic algorithm that solves it in time $poly(n) \times f(k)$ with $f$ an arbitrary function. In order to prove that a problem is para-NP-hard with respect to $k$, it is enough to prove that the un-parameterized problem is NP-hard for some fixed value of the parameter [4]. For example the *k-COLORING* graph problem is para-NP-hard with respect to the number $k$ of colors from knowing that the graph coloring problem is already NP-hard with $k = 3$ colors.

Several parameters have been considered for the analysis of the parameterized complexity of scheduling problems, like the maximum processing time $p_{max}$ [8] or the width of the precedence graph [2]. In the presence of time windows, recent papers considered parameters based on the structure of time intervals. Bodlaender and van der Wegen [1] addressed the single-machine scheduling of a set of chain like precedence constraints with delays between successive tasks, and each chain has its own time window (release time and deadline). They defined the *thickness* as the maximum number of overlapping intervals of chains and proved that the problem with minimum delays given in unary is W[2]-hard with respect to the

<footnote>*claire.hanen@lip6.fr. Sorbonne Université, CNRS, LIP6, F-75005 Paris, France and UPL, Université Paris Nanterre, F-92000 Nanterre, France</footnote>

<footnote>†maher.mallem@lip6.fr. Sorbonne Université, CNRS, LIP6, F-75005 Paris, France</footnote>

<footnote>‡alix.munier@lip6.fr. Sorbonne Université, CNRS, LIP6, F-75005 Paris, France</footnote>
thickness. Munier Kordon [9] developed an FPT algorithm for the decision problem $P|prec, p_j = 1, r_j, d_j|\star$. A star in the third field denotes here a decision problem. The parameter was the *pathwidth* $\mu$ of the interval graph induced by the time windows of the tasks, which equals the maximum number of overlapping time windows at any given time, minus one. An FPT algorithm with respect to the tuple of parameters $(\mu, p_{\max})$ has been provided in [5] for a problem with typed tasks of arbitrary processing times. This shows that the *pathwidth* $\mu$ is an interesting parameter to handle problems with time windows. In this work we consider several single-machine scheduling problems with release dates, deadlines and precedence relations with or without delays. We analyze the parameterized complexity of these problems with respect to the parameter $\mu$.

## 2 An FPT algorithm for $1|prec, r_j, d_j|\star$

In this section we consider the case where there are no delays. Related problems are $1|prec, r_i|C_{max}$ which is polynomial [6] whereas $1|r_i|L_{max}$ is strongly NP-hard [7]. This implies the NP-hardness of $1|prec, r_j, d_j|\star$, even without precedence constraints. It is also proved in [5] that $P2|r_j, d_j|\star$ is para-NP-complete with respect to the parameter $\mu$. We provide in this talk an FPT algorithm based only on the parameter $\mu$ for the single-machine case. We consider the sorted list $(u_\alpha)$ of end points of the jobs intervals $(r_i, d_i)$. The algorithm is based on a dynamic programming recurrence equation for $M_\alpha(X)$, the optimal makespan of a feasible schedule of a subset $X$ of jobs starting before $u_\alpha$. The parameter $\mu$ is used to enumerate the feasible subsets and the terms of the recurrence equation, leading to the following result:

**Theorem 1** $1|prec, r_j, d_j|\star$ and $1|prec, r_j, d_j|C_{max}$ are fixed-parameter tractable with respect to the parameter $\mu$. The complexity of the FPT algorithm is $O(n^2 \times 2^{2\mu})$.

## 3 Hardness results for $1|chains(\ell_{i,j}), p_j = 1, r_j, d_j|\star$

In this section, delays values $\ell_{i,j}$ are added to the precedence relations. Two cases are considered: EXACT-DELAYS for which delays are equal to the given values $\ell_{i,j}$ and MIN-DELAYS for which delays are required to be greater than or equal to the given values. In both cases we show that adding delays to the problem makes it para-NP complete with respect to parameter $\mu$ even with chains as precedence relations and unit-time jobs.

**Theorem 2** $1|chains(\ell_{i,j}), p_j = 1, r_j, d_j|\star$ is strongly NP-hard with *pathwidth* $\mu = 1$ in both EXACT-DELAYS and MIN-DELAYS cases.

This result complements the work done by Bodlaender and van der Wegen [1], which investigated the parameterized complexity of similar single-machine scheduling problems where time windows were given on chains instead of individual jobs
with respect to the thickness. We establish the para-NP hardness of our problems, a stronger result than W[2]-hardness. Moreover, our reductions are based on a trick of our own that do not require delays to be given in unary.

The EXACT-DELAYS case is proven using a reduction from 3-COLORING. We consider as many chains as there are nodes in the input graph. We dedicate one time segment of length three to each edge in the graph. The chain relative to a node $i \in [1..n]$ must schedule a job in all the time segments where node $i$ is part of the corresponding edge. Then two nodes sharing an edge have both a job to schedule in the same edge time segment of length three at some point. If we associate the position of jobs to color choices, then scheduling both jobs at different times corresponds to choosing different colors between nodes sharing an edge. Finally the exact delays are used to make the color choice consistent along each chain.

The MIN-DELAYS case is also reduced from 3-COLORING and is based on the same idea as the previous reduction. Around the beginning and the end of each chain, we add two gadgets that force all the delays along the edge time segments to be equal to their minimum value in any valid schedule. This allows us to keep the color choice consistent along each chain and make the reduction work the same way as in the EXACT-DELAYS case.

# 4 Conclusion

In this talk we provide a new FPT algorithm for a single-machine scheduling problem with release dates, deadlines and precedence relations with pathwidth $\mu$ as the parameter. When precedence delays are added, we show the para-NP-completeness with respect to parameter $\mu$ of a restrictive sub-case of the problem, which suggests that parameter $\mu$ alone is not enough to handle delays efficiently. Future work would investigate the maximum value of a delay $\ell_{max}$ as a parameter. It would be interesting to see whether an FPT algorithm exists for problem $1|prec(\ell_{i,j}), p_j = 1, r_j, d_j|C_{max}$ with respect to the tuple of parameters $(\mu, \ell_{max})$.

# References

[1] Hans L Bodlaender and Marieke van der Wegen. Parameterized complexity of scheduling chains of jobs with delays. arXiv preprint arXiv:2007.09023, 2020.

[2] Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, René van Bevern, and Gerhard J Woeginger. Precedence-constrained scheduling problems parameterized by partial order width. In *International conference on discrete optimization and operations research*, pages 105–120. Springer, 2016.

[3] R. Downey and M. Fellows. *Parameterized complexity*. Springer, 1999.

[4] J. Flum and M. Grohe. *Parameterized complexity theory*. Springer, 1998.
[5] Claire Hanen and Alix Munier-Kordon. Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. *Submitted*, 2021.

[6] E.L. Lawler. Optimal sequencing of a single machine subject to precedence constraints. *Management Sci.*, 19:544–546, 1973.

[7] J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. *Ann. of Discrete Math.*, 1:343–362, 1977.

[8] Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. *Mathematical Programming*, 154(1):533–562, 2015.

[9] Alix Munier Kordon. A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. *Discrete Applied Mathematics*, 290:1–6, 2021.