Fixed Parameter Tractability of scheduling dependent typed tasks with time windows

Claire Hanen (Sorbonne Université – LIP6)

Time:

Online, Zoom Meeting：

Meeting ID: 981 3280 2131

Passcode: 130657

This talk discusses the parameterized complexity of scheduling problems,

assuming precedence constraints, time windows and typed tasks resource

constraints. We recall the usual parameters used for scheduling problems

and focus on a parameter suitable for problems with time windows, the

pathwitdth of the underlying interval graph. We present three results

involving this parameter. First we show a fixed parameter tractable

(FPT) algorithm for a scheduling problem with unit processing times.

Then, a para-NP-Hardness result assuming arbitrary processing times and

finally we outline a FPT algorithm for this problem by considering two

parameters. Authors: Claire Hanen and Alix Munier-Kordon.