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

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

Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop scheduling problems
by Zdeněk Hanzálek 22 Nov '22

22 Nov '22

Dear scheduling researcher, We are delighted to announce the talk given by Sigrid Knust (Uni of Osnabrück). The title is "Synchronous flow shop scheduling problems". The seminar will take place on Zoom on Wednesday, November 23 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91616587714?pwd=SFJGcnpVbTFSSWFGVWt5WHFwL2xuQT09 Meeting ID: 916 1658 7714 Passcode: 332102 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. A synchronous flow shop is a variant of a non-preemptive permutation flow shop where transfers of jobs from one machine to the next take place at the same time. The processing is organized in synchronized cycles which means that in a cycle all current jobs start at the same time on the corresponding machines. Then all jobs are processed and have to wait until the last one is finished. Afterwards, all jobs are moved to the next machine simultaneously. As a consequence, the processing time of a cycle is determined by the maximum processing time of the operations contained in it. Furthermore, only permutation schedules are feasible, i.e., the jobs have to be processed in the same order on all machines. The goal is to find a permutation of the jobs such that the makespan is minimized. Motivated by a practical application in production planning at a company assembling shelf boards for kitchen elements, we investigate different aspects of synchronous flow shop problems. Especially, we consider the situation of dominating machines, additional resources, setup times and leaving machines idle. The next talk in our series will be in January 2023. 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

Alessandro Agnetis (University of Siena) | November 9 | Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems
by Zdeněk Hanzálek 07 Nov '22

07 Nov '22

Dear scheduling researcher, We are delighted to announce the talk given by Alessandro Agnetis (University of Siena). The title is " Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems ". The seminar will take place on Zoom on Wednesday, November 9 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98121270904?pwd=aUxmUk5iNENoU3czUmo1Vzg1b3U2dz09 Meeting ID: 981 2127 0904 Passcode: 729055 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Typical scheduling problems deal with a set of activities (jobs) requiring various resources (machines) to be performed. In most scheduling scenarios, it is assumed that machines are continuously avalable (possibly except in some scheduled maintenance intervals), and this gives rise to problems in which the typical scheduling objectives (makespan, total weighted completion time etc) are pursued. A significantly different scenario arises if machines may actually fail, i.e., (i) while performing a job i, a machine becomes unavailable (e.g. breaks down) with probability \pi_i, and (ii) such failures are unrecoverable, in the sense that from then onwards the machine is lost and so are the jobs already allocated and not yet processed on that machine. If a job i is successfully completed, a reward r_i is attained. In this context, the basic problem is how to assign the jobs to the machines and how to sequence them so that the expected reward is maximized. In this talk we review the main results, discuss relationships with other sequencing problems and point out some open problems. We address the following scenarios. 1) m parallel (identical) machines. While the single-machine case is easy, for two or more machines the problem is hard and various approaches have been proposed to address it. For general m, list scheduling yields a 0.8531-approximate solution. The argument of the proof is similar to the one used by Schwiegelshohn to prove Kawaguchi and Kyan's bound for the minimization of total weighted completion time. 2) In order to hedge against machine failures, one can use job replication. In this case, copies of the same job can be scheduled on different machines, and the reward r_i is attained if at least one copy is successfully completed. Although also this problem is hard for m>=2, relatively simple algorithms provide solutions which are provably close to optimality. 3) This class of sequencing problems is also related to testing problems, as follows. A system consists of n components, each of which can be either functioning or not. Only if all components are functioning, the system is "up". Component i is functioning with probability \pi_i, and testing it costs c_i. As soon as a component that is not functioning is detected, the testing stops (concluding that the system is "down"). The problem is to decide in which order should the components be tested, in order to minimize the expected costs. While the single-tester problem is solved by a simple priority rule, various problem variants can be considered. In particular, if several testers operate in parallel, under time constraints, the problem gets more complicated. While it is NP-hard for three or more testers, its complexity with two testers is still open. The next talk in our series will be: Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop 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