- Scheduling seminar - list.iid.ciirc.cvut.cz

Christoph Dürr (Sorbonne Uni)| December 8 | Three models for scheduling under explorable uncertainty
by Zdeněk Hanzálek 06 Dec '21

06 Dec '21

Dear scheduling researcher, We are delighted to announce the talk given by Christoph Dürr <http://www.lip6.fr/Christoph.Durr> (Sorbonne Uni). The title is "Three models for scheduling under explorable uncertainty". The seminar will take place on Zoom on Wednesday, December 8 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94434410356?pwd=SWlmUElObjhtQWZCcm9PZGw5TTVnZz09 <https://cesnet.zoom.us/j/94434410356?pwd=SWlmUElObjhtQWZCcm9PZGw5TTVnZz09> Meeting ID: 944 3441 0356 Passcode: 040955 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We consider a single machine scheduling problem, where every job has a processing time and a priority weight and the objective is to minimize the total weighted sum of completion times. The novelty is that the job characteristics are initially given in an imprecise manner to the algorithm. Tests can be performed for chosen jobs to learn their precise values, allowing for a better ordering of the jobs in the schedule. These tests however take some time, delaying the subsequent schedule. The algorithm needs to produce a schedule consisting of executions of all jobs and tests of some jobs. We will present three different models that have been studied in this context, as well as the results obtained for each of them. The talk covers papers authored by Levi, Magnanti and Shaposhnik, by C.D., Thomas Erlebach, Nicole Megow, Julie Meißner, and by Fanny Dufossé, C.D., Noël Nadal, Denis Trystram and Óscar C. Vásquez. The next talk in our series will be given by Rubén Ruiz (UP de València)| December 22| State-of-the-art flowshop scheduling heuristics: Dos and Don'ts 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

Michel Gendreau (Polytech Montréal) | November 24 | Tabu search for the time-dependent vehicle routing problem with time windows on a road network
by Zdeněk Hanzálek 22 Nov '21

22 Nov '21

Dear scheduling researcher, We are delighted to announce the talk given by Michel Gendreau (Polytech Montréal). The title is "Tabu search for the time-dependent vehicle routing problem with time windows on a road network". The seminar will take place on Zoom on Wednesday, November 24 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94687225692?pwd=SWVESXR6djcvWkpxeUc3a0xiLzVNQT09 Meeting ID: 946 8722 5692 Passcode: 557044 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Travel times inside cities often vary quite a lot during a day and significantly impact the duration of delivery routes. Some authors have proposed time-dependent (TD) variants of several vehicle routing problems (VRPs), including the VRP with time windows (VRPTW). In most papers, time-dependency is defined on customer-based graphs. Thus, a major impact of travel time variations is missed: in an urban environment, not only do travel times change, but also the paths used to travel from one customer to another. To address this issue, we work directly with the road network and consider travel time (or travel speed) variations on each road segment. We present a solution approach, based on tabu search, for a TDVRPTW in which travel speeds are associated with segments in the road network. Computational results on instances with up to 200 nodes and 580 arcs are reported and assessed. (Joint work with Maha Gmira, Andrea Lodi, and Jean-Yves Potvin). The next talk in our series will be given by Christoph Dürr (Sorbonne Uni)| December 8 | Three models for scheduling under explorable uncertainty 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

Carlo Mannino (SINTEF & Oslo Uni.) | November 10 | Train Scheduling: Models, decomposition methods and practice.
by Zdeněk Hanzálek 08 Nov '21

08 Nov '21

Dear scheduling researcher, We are delighted to announce the talk given by Carlo Mannino (SINTEF & Oslo Uni.). The title is "Train Scheduling: Models, decomposition methods and practice". The seminar will take place on Zoom on Wednesday, November 10 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95159122899?pwd=R3IrUUNuUi9IV09Cejczb0FDS0loQT09 <https://cesnet.zoom.us/j/95159122899?pwd=R3IrUUNuUi9IV09Cejczb0FDS0loQT09> Meeting ID: 951 5912 2899 Passcode: 786508 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Train scheduling is one of the most critical planning tasks required to run a railway, with most rail operators and managers having large departments devoted to this task. Depending on the time scale, we have two main scheduling problems. At the strategic and tactical levels, the train timetabling problem consists in finding feasible, robust schedules that are usable for months or years into the future. At the operational level, we have the train re-scheduling problem, where one wants to schedule trains in real-time in order to tackle deviations from the original timetable, minimizing delays and knock-on effects. Both problems share a common core-model, which is a job-shop scheduling model with no-wait and blocking constraints. The core problem can be modeled as a disjunctive program. After an illustration of the train scheduling application, I will present a basic MILP formulation for the disjunctive program. It turns out, however, that even small to medium size real-life instances cannot be solved by simply instantiating this formulation and invoking a state-of-the-art MILP solver. Next, therefore, I will go through two recent reformulations, which allow us to significantly increase the size of tractable instances. The first is obtained from the classical Benders' reformulation by strengthening its standard constraints. The second is often referred to as "Logic Benders' Reformulation" and exploits a natural, spatial decomposition of the railway network. I will finally show the strong link between these reformulations. I will conclude the talk by presenting a practical application of the described approaches to a traffic management system controlling trains in the greater Oslo region network. The system is currently undergoing a field-test campaign at Oslo control center. The next talk in our series will be given by Michel Gendreau (Polytech Montréal) | November 24 | Tabu search for the time-dependent vehicle routing problem with time windows on a road network. 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

Benjamin Moseley (Carnegie Mellon) | October 27 | Machine Learning for Scheduling
by Zdeněk Hanzálek 25 Oct '21

25 Oct '21

Dear scheduling researcher, We are delighted to announce the talk given by Benjamin Moseley <http://www.andrew.cmu.edu/user/moseleyb/> (Carnegie Mellon). The title is "Machine Learning for Scheduling". The seminar will take place on Zoom on Wednesday, October 27 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96553570741?pwd=ZkcwUk1IZjM1R2xDSkNQUWtYOHNVdz09 <https://cesnet.zoom.us/j/96553570741?pwd=ZkcwUk1IZjM1R2xDSkNQUWtYOHNVdz09> Meeting ID: 965 5357 0741 Passcode: 705618 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. This talk will discuss a model for augmenting algorithms with useful predictions that go beyond worst-case bounds on the algorithm performance. The model ensures predictions are formally learnable and instance robust. Learnability guarantees that predictions can be efficiently constructed from past data. Instance robustness formally ensures a prediction is robust to modest changes in the problem input. This talk will discuss predictions that satisfy these properties for scheduling and resource augmentation. Algorithms developed break through worst-case barriers with accurate predictions and have a graceful degradation in performance when the error in the predictions grows. The next talk in our series will be given by Carlo Mannino (SINTEF & Oslo Uni.) | November 10 | Train Scheduling: Models, decomposition methods and practice. 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

Federico Della Croce (DIGEP - Polito.it) | October 13 | The Longest Processing Time Rule for Identical Parallel Machines Revisited
by Zdeněk Hanzálek 11 Oct '21

11 Oct '21

Dear scheduling researcher, We are delighted to announce the talk given by Federico Della Croce (DIGEP - Polito.it). The title is "The Longest Processing Time Rule for Identical Parallel Machines Revisited". The seminar will take place on Zoom on Wednesday, October 13 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95567469894?pwd=cDcyZGRWaTVRTVptOEUvNlIrTUpOZz09 <https://cesnet.zoom.us/j/95567469894?pwd=cDcyZGRWaTVRTVptOEUvNlIrTUpOZz09> Meeting ID: 955 6746 9894 Passcode: 138314 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We consider the P||Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines to minimize makespan. We revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969. LPT requires sorting jobs in non-ascending order of processing times and then assigning one job at a time to the machine whose load is smallest so far. We provide new insights into LPT and discuss the approximation ratio of a modification of LPT that improves Graham’s bound. We use linear programming to analyze the approximation ratio of our approach. This performance analysis can be seen as a valid alternative to formal proofs based on analytical derivation. Also, we derive from the proposed approach an O(n log n) time complexity heuristic called SLACK. The heuristic splits the sorted job set in tuples of m consecutive jobs (1,...,m; m+1,...,2m; etc.) and sorts the tuples in non-increasing order of the difference (SLACK) between the largest and smallest job in the tuple. Given this new ordering of the job set, list scheduling is applied. This approach strongly outperforms LPT on benchmark literature instances and is competitive with more involved approaches such as COMBINE and LDM. The next talk in our series will be given by Benjamin Moseley <http://www.andrew.cmu.edu/user/moseleyb/> (Carnegie Mellon) | October 27 | Machine Learning for 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

Leah Epstein (University of Haifa) | September 29 | The benefit of preemption
by Zdeněk Hanzálek 22 Sep '21

22 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Leah Epstein (University of Haifa). The title is "The benefit of preemption". The seminar will take place on Zoom on Wednesday, September 29 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09 <https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09> Meeting ID: 979 8935 6749 Passcode: 307940 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Given an input of a scheduling problem, any non-preemptive solution for it can be used as a preemptive solution. Thus, the optimal cost of a preemptive solution is not larger than that of an optimal non-preemptive solution. As preemption comes at a cost in real-life applications, it is of interest to find the worst-case ratio between the two costs. For a given problem, the supremum ratio over all possible inputs of the ratio between the two costs (of an optimal solution without preemption and an optimal solution that possibly uses preemption) is called the power or benefit of preemption. While many scheduling variants can be studied with respect to this measure, we will focus on the cases of a single machine, parallel identical machines, and uniformly related machines, and we will discuss the objectives of makespan and total (weighted) completion time. We will exhibit how one can benefit from preemption, and we will analyze the resulting worst case ratios for several basic models. The next talk in our series will be given by Federico Della Croce (DIGEP - Polito.it) | October 13 | The Longest Processing Time Rule for Identical Parallel Machines Revisited. 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

Nicholas G. Hall (The Ohio State Uni) | September 15 | Dynamic Opponent Choice in Tournaments
by Zdeněk Hanzálek 13 Sep '21

13 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Nicholas G. Hall (The Ohio State University). The title is "Dynamic Opponent Choice in Tournaments". The seminar will take place on Zoom on Wednesday, September 15 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09 <https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09> Meeting ID: 991 8064 1475 Passcode: 994980 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We propose an alternative design for tournaments that use a preliminary stage, followed by several rounds of single elimination play. Most U.S. major sports, for example, are organized in this way. However, the conventional "bracket" design of these tournaments suffers from several deficiencies. First, top ranked players randomly incur unfortunate matchups against other players, which introduces an unnecessary element of luck. Second, as documented in the tournament design literature, various reasonable criteria such as stronger ranked players having a higher probability of winning, are not satisfied. Third, the probability that the top two players meet is not maximized. Fourth, there is the widely observed issue of shirking at the preliminary stage, where a player loses deliberately to obtain an easier path through the tournament. Finally, the use of a conventional fixed bracket fails to allow players to consider information that develops during the tournament, such as injuries to other players. To address all these issues, we allow higher ranked players at the single elimination stage to choose their next opponent at each round. We allow each player's ranking either to remain static, or to improve from beating a higher ranked player. Using data from 1,902 men's professional tennis tournaments from 2001-2016, we demonstrate the reasonableness of the results obtained. We also perform sensitivity analysis for the effect of increasing irregularity in the pairwise win probability matrix on three traditional performance measures. Finally, we show that our opponent choice design reduces shirking, and could have eliminated it in some notorious situations. In summary, compared with the conventional design, the opponent choice design provides higher probabilities that the best player wins and also that the two best players meet, reduces shirking, and performs well for preservation of ranking. The next talk in our series will be given by Leah Epstein (University of Haifa) | September 29 | The benefit of preemption. 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

Nicholas G. Hall (The Ohio State Uni) | September 15 | Dynamic Opponent Choice in Tournaments
by Zdeněk Hanzálek 01 Sep '21

01 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Nicholas G. Hall (The Ohio State University). The title is "Dynamic Opponent Choice in Tournaments". The seminar will take place on Zoom on Wednesday, September 15 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09 <https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09> Meeting ID: 991 8064 1475 Passcode: 994980 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We propose an alternative design for tournaments that use a preliminary stage, followed by several rounds of single elimination play. Most U.S. major sports, for example, are organized in this way. However, the conventional "bracket" design of these tournaments suffers from several deficiencies. First, top ranked players randomly incur unfortunate matchups against other players, which introduces an unnecessary element of luck. Second, as documented in the tournament design literature, various reasonable criteria such as stronger ranked players having a higher probability of winning, are not satisfied. Third, the probability that the top two players meet is not maximized. Fourth, there is the widely observed issue of shirking at the preliminary stage, where a player loses deliberately to obtain an easier path through the tournament. Finally, the use of a conventional fixed bracket fails to allow players to consider information that develops during the tournament, such as injuries to other players. To address all these issues, we allow higher ranked players at the single elimination stage to choose their next opponent at each round. We allow each player's ranking either to remain static, or to improve from beating a higher ranked player. Using data from 1,902 men's professional tennis tournaments from 2001-2016, we demonstrate the reasonableness of the results obtained. We also perform sensitivity analysis for the effect of increasing irregularity in the pairwise win probability matrix on three traditional performance measures. Finally, we show that our opponent choice design reduces shirking, and could have eliminated it in some notorious situations. In summary, compared with the conventional design, the opponent choice design provides higher probabilities that the best player wins and also that the two best players meet, reduces shirking, and performs well for preservation of ranking. The next talk in our series will be given by Leah Epstein (University of Haifa) | September 29 | The benefit of preemption. 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

Andrea Schaerf (University of Udine) | July 7 | Educational Timetabling: Problems, Benchmarks, Algorithms, and Practical Issues
by Zdeněk Hanzálek 01 Jul '21

01 Jul '21

Dear scheduling researcher, We are delighted to announce the talk given by Andrea Schaerf <http://www.dpia.uniud.it/schaerf/> (University of Udine). The title is "Educational Timetabling: Problems, Benchmarks, Algorithms, and Practical Issues". The seminar will take place on Zoom on Wednesday, July 7 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98579414742?pwd=enQxM2wveUowQ3BZenB1QURKVStadz09 <https://cesnet.zoom.us/j/98579414742?pwd=enQxM2wveUowQ3BZenB1QURKVStadz09> Meeting ID: 985 7941 4742 Passcode: 361848 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Educational timetabling problems consist in scheduling a sequence of events (lectures, seminars, or exams) involving teachers and students in a prefixed period of time, satisfying a set of constraints of various types. In this talk, we critically review different formulations, public datasets, and search methods. In particular, we illustrate local search methods, their parameter tuning procedure, and their results. Finally, we discuss practical issues involved in the actual solution of timetabling problems. The next talk in our series will be in September, stay tuned. 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

Mike Carter (University of Toronto) | June 23 | Challenges in Healthcare Scheduling Applications
by Zdeněk Hanzálek 21 Jun '21

21 Jun '21

Dear scheduling researcher, We are delighted to announce the talk given by Mike Carter <https://che.utoronto.ca/professor-michael-w-carter/> (University of Toronto). The title is " Challenges in Healthcare Scheduling Applications". The seminar will take place on Zoom on Wednesday, June 23 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93477049829?pwd=aE1lVjFyS1ZpQkdxRno2cVptSVdqUT09 <https://cesnet.zoom.us/j/93477049829?pwd=aE1lVjFyS1ZpQkdxRno2cVptSVdqUT09> Meeting ID: 934 7704 9829 Passcode: 866135 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In the immortal words of Monty Python, “… and now for something completely different!” Over the past three decades, I have spent much of my time working on practical healthcare applications. Typically, the projects are done with healthcare collaborators. Virtually all of the scheduling problems are highly stochastic, and scheduling approaches focus on managing variability. In this talk, I will describe several healthcare applications including: diagnostic imaging, cancer treatment (chemotherapy and radiation), nurse/physician scheduling, surgical scheduling, 911 call centres, home care routing, medical resident scheduling and primary care appointments (e.g. advanced access). In each case, I will describe the underlying uncertainties and briefly review recent approaches. The next talk in our series will be given by Andrea Schaerf (University of Udine) | July 7 | Educational Timetabling: Problems, Benchmarks, Algorithms, and Practical Issues. 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