We are delighted to announce the talk given by Jacques Carlier (Sorbonne
University).
The title is " Constructive and destructive bounds for the m-machine
scheduling problem ".
The seminar will take place on Zoom on Wednesday, February 1 at 14:00 UTC.
Join Zoom Meeting
https://cesnet.zoom.us/j/91663233347?pwd=SndKeS93bnRDdGRPWGtQUS9pWlZEUT09
Meeting ID: 916 6323 3347
Passcode: 218128
You can follow the seminar online or offline on our Youtube channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
The aim of this talk is to present some new results on constructive and
destructive bounds for the m-machine scheduling problem. Recently we
have characterized mathematically the three main constructive bounds
which are the preemptive bound, the energetic bound and the JPPS
makespan. These characterizations give insights to their similarities
and differences. It explains why these bounds are generally equal in
practice. Moreover our characterization of the energetic bound
introduced by Erschler, Lopez and Thuriot permits to build a 0(n
alpha(n) logn) ( alpha(n) Ackermann coefficient) checker. It is the best
one in literature. We have compared it to the checkers of Baptiste
Lepape and Nuijten (O(nsquare)) and to the checker of Ouellet and
Quimper (O(nlognlogn)). The checker of Baptiste, Lepape and Nuijten is
based on an identification of useful intervals and on incremental
evaluations of intervals energy. Ouellet and Quimper prove that the
energy matrix is a Monge matrix and evaluate the energy of some interval
thanks to a pre-calculated data structure based on range trees. We
characterize mathematically the useful intervals, then we use the data
structures introduced by Ouellet and Quimper and a nice algorithm for
partial Monge Matrix. Our checker is also the best one in practice in
literature, as it is confirmed by the numerical results we report. Work
in collaboration with Abderrahim Sahli, Antoine Jouglet1 and Eric Pinson.
The next talk in our series will be:
Vincent T'kindt (University of Tours) | February 15 | The Marriage of
Matheuristics and Scheduling.
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
