Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

March 2024

1 participants
2 discussions

Pieter Smet (KU Leuven) | March 20 | Robustness in personnel rostering.
by Zdeněk Hanzálek 18 Mar '24

18 Mar '24

Dear scheduling researcher, We are delighted to announce the talk given by Pieter Smet (KU Leuven). The title is "Robustness in personnel rostering". The seminar will take place on Zoom on Wednesday, March 20 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09 <https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09> Meeting ID: 997 7514 8608 Passcode: 885832 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In this talk, we study the problem of generating personnel rosters that are robust with respect to disruptions caused by employee absenteeism. If an employee unexpectedly becomes absent, they must be replaced by another employee. This in turn may affect the working hours of other employees, creating an undesirable ripple effect that changes a large part of the roster. We investigate how making use of on-call duties may avoid such large perturbations. We begin by first introducing a metric to quantify the robustness of a roster, which is then used to generate sufficiently robust rosters. In the second part of this talk, we discuss the conditions under which machine learning can lead to better solutions. A novel methodology is presented to determine the minimum prediction performance required to outperform the non-data-driven rostering approach. The next talk in our series will be: André Rossi (Universite PSL) | April 3 | Maximizing stability of assembly line balancing schedules under uncertain task duration 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

Laurent Perron (Google France) | March 6 | The CP-SAT solver.
by Zdeněk Hanzálek 04 Mar '24

04 Mar '24

Dear scheduling researcher, We are delighted to announce the talk given by Laurent Perron (Google France). The title is "The CP-SAT solver". The seminar will take place on Zoom on Wednesday, March 6 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98573827806?pwd=UDRqdzYwbktrR29RQk02MVZqMUtkUT09 Meeting ID: 985 7382 7806 Passcode: 287789 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The CP-SAT solver is developed by the Operations Research team at Google and is part of the OR-Tools open-source optimization suite. It is an implementation of a purely integral Constraint Programming solver on top of a SAT solver using Lazy Clause Generation. It draws its inspiration from the chuffed solver, and from the CP 2013 plenary by Peter Stuckey on Lazy Clause Generation. The CP-SAT solver improves upon the chuffed solver in two main directions. First, it uses a simplex alongside the SAT engine. Second, it implements and relies upon a portfolio of diverse workers for its search part. The use of the simplex brings the obvious advantages of a linear relaxation on the linear part of the full model. It also started the integration of MIP technology into CP-SAT. This is a huge endeavour, as MIP solvers are mature and complex. It includes presolve -- which was already a part of CP-SAT --, dual reductions, specific branching rules, cuts, reduced cost fixing, and more advanced techniques. It also allows the tight integration of the research from the Scheduling on MIP community along with the most advanced scheduling algorithms. This has enabled breakthroughs in solving and proving hard scheduling instances of the Job-Shop problems and Resource Constraint Project Scheduling Problems. Using a portfolio of different workers makes it easier to try new ideas and to incorporate orthogonal techniques with little complication, except controlling the explosion of potential workers. These workers can be categorized along multiple criteria like finding primal solutions -- either using complete solvers, Local Search or Large Neighborhood Search --, improving dual bounds, trying to reduce the problem with the help of continuous probing. This diversity of behaviors has increased the robustness of the solver, while the continuous sharing of information between workers has produced massive speedups when running multiple workers in parallel. All in all, CP- SAT is a state-of-the-art solver, with unsurpassed performance in the Constraint Programming community, breakthrough results on Scheduling benchmarks (with the closure of many open problems), and competitive results with the best MIP solvers (on purely integral problems). The next talk in our series will be: Pieter Smet (KU Leuven) | March 20 | Robustness in personnel rostering. 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