Room 206 (2nd floor, badged access)
12 juin 2025 - 14h00
Parameterized complexity of scheduling problems with precedence delays
par Maher Mallem de INRIA Lyon
invité(e) par David MONNIAUX
12 juin 2025 - 14h00
Parameterized complexity of scheduling problems with precedence delays
par Maher Mallem de INRIA Lyon
invité(e) par David MONNIAUX
Abstract: In scheduling problems it is commonplace to have a precedence graph, which asks that some tasks must be completed before starting some other task. Time constraints which relate a task to its predecessors - like a latency, a setup time or a countdown timer - can be modeled by precedence delays. Given a precedence constraint from task i to task j, having a minimum (resp. exact, maximum) precedence delay l_{i,j} implies that task j can only start at least (resp. exactly, at most) l_{i,j} time units after task i is completed. Although most scheduling problems featuring precedence delays have been shown to be NP-complete, the hardness proofs typically make use of unbounded delay values, which can be unrealistic in real-life applications.
In this talk, we investigate the computational complexity of scheduling problems with bounded precedence delays. This is achieved by studying the parameterized complexity of these problems with respect to parameter l_{max} - i.e. the maximum delay value which appears in the precedence graph given in the input. We show that most scheduling problems featuring precedence delays remain difficult with bounded l_{max}. Then we propose several parameter ideas which, when paired with a bounded l_{max} value, lead to promising dynamic programming parameterized algorithms.
