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

Kangbok Lee (POSTECH) | February 16 | Scheduling Heuristics for Steelmaking Continuous Casting Processes
by Zdeněk Hanzálek 14 Feb '22

14 Feb '22

Dear scheduling researcher, We are delighted to announce the talk given by Kangbok Lee (POSTECH, Korea). The title is "Scheduling Heuristics for Steelmaking Continuous Casting Processes". The seminar will take place on Zoom on Wednesday, February 16 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91094063787?pwd=d01UbWRPOHJQUy93dnBhWU5QclRLQT09 Meeting ID: 910 9406 3787 Passcode: 284143 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Steelmaking-Continuous Casting (SCC) is a bottleneck in the steel production process and its scheduling has become more challenging over time. In this paper, we provide an extensive literature review that highlights challenges in the SCC scheduling and compares existing solution methods. From the literature review, we collect the essential features of an SCC process, such as unrelated parallel machine environments, stage skipping, and maximum waiting time limits in between successive stages. We consider an SCC scheduling problem with as objective the minimisation of the weighted sum of cast break penalties, total waiting time, total earliness, and total tardiness. We formulate the problem as a mixed-integer linear programming model and develop an iterated greedy matheuristic that solves its subproblems to find a near-optimal solution. Through numerical experiments, we show that our algorithm outperforms two types of genetic algorithms when applied to test instances. The next talk in our series will be given by: John W. Fowler (Arizona State Univ.) | March 2 | Scheduling Problems in Semiconductor Wafer Fabrication Facilities: Part 1 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

Yindong Shen (AIA Huazhong Uni) | February 2| Public transit planning and scheduling based on AVL data in China
by Zdeněk Hanzálek 31 Jan '22

31 Jan '22

Dear scheduling researcher, We are delighted to announce the talk given by Yindong Shen (AIA Huazhong Uni). The title is "Public transit planning and scheduling based on AVL data in China". The seminar will take place on Zoom on Wednesday, February 2 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93999293735?pwd=S0R4Z0xPckVjdjd6ejRBbjVyZlZ6dz09 Meeting ID: 939 9929 3735 Passcode: 992845 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The public transit operations planning process commonly includes the following activities: network route design, service planning (frequency setting and timetabling) and scheduling (vehicle scheduling, crew scheduling and rostering). However, network route design is generally the only one widely recognized, whilst service planning and scheduling are often ignored in China. This leads to the lack of elaborate timetables and schedules, hence, transit operation is often in disorder with high operating costs. To raise the service level and the utilization of resources, an applied study for three cities in China has been conducted, focusing on the enhancement of the recognition and execution of public transit planning and scheduling. A comprehensive framework of public transit planning is first proposed, which is composed of three traditional Chinese items (i.e. network route design, land use for depots, and deployment of vehicles) and the following newly added items: intelligent public transit system (iPTS) planning, service planning, and scheduling. This is pioneering work in China, during which an iPTS plan is conceived and a new vehicle scheduling approach based on AVL data is developed. Experiments during actual projects show that vehicle schedules with high on-time probability and low cost were compiled, while the essential input parameters such as headways and trip times were set automatically. It is anticipated that the research fruits and practical experiences obtained would be of great benefit in improving service and management levels and resource use in public transport in China and some other developing countries. The next talk in our series will be given by: Kangbok Lee (POSTECH)| February 16| Scheduling Heuristics for Steelmaking Continuous Casting Processes 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

Dvir Shabtay (Ben-Gurion Uni)| January 19| On the Parameterized Complexity of Machine Scheduling Problems
by Zdeněk Hanzálek 17 Jan '22

17 Jan '22

Dear scheduling researcher, We are delighted to announce the talk given by Dvir Shabtay (Ben-Gurion Uni). The title is "On the Parameterized Complexity of Machine Scheduling Problems". The seminar will take place on Zoom on Wednesday, January 19 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94434108596?pwd=UTFuT2V3VjRiT3dwTENwRStZSkxPdz09 <https://cesnet.zoom.us/j/94434108596?pwd=UTFuT2V3VjRiT3dwTENwRStZSkxPdz09> Meeting ID: 944 3410 8596 Passcode: 384746 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The main goal of parameterized complexity is to try to design algorithms that are capable of solving (in reasonable time) hard problems in cases where some predefined problem parameters are of limited size. This theory was developed in the early 90s, contributing to many new techniques in the area of algorithmic design ever since. In this talk we survey the main aspects of parametrized complexity, and highlight its applicability to the area of scheduling. We also discuss some challenges and open problems for future research. The next talk in our series will be given by Yindong Shen (AIA Huazhong Uni) | February 2, 2022| Public transit planning and scheduling based on AVL data in China 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

Rubén Ruiz (UP de València)| December 22| State-of-the-art flowshop scheduling heuristics: Dos and Don'ts
by Zdeněk Hanzálek 20 Dec '21

20 Dec '21

Dear scheduling researcher, We are delighted to announce the talk given by Rubén Ruiz (UP de València). The title is "State-of-the-art flowshop scheduling heuristics: Dos and Don'ts". The seminar will take place on Zoom on Wednesday, December 22 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91381308994?pwd=bFgzTFR1ZzlNNHpybTc5YTlTTHRxQT09 Meeting ID: 913 8130 8994 Passcode: 212305 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Many scheduling problems are simply too hard to be solved exactly, especially for instances of medium or large size or when realistic constraints are present. As a result, the literature on heuristics and metaheuristics for scheduling is extensive. More often than not, metaheuristics are capable of generating solutions close to optimality or to tight lower bounds for instances of realistic size in a matter of minutes. Metaheuristics have been refined over the years and there are literally hundreds of papers published every year with applications to most domains in many different journals. Most regrettably, some of these methods are complex in the sense that they have many parameters that affect performance and hence need careful calibration. Furthermore, many times published results are hard to reproduce due to specific speed-ups being used or complicated software constructs. These complex methods are difficult to transfer to industries in the case of scheduling problems. Another important concern is the recently recognized “tsunami” of novel metaheuristics that mimic the most bizarre natural or human processes, as for example intelligent water drops, harmony search, firefly algorithms and the like. See K. Sörensen “Metaheuristics—The Metaphor exposed” (2015), ITOR 22(1):3-18. In this presentation, we briefly review different flowshop problems and variants. From the basic flowshop problem with makespan minimization to other objectives like flowtime minimization, flowshops with sequence-dependent setup times, no-idle flowshops, all the way up to complex hybrid flexible flowline problems. We will show how simple Iterated Greedy (IG) algorithms often outperform much more complex approaches. IG methods are inherently simple with very few parameters. They are easy to code and results are easy to reproduce. We will show that for all tested problems so far they show state-of-the-art performance despite their simplicity. As a result, we will defend the choice of simpler, yet good performing approaches over complicated metaphor-based algorithms. The next talk in our series will be given by Christian Artigues (LAAS-CNRS Toulouse)| December 22| 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

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

2024

2023

2022

2021

Scheduling seminar