Dear scheduling researcher,
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