Animation scientifique

We consider a single machine scheduling problem where each job $j$ is given a length $p_j$ (also called processing time), a release date $r_j$ (i.e., the date of first availability) and a deadline $d_j$. The corresponding decision problem asks whether there exists a schedule --- i.e, a function assigning a nonnegative start time to each job --- such that at most one job is processed at any time, and each job $j$ is processed within its availability window $[r_j, d_j)$. Despite being considered (and proved NP-complete) in the famous 1979 book ``Computers and Intractability'' by Garey and Johnson, its parameterized complexity has been thoroughly studied only recently.

In this talk, we present several parameterized complexity results for this problem obtained during my PhD thesis. We consider the interval representation defined by the job time windows $[r_j ,d_j)$. Taking inspiration from graph theory, we define the pathwidth of the scheduling instance, and we introduce a new parameter, which we call the proper level. For both parameters, we present a dynamic programming fixed-parameter algorithm. This paves the way for a more in-depth study of the parameterized complexity of scheduling problems.