Datum / čas
Date(s) - 15.11.
15:00 - 17:00
Kategorie
Presenter – Claire Hanen (Sorbonne U., LIP6) Invited by – Zdeněk Hanzálek (CTU in Prague)
Fixed Parameter Tractability of scheduling dependent typed tasks with time windows
Nov 15, 2023 at 15 CET
Join online or offline on our Youtube channel: Scheduling seminar – YouTube
Abstract:
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.
Find full info and program at https://schedulingseminar.com/.