Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

October 2022

1 participants
2 discussions

Clifford Stein (Columbia Uni) | October 26 | Scheduling with Speed Predictions
by Zdeněk Hanzálek 24 Oct '22

24 Oct '22

Dear scheduling researcher, We are delighted to announce the talk given by Clifford Stein (Columbia Uni). The title is "Scheduling with Speed Predictions". The seminar will take place on Zoom on Wednesday, October 26 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09 <https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09> Meeting ID: 915 8132 9122 Passcode: 596335 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. We study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. In this talk, we give an algorithm that simultaneously achieves, for any x < 1, a 1 + x approximation when the predictions are accurate and a 2+ 2/x approximation when the predictions are not accurate. We also study special cases and evaluate our algorithms performance as a function of the error. Joint work with Eric Balanski, TingTing Ou and Hao-Ting Wei, all at Columbia. The next talk in our series will be: Alessandro Agnetis (University of Siena) | November 9 | Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems. 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

Greet Vanden Berghe (KU Leuven) | October 12 | Vehicle routing - a focus on heuristic design
by Zdeněk Hanzálek 10 Oct '22

10 Oct '22

Dear scheduling researcher, We are delighted to announce the talk given by Greet Vanden Berghe (KU Leuven). The title is "Vehicle routing - a focus on heuristic design". The seminar will take place on Zoom on Wednesday, October 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98337053582?pwd=WnFNYnVManFScEtaMEw2dE5GSnhJZz09 Meeting ID: 983 3705 3582 Passcode: 503069 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Local search-based algorithms have tended towards incorporating an ever-increasing number of heuristics for different problem classes, for example all sorts of vehicle routing generalizations. These heuristics range from all-purpose `swap' and `insert' to complicated made-to-measure operators. It has become a challenge to determine the impact of individual components on an algorithm's performance. In contrast to targeting generalizing problem extensions, it may be worthwhile to focus on a problem's core when designing a basic optimization heuristic. This talk introduces a recently published local search operator for vehicle routing problems: SISRs. This heuristic is unique insofar as it seeks to induce `spatial' and `capacity' slack during a ruin phase which may subsequently be exploited in an almost-greedy recreate phase. SISRs emerged after a dedicated attempt towards solving the vehicle routing problem's most basic special case, that is the `capacitated VRP'. SISRs' quality is validated by way of demonstrating its performance across a wide and diverse range of VRP generalizations. This confirms that the basic CVRP ruin & recreate heuristic is also effective when applied to more general vehicle problems, including fleet minimization, without the need to design additional problem-specific components. The next talk in our series will be: Clifford Stein (Columbia Uni) | October 26 | Scheduling with Speed Predictions. 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