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

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

Jinjiang Yuan (Zhengzhou Uni) | June 9 | Updated complexity results in single-machine primary-secondary scheduling for minimizing two regular criteria
by Zdeněk Hanzálek 07 Jun '21

07 Jun '21

Dear scheduling researcher, We are delighted to announce the talk given by Jinjiang Yuan (Zhengzhou Uni). The title is "Updated complexity results in single-machine primary-secondary scheduling for minimizing two regular criteria". The seminar will take place on Zoom on Wednesday, June 9 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96998490212?pwd=Zm5QTXdTcnYyeVh5NytCb3NvNUpmUT09 <https://cesnet.zoom.us/j/96998490212?pwd=Zm5QTXdTcnYyeVh5NytCb3NvNUpmUT09> Meeting ID: 969 9849 0212 Passcode: 556764 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 primary-secondary scheduling problem, we have a primary scheduling criterion and a secondary scheduling criterion. The goal of the problem is to find a schedule which minimizes the second criterion, subject to the restriction that the primary criterion is minimized. Lee and Vairaktarakis [LV1993] presented a comprehensive review for the computational complexity of the single-machine primary-secondary scheduling problems, where all the jobs are released at time zero. When both of the two criteria are regular, more than twenty problems were posed as open in [LV1993]. This talk will report the research progress of these open problems. The next seminar in our series will be given by Mike Carter <https://che.utoronto.ca/professor-michael-w-carter/> (Uni of Toronto) "Challenges in Healthcare Scheduling Applications" and it will be held on June 23 at 13:00 UTC. 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

Erik Demeulemeester (KU Leuven) | May 26 | On the State of the Art in Proactive/Reactive Project Scheduling
by Zdeněk Hanzálek 24 May '21

24 May '21

Dear scheduling researcher, We are delighted to announce the talk given by Erik Demeulemeester (KU Leuven). The title is "On the State of the Art in Proactive/Reactive Project Scheduling". The seminar will take place on Zoom on Wednesday, May 26 at 13:00 UTC. https://cesnet.zoom.us/j/93810859740?pwd=T3Z6d3hZSDM2UnFDRVQrMi9YMnY5Zz09 Meeting ID: 938 1085 9740 Passcode: 021060 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The majority of publications in the extensive literature on resource-constrained project scheduling focus on a static deterministic setting for which a so-called baseline schedule is computed prior to project execution. In the real world, however, a project may be subject to considerable uncertainty. During the actual execution of a project, the baseline schedule may indeed suffer from disruptive events, causing the actually realized activity start times to deviate from the predicted baseline start times. This presentation focuses on robust project scheduling, in particular the development of effective and efficient proactive and reactive scheduling procedures. Proactive scheduling aims at generating robust baseline schedules that carry sufficient protection against possible schedule disruptions that may occur during project execution. Reactive scheduling procedures aim at repairing the baseline schedule when the built-in protection fails during the execution of the project. We discuss the fundamentals of state of the art proactive/reactive project scheduling approaches and discuss key directions for future research. The next seminar in our series will be given by Jinjiang Yuan (Zhengzhou Univ.) "Updated complexity results in single-machine primary-secondary scheduling for minimizing two regular criteria" and it will be held on June 9 at 13:00 UTC. 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