Supervision : Claire HANEN

Parameterized Complexity and New Efficient Enumerative Schemes for RCPSP

Most scheduling problems are strongly NP-hard and have required intricate heuristics to be solved in practice. While yielding results short term, such heuristics rarely help to identify what fundamentally makes these problems difficult. Such analysis would uncover the similarities between seemingly different problems and facilitate strategy transfers. This would also prove useful whenever one would like to enrich a problem - for example by adding precedence relations or going from equal-length task to task of arbitrary time length.
One way to gather such knowledge is to go beyond classical complexity theory and consider parameterized complexity theory. Given a problem P we choose parameter k as some property of the input like the number of machines or the width of the precedence graph (if there is one). Depending on problem P and parameter k either, we design algorithms which are fixed-parameter tractable with respect to k (i.e. which operate in time f(k) x poly(n) with f an arbitrary computable function), or we show that P remains hard even when k is small (typically via a reduction from a well-known difficult parameterized problem in the same manner as an NP-hardness proof). Then the set of parameters for which problem P is fixed-parameter tractable can be interpreted as a footprint. By comparing it to the set of working parameters from another NP-hard problem P', one could infer whether P is ’equivalent’ to P', ’strictly harder’ than P', or if both problems are difficult for different reasons.
In this thesis we study the parameterized complexity of the Resource-Constrained Project Scheduling Problem (RCPSP) and its subproblems, possibly enhanced with job time windows and precedence delays. With precedence delays we consider parameter l_max - i.e. the maximum delay value appearing in the input - in the case of minimum delays, exact delays and the lesser studied maximum delays. For all delay types, we show that scheduling unit-time jobs on a single machine with a single available delay value is hard even with small l_max. This suggests that another property of the problem has to be bounded in order to deal with precedence delays.
This motivates the integration of job time windows to problems featuring precedence delays in order to broaden available parameter choices. We consider two parameters which have shown recent success in the literature. Namely slack ? - i.e. the maximum difference between the time window length of a job and its processing time - and pathwidth µ - i.e. the maximum number of job time windows which can include the same time unit. We also introduce a new parameter, the proper level q, which is defined as the maximum number of job time windows which can strictly include on both ends another job time window. We obtain several fixed-parameter tractable algorithms and set multiple hardness results with respect to these parameters, both with or without precedence delays. We also consider various other scheduling parameters in order to give a more complete view of the parameterized landscape of RCPSP and its subproblems.

2022-2024 Publications

• 2024
  • M. Mallem : “Parameterized Complexity and New Efficient Enumerative Schemes for RCPSP”, thesis, phd defence 10/11/2024, supervision Hanen, Claire (2024)
  • M. Mallem, C. Hanen, A. Munier‑Kordon : “A New Structural Parameter on Single Machine Scheduling with Release Dates and Deadlines”, International Symposium on combinatorial optimization 2024, vol. 14594, Lecture Notes in Computer Science, Tenerife (Canaries), Spain, pp. 205-219, (Springer Nature Switzerland) (2024)
• 2022
  • M. Mallem, C. Hanen, A. Munier‑Kordon : “Scheduling coupled tasks with time windows: a parameterized complexity analysis”, (2022)
  • M. Mallem, C. Hanen, A. Munier Kordon : “Parameterized complexity of a parallel machine scheduling problem”, International Symposium on Parameterized and Exact Computation (IPEC), Postdam, Germany (2022)
  • C. Hanen, M. Mallem, A. Munier‑Kordon : “Parameterized Complexity of Single-machine Scheduling with Precedence, Release Dates and Deadlines”, Models and Algorithms for Planning and Scheduling, Biella, Italy (2022)
  • M. Mallem : “Parameterized complexity of a single machine scheduling problem”, 23^e congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne - Lyon, France (2022)