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/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
