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