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

Vikram Tiwari (Vanderbilt Uni) | June 7 | Surgery Scheduling: Research and Practice
by Zdeněk Hanzálek 05 Jun '23

05 Jun '23

Dear scheduling researcher, We are delighted to announce the talk given by Vikram Tiwari (Vanderbilt University). The title is "Surgery Scheduling: Research and Practice". The seminar will take place on Zoom on Wednesday, June 7 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96890046173?pwd=bjYzLzkzSUJMU1ZCMWhka2h4RjRqdz09 Meeting ID: 968 9004 6173 Passcode: 999261 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Scheduling of surgeries is a complex process that involves simultaneous scheduling of not only several resources (staff, room, equipment, supplies, instruments), but also building flexibility in capacity-reservation policies to accommodate most types of patient classes. In the case of trauma centers this complexity increases even more due to the need for dynamic rescheduling of elective surgeries as emergency surgeries arrive randomly. In practice, these issues are tackled every day in a ‘non-optimal / heuristic’ way. Recent research in this area has shown the potential of implementing modified priority rules. In contrast to trauma centers, ambulatory surgery centers only perform elective surgeries and have a lower cost structure. Their profitability is therefore dependent upon efficient use of capacity. Recent research has modeled these as Hybrid Flow Shops and solved the capacity planning problem using easy to implement heuristics. This talk will also discuss some new avenues of operating room scheduling that have not yet been researched by academics. The next talk in our series will be: Tami Tamir (Reichman Uni) | June 21 | Scheduling with Machine-Dependent Priority Lists. 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

Erwin Pesch (Uni of Siegen) | May 24 | Conflict-Free Crane Scheduling in a Seaport Terminal.
by Zdeněk Hanzálek 22 May '23

22 May '23

Dear scheduling researcher, We are delighted to announce the talk given by Erwin Pesch (University of Siegen). The title is "Conflict-Free Crane Scheduling in a Seaport Terminal". The seminar will take place on Zoom on Wednesday, May 24 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98592826019?pwd=L1RRMkQ2Q0I4bjN4MzdFVUxLMjlqZz09 Meeting ID: 985 9282 6019 Passcode: 464787 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 focus on a container dispatching and conflict-free yard crane routing problem that arises at a storage yard in an automated, maritime container terminal. A storage yard serves as an intermediate buffer for import/export containers and exchanges containers between water- and landside of a maritime terminal. The problem is in which order and by which crane the containers are transported in order to minimize the makespan and prevent crane interferences. First, we limit our attention to incoming containers only that are positioned by twin cranes. Containers are assigned to the cranes according to different policies. We show that some cases are polynomially solvable. Approximation algorithms with guaranteed absolute and relative deviations from the optimum are devised for others. The results translate for the case of outgoing containers. In the second part we consider two rail mounted gantry cranes of different sizes, with the possibility to cross each other, that perform inbound, outbound and housekeeping requests. We solve this problem to optimality by a branch-and-cut approach that decomposes the problem into two problem classes and connects them via logic-based Benders constraints. The next talk in our series will be: Vikram Tiwari (Vanderbilt Uni) | June 7 | Surgery Scheduling: Research 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

Dries Goossens (Ghent University) | May 10 | Sports scheduling: from consulting to science
by Zdeněk Hanzálek 09 May '23

09 May '23

Dear scheduling researcher, We are delighted to announce the talk given by Dries Goossens (Ghent University). The title is "Sports scheduling: from consulting to science". The seminar will take place on Zoom on Wednesday, May 10 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96538835333?pwd=bktZNDliS09sNllZeXh0aWFBdFpidz09 Meeting ID: 965 3883 5333 Passcode: 652168 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Any sports competition needs a schedule, specifying when and where teams meet each other. Apart from a number of pioneering theoretical results, most sports timetabling contributions in the literature read as case studies, describing a single problem instance for which a tailored algorithm is developed and compared to a manual solution. While the reported problems are challenging, and the algorithms made an impact in practice, it is hard to assess algorithmic performance. Indeed, real-life problem instances are rarely shared, and few realistic benchmark instances are available. In this talk, we discuss our efforts to obtain insights in the strengths and weaknesses of several state-of-the-art sport scheduling algorithms, and to predict which algorithm to select for which type of problem. The story covers the development of a problem classification and unifying data format, the generation of a set of diverse and realistic benchmark instance, the organization of a timetabling competition, and an instance space analysis for sports scheduling. The next talk in our series will be: Erwin Pesch (Uni of Siegen) | May 24 | Conflict-Free Crane Scheduling in a Seaport Terminal. 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

Rainer Kolisch (TU Munich) | April 26 | The Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles: Models, Methods, and Applications
by Zdeněk Hanzálek 24 Apr '23

24 Apr '23

Dear scheduling researcher, We are delighted to announce the talk given by Rainer Kolisch (TU Munich). The title is "The Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles: Models, Methods, and Applications". The seminar will take place on Zoom on Wednesday, April 26 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94073736203?pwd=V2RwWkI3eTB2WGw4TFU5YmdmRVgwZz09 Meeting ID: 940 7373 6203 Passcode: 259630 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The resource-constrained project scheduling problem with flexible resource profiles (FRCPSP) is a generalization of the RCPSP where for each activity a work content is given, which has to be allocated between the start and the finish time of the activity. Hence, next to the start time of activities, a schedule comprises the decision about the duration and the allocation of the work content between the start and the finish time for the activities. The FRCPSP has been introduced in 2003 in the context of real-world application of pharmaceutical research projects. Since, then different models and methods as well as applications have been proposed in the literature. In this talk we will present the FRCPSP, discuss available MIP-formulations as well as heuristics and will present work on the use of FRCPSP to solve different real-world optimization problems. The next talk in our series will be: Dries Goossens (Ghent University) | May 10 | Sports scheduling: from consulting to science. 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

Wojciech Bozejko (Poli Wroclawska) | April 12 | Optimal solving of scheduling problems on D-Wave quantum machines
by Zdeněk Hanzálek 11 Apr '23

11 Apr '23

Dear scheduling researcher, We are delighted to announce the talk given by Wojciech Bozejko (Poli Wroclawska). The title is "Optimal solving of scheduling problems on D-Wave quantum machines". The seminar will take place on Zoom on Wednesday, April 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95332759663?pwd=YVNNT3JrWFhzbmQxcFpUczBGM0d4QT09 Meeting ID: 953 3275 9663 Passcode: 208021 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 disadvantage of calculations on real quantum computers is their non-determinism. For optimization problems, it is possible to get surprisingly good results using Quantum Annealing approach, but without a guarantee of the optimality of the result. Simply put, the quantum machine has not found anything better. In the presentation an approach that provides such a guarantee of optimality is proposed. A solution that is optimal in the strict mathematical sense is generated, without probabilistic considerations. For this purpose, a D-Wave quantum machine is used working as a sampler implementing quantum annealing -- an approach considered as a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then the mechanism of a Branch and Bound scheme is used and controlled by quantum annealing, which allows us to obtain very quickly -- in constant time for considered instances -- the boundaries of the considered subproblems. The whole idea is an alternately combination of calculations realized on QPU and CPU, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness as well as with total number of tardy jobs criteria. The main result is the formulation of the lower bound in a "language" (i.e. mathematical model) understandable by a quantum machine. The next talk in our series will be: Rainer Kolisch (TU Munich) | April 26 | The Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles: Models, Methods, and Applications. 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

Xiangtong Qi (HKUST) | March 15 | Cooperative Games Models for Scheduling Problems
by Zdeněk Hanzálek 13 Mar '23

13 Mar '23

Dear scheduling researcher, We are delighted to announce the talk given by Xiangtong Qi (HKUST). The title is "Cooperative Games Models for Scheduling Problems". The seminar will take place on Zoom on Wednesday, March 15 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95025420403?pwd=cERNTzJzTHJRTmpJOXZMeFFOL1Awdz09 Meeting ID: 950 2542 0403 Passcode: 559414 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Cooperative game theory focuses on schemes that lead to a global collaboration among multiple independent decision makers. In cooperative game theory, one basic concept is the allocation in the core that characterizes how the players shall share the cost/benefit in a way acceptable to all sub-coalitions. Unfortunately, it is well known that many cooperative games have an empty core, including games concerning scheduling problems. For such games the global collaboration will not be sustainable. We consider a situation where an outside party has the need to stabilize the ground coalition because, for example, the best social welfare can be achieved only when all players collaborate. We introduce a few economic treatments that can be used by the outside party such as providing subsidy and charging penalty. These treatments, including their concepts and implementations, are demonstrated by games related to scheduling problems. The next talk in our series will be: Erwin Pesch (Uni of Siegen) | March 29 | Conflict-Free Crane Scheduling in a Seaport Terminal. 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

Hyun-Jung Kim (KAIST) | March 1 | Scheduling with Machine Learning
by Zdeněk Hanzálek 27 Feb '23

27 Feb '23

Dear scheduling researcher, We are delighted to announce the talk given by Hyun-Jung Kim (KAIST). The title is "Scheduling with Machine Learning". The seminar will take place on Zoom on Wednesday, March 1 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95707763175?pwd=aTdmWDN1RG0ySlk0a1dZWUdUdXZJUT09 Meeting ID: 957 0776 3175 Passcode: 047586 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Manufacturing companies have recently shown a growing interest in using machine learning to improve scheduling problems. In this talk, we will present three real-life industrial scheduling problems faced by industries with a specific focus on the application of machine learning. First, in semiconductor manufacturing, multiple weighted dispatching rules are used to determine a sequence of jobs. Engineers assign these weights based on their previous experience. We propose a machine learning approach to determine the best weight set for all rules, especially when there is not enough time to derive it. Second, we propose an integration method of machine learning and mathematical formulation for scheduling problems in steel manufacturing. This approach reflects the engineers’ preferences and improves the performance of scheduling at the same time. Finally, we will present a hybrid flow shop scheduling problem for insulation manufacturing where machine learning with the NEH algorithm has been applied. We will also discuss the challenges of implementing machine learning or other heuristic algorithms in practical settings. The next talk in our series will be: Xiangtong Qi (HKUST) | March 15 | Cooperative Games Models for Scheduling 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

Vincent T’kindt (University of Tours) | February 15 | The Marriage of Matheuristics and Scheduling
by Zdeněk Hanzálek 13 Feb '23

13 Feb '23

Dear scheduling researcher, We are delighted to announce the talk given by Vincent T’kindt (University of Tours). The title is "The Marriage of Matheuristics and Scheduling". The seminar will take place on Zoom on Wednesday, February 15 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91263922505 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 is about the heuristic solution of scheduling problems by means of heuristics based on mathematical programming, well-known under the name of matheuristics. Whatever they are used to build or improve a solution, they always take advantage of mathematical programming in order to efficiently solve some subproblems. Matheuristics have been introduced in the literature during the last decade especially to solve routing problems. Few is known about their application to machine scheduling problems. I will introduce to different forms of matheuristics and give a feedback on the solution of some scheduling problems, making also an outing in the land of machine learning. The next talk in our series will be: Hyun-Jung Kim (KAIST) | March 1 | Scheduling with Machine Learning. 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

Jacques Carlier (Sorbonne University) | February 1 | Constructive and destructive bounds for the m-machine scheduling problem
by Zdeněk Hanzálek 30 Jan '23

30 Jan '23

Dear scheduling researcher, We are delighted to announce the talk given by Jacques Carlier (Sorbonne University). The title is " Constructive and destructive bounds for the m-machine scheduling problem ". The seminar will take place on Zoom on Wednesday, February 1 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91663233347?pwd=SndKeS93bnRDdGRPWGtQUS9pWlZEUT09 Meeting ID: 916 6323 3347 Passcode: 218128 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The aim of this talk is to present some new results on constructive and destructive bounds for the m-machine scheduling problem. Recently we have characterized mathematically the three main constructive bounds which are the preemptive bound, the energetic bound and the JPPS makespan. These characterizations give insights to their similarities and differences. It explains why these bounds are generally equal in practice. Moreover our characterization of the energetic bound introduced by Erschler, Lopez and Thuriot permits to build a 0(n alpha(n) logn) ( alpha(n) Ackermann coefficient) checker. It is the best one in literature. We have compared it to the checkers of Baptiste Lepape and Nuijten (O(nsquare)) and to the checker of Ouellet and Quimper (O(nlognlogn)). The checker of Baptiste, Lepape and Nuijten is based on an identification of useful intervals and on incremental evaluations of intervals energy. Ouellet and Quimper prove that the energy matrix is a Monge matrix and evaluate the energy of some interval thanks to a pre-calculated data structure based on range trees. We characterize mathematically the useful intervals, then we use the data structures introduced by Ouellet and Quimper and a nice algorithm for partial Monge Matrix. Our checker is also the best one in practice in literature, as it is confirmed by the numerical results we report. Work in collaboration with Abderrahim Sahli, Antoine Jouglet1 and Eric Pinson. The next talk in our series will be: Vincent T’kindt (University of Tours) | February 15 | The Marriage of Matheuristics and 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

Lars Rohwedder (Maastricht University) | January 18 | Recent advances in flow time scheduling
by Zdeněk Hanzálek 16 Jan '23

16 Jan '23

Dear scheduling researcher, We are delighted to announce the talk given by Lars Rohwedder (Maastricht University). The title is " Recent advances in flow time scheduling ". The seminar will take place on Zoom on Wednesday, January 18 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96444131847?pwd=S0d6QnplZzh6S2t0dUMzYXcxSTVPZz09 Meeting ID: 964 4413 1847 Passcode: 537506 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Flow time is one of the most natural metrics to optimize in scheduling, but algorithmically it can be notoriously difficult to handle. I will talk about some recent advances in this topic, focusing on two results by myself and co-authors: a PTAS for the sum of weighted flow times on a single machine and improved approximation guarantees for parallel unrelated machines. The first result is enabled by a study of structural properties of constraints in a natural ILP formulation and the second result relies on a novel connection to discrepancy theory. The next talk in our series will be: Jacques Carlier (Sorbonne University) | February 1 | Constructive and destructive bounds for the m-machine scheduling problem. 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