Wednesday, September 22, 2021

[DMANET] [Scheduling seminar] Leah Epstein (University of Haifa) | September 29 | The benefit of preemption

We are delighted to announce the talk given by Leah Epstein (University
of Haifa).

The title is "The benefit of preemption".

The seminar will take place on Zoom on Wednesday, September 29 at 13:00 UTC.

Join Zoom Meeting
https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09
<https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09>

Meeting ID: 979 8935 6749
Passcode: 307940

You can follow the seminar online or offline on our Youtube channel as
well:

https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A

The abstract follows.

Given an input of a scheduling problem, any non-preemptive solution for
it can be used as a preemptive solution. Thus, the optimal cost of a
preemptive solution is not larger than that of an optimal non-preemptive
solution. As preemption comes at a cost in real-life applications, it is
of interest to find the worst-case ratio between the two costs. For a
given problem, the supremum ratio over all possible inputs of the ratio
between the two costs (of an optimal solution without preemption and an
optimal solution that possibly uses preemption) is called the power or
benefit of preemption. While many scheduling variants can be studied
with respect to this measure, we will focus on the cases of a single
machine, parallel identical machines, and uniformly related machines,
and we will discuss the objectives of makespan and total (weighted)
completion time. We will exhibit how one can benefit from preemption,
and we will analyze the resulting worst case ratios for several basic
models.

The next talk in our series will be given by

Federico Della Croce (DIGEP - Polito.it) | October 13 | The Longest
Processing Time Rule for Identical Parallel Machines Revisited.

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/
*
**********************************************************