Claire Hanen (Sorbonne U., LIP6) | November 15 | Fixed Parameter Tractability of scheduling dependent typed tasks with time windows

Dear scheduling researcher, We are delighted to announce the talk given by Claire Hanen (Sorbonne U., LIP6). The title is " Fixed Parameter Tractability of scheduling dependent typed tasks with time windows ". The seminar will take place on Zoom on Wednesday, November 15 at 14:00 UTC. Please check carefully the summer/winter time change in your country. Join Zoom Meeting https://cesnet.zoom.us/j/98132802131?pwd=aUpBNHpxNkUvV0tZbTcxemZFK3JBUT09 Meeting ID: 981 3280 2131 Passcode: 130657 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. 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. The next talk in our series will be: Maria Elena Bruni (Uni of Calabria) | November 29 | Enhancing project resilience: a risk-averse approach to payment delays. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/
participants (1)
-
Zdeněk Hanzálek