Datum / čas
Date(s) - 01.02.
15:00 - 17:00

Kategorie ne Kategorie

Jacques Carlier (Sorbonne University)

Constructive and destructive bounds for the m-machine scheduling problem

February 1, 2023 at 15 CET

Join online or offline on our Youtube channel:

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

The abstract:
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.

Jacques Carlier  received the degrees of Computer Science in 1972 and Mathematics in 1974, MSc (OEA) in Computer Science in 1973, PhD (Doctorat de 3eme cycle) in Disjunctive Scheduling Problems in 1975 and PhD (Doctorat d’Etat) in Resource Constrained Scheduling in 1984, all from University of Paris VI. From 1974 to 1985 he was Assistant Professor at the same University. Since 1985 he is Professor at University of Technology of Compiegne. He is currently director of the MSc in Computer Science at the same university. His research interests include operations research and in particular, scheduling problems, reliability and routing in telecommunication networks.

The seminar is organized by Zdeněk Hanzálek (CIIRC CTU in Prague), Michael Pinedo (New York University) and Guohua Wan (Shanghai Jiao Tong).

Find full info and program at https://schedulingseminar.com/.