Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

January 2023

1 participants
2 discussions

Jacques Carlier (Sorbonne University) | February 1 | Constructive and destructive bounds for the m-machine scheduling problem
by Zdeněk Hanzálek 30 Jan '23

30 Jan '23

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

1 0

Lars Rohwedder (Maastricht University) | January 18 | Recent advances in flow time scheduling
by Zdeněk Hanzálek 16 Jan '23

16 Jan '23

Dear scheduling researcher, We are delighted to announce the talk given by Lars Rohwedder (Maastricht University). The title is " Recent advances in flow time scheduling ". The seminar will take place on Zoom on Wednesday, January 18 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96444131847?pwd=S0d6QnplZzh6S2t0dUMzYXcxSTVPZz09 Meeting ID: 964 4413 1847 Passcode: 537506 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Flow time is one of the most natural metrics to optimize in scheduling, but algorithmically it can be notoriously difficult to handle. I will talk about some recent advances in this topic, focusing on two results by myself and co-authors: a PTAS for the sum of weighted flow times on a single machine and improved approximation guarantees for parallel unrelated machines. The first result is enabled by a study of structural properties of constraints in a natural ILP formulation and the second result relies on a novel connection to discrepancy theory. The next talk in our series will be: Jacques Carlier (Sorbonne University) | February 1 | Constructive and destructive bounds for the m-machine scheduling problem. 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/

1 0