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

Norbert Trautmann (University of Bern) | December 4 | Mixed-integer linear programming for project scheduling with resource-unit related constraints
by Zdeněk Hanzálek 02 Dec '24

02 Dec '24

Dear scheduling researcher, We are delighted to announce the talk given by Norbert Trautmann (University of Bern). The title is "Mixed-integer linear programming for project scheduling with resource-unit related constraints". The seminar will take place on Zoom on Wednesday, December 4 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93745359018?pwd=WPl0pMPIc8GP7Ou2GxRTKzxusUqjow.1 <https://cesnet.zoom.us/j/93745359018?pwd=WPl0pMPIc8GP7Ou2GxRTKzxusUqjow.1> Meeting ID: 937 4535 9018 Passcode: 272218 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A <https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A> The abstract follows. The widely discussed Resource-Constrained Project Scheduling Problem (RCPSP) consists in devising a schedule for the execution of the project activities such that (a) the project duration is minimized, (b) the completion-start precedence between given pairs of activities is respected, and (c) at no time does the total demand of the in-progress activities exceed the available capacity of the various resource types required for the execution of the activities. In the literature, different formulations of the RCPSP have been presented as binary or mixed-binary linear optimization problems; according to the time representation, the two groups of discrete-time and continuous-time formulations can be distinguished. In many applications, resource types represent pools of equipment units or teams of people with specific skills. In this talk, we consider two novel variants of the RCPSP in which additional constraints related to the individual units of the various resource types have to be considered. In the first variant, the execution of the project is distributed across multiple sites, i.e., for the execution of each activity, a particular site must be selected; moreover, while some resource units are available only at a particular site, other resource units can be moved between sites, requiring some transportation time. In the second variant, the workload should be balanced among the individual units of each resource type. For both variants, we present a continuous-time assignment-based formulation as a mixed-binary linear optimization problem. The next talk in our series will be announced in January 2025. For more details, please visit https://schedulingseminar.com/ <https://schedulingseminar.com/> With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- 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

Philippe Laborie (Hexaly) | November 20 | Hexaly Optimizer for Scheduling
by Zdeněk Hanzálek 18 Nov '24

18 Nov '24

Dear scheduling researcher, We are delighted to announce the talk given by Philippe Laborie (Hexaly). The title is " Hexaly Optimizer for Scheduling ". The seminar will take place on Zoom on Wednesday, November 20 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99723070697?pwd=UpfVCqZTGBxoCQMoJ7czR8p490QSyc.1 Meeting ID: 997 2307 0697 Passcode: 433986 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Hexaly Optimizer is a model-and-run mathematical optimization solver that addresses a broad range of industrial optimization problems in the areas of supply chain and workforce management, such as routing, scheduling, packing, clustering, matching, assignment, or facility location. Its mathematical formalism extends classical Mixed-Integer Linear Programming with set, permutation and interval variables on which any usual algebraic operator (arithmetic, logic, relational, etc.) can be applied. Hexaly Optimizer is widely used in industry today, has performances often comparable to the best dedicated algorithms, allows compact modeling, scales well (with problem size and complexity) and is constantly improving. This seminar focuses on the use of Hexaly Optimizer to model and solve industrial scheduling problems. We show how to exploit the mathematical concepts of the input formalism to model several classic scheduling problems in an elegant and compact manner and give an idea of the solver's performance compared to the state of the art. Next, we outline the various techniques employed under the hood to produce good-quality primal and dual solutions like constraint propagation, local search, large neighborhood search, linear relaxations, scheduling heuristics, or exact scheduling algorithms on particular sub-problems. The next talk in our series will be: Norbert Trautmann (University of Bern) | December 4 | Mixed-integer linear programming for project scheduling with resource-unit related constraints For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- 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

Hugo Chareyre (Artelys) | November 6 | Operational scheduling in automotive industry
by Zdeněk Hanzálek 04 Nov '24

04 Nov '24

Dear scheduling researcher, We are delighted to announce the talk given by Hugo Chareyre (Artelys). The title is " Operational scheduling in automotive industry". The seminar will take place on Zoom on Wednesday, November 6 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98884415966?pwd=OTzYfvWhtPObJTHpZaK2BarbGHoLUh.1 Meeting ID: 988 8441 5966 Passcode: 576609 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Artelys has developed a scheduler service for Toyota Motor Europe that creates plannings for post-production workshops operations across Europe. The problem consists in scheduling operations on vehicles on different production lines with available resources. This case study details how this industrial problem differs from the classical Resource Constrained Project Scheduling Problem (RCPSP) with its additional operational constraints (multiple shifts, preemptive breaks, sequence constraints, etc.) and its multi-objectives (minimizing late tasks, late vehicles, maximizing efficiency and workers ergonomics, etc.). Artelys has worked closely with Toyota to deploy this scheduler service as micro-service in order to solve this complex problem in a real-time context and as a flexible decision-aid software. The associated constraint programming model is implemented with Fico Mosel modelling language and the model is solved using Artelys Kalis solver. This micro-service has replaced a manual tedious task that was taking place differently in all workshops by delivering faster, higher quality solutions. The next talk in our series will be: Philippe Laborie (Hexaly) | November 20 | Hexaly Optimizer for Scheduling For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- 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

Maciej Drozdowski (Poznan UT)| Oct 23 | Scheduling divisible loads
by Zdeněk Hanzálek 21 Oct '24

21 Oct '24

Dear scheduling researcher, We are delighted to announce the talk given by Maciej Drozdowski (Poznan UT). The title is "Scheduling divisible loads". The seminar will take place on Zoom on Wednesday, October 23 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96350506239?pwd=QlxrGyT3FiSaawN9eQqBj7u8pdF5IU.1 Meeting ID: 963 5050 6239 Passcode: 185009 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 divisible load theory (DLT) will be introduced. The theory is a scheduling and computer performance model applicable in data-parallel applications. Its basic assumption is that the computing work can be divided into pieces of arbitrary sizes and these pieces can be processed independently in parallel. In the talk we will proceed from the basic formulation of divisible load scheduling on heterogeneous system to a formulation for multi-installment divisible load processing in heterogeneous system with hierarchical memory and energy constraints. NP-hardness of various DLT scheduling problem variants will be considered. Application of DLT as isoefficiency maps visualizing parallel processing performance relationships will be demonstrated. The next talk in our series will be: Hugo Chareyre (Artelys) | November 6 | Operational scheduling in automotive industry 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

Maciej Drozdowski (Poznan UT)| Oct 23 | Scheduling divisible loads
by Zdeněk Hanzálek 14 Oct '24

14 Oct '24

Dear scheduling researcher, We are delighted to announce the talk given by Maciej Drozdowski (Poznan UT). The title is "Scheduling divisible loads". The seminar will take place on Zoom on Wednesday, October 23 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96350506239?pwd=QlxrGyT3FiSaawN9eQqBj7u8pdF5IU.1 Meeting ID: 963 5050 6239 Passcode: 185009 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 divisible load theory (DLT) will be introduced. The theory is a scheduling and computer performance model applicable in data-parallel applications. Its basic assumption is that the computing work can be divided into pieces of arbitrary sizes and these pieces can be processed independently in parallel. In the talk we will proceed from the basic formulation of divisible load scheduling on heterogeneous system to a formulation for multi-installment divisible load processing in heterogeneous system with hierarchical memory and energy constraints. NP-hardness of various DLT scheduling problem variants will be considered. Application of DLT as isoefficiency maps visualizing parallel processing performance relationships will be demonstrated. The next talk in our series will be: Hugo Chareyre (Artelys) | November 6 | Operational scheduling in automotive industry 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

Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics
by Zdeněk Hanzálek 10 Jun '24

10 Jun '24

Dear scheduling researcher, We are delighted to announce the talk given by Ender Ozcan (Uni of Nottingham). The title is "Machine Learning meets Selection Hyper-heuristics". The seminar will take place on Zoom on Wednesday, June 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91588200395?pwd=sySE3R77BKsPZfaOOQ8O7EyeuhfLT3.1 Meeting ID: 915 8820 0395 Passcode: 557258 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Hyper-heuristics are powerful search methodologies that operate on low level heuristics or heuristic components to tackle computationally hard optimisation problems. The current state-of-the-art in hyper-heuristic research contains classes of algorithms that focus on intelligently selecting or generating a suitable heuristic for a given situation. Hence, there are two main types of hyper-heuristics: selection and generation hyper-heuristics. A typical selection hyper-heuristic chooses a low-level heuristic and applies it to the current solution at each step of a search, before deciding whether to accept or reject the newly created solution. Generation hyper-heuristics, in contrast, automatically build heuristics or heuristic components during the search process. Machine learning is revolutionising various fields, and its integration with hyper-heuristics holds immense potential. This talk will first offer a concise overview of hyper-heuristics, followed by illustrative case studies demonstrating how we have successfully applied machine learning to automatically design more effective selection hyper-heuristics. The next talk in our series will be: 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

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 27 May '24

27 May '24

Dear scheduling researcher, We are delighted to announce the talk given by Matthias Mnich (TU Hamburg). The title is " New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines ". The seminar will take place on Zoom on Wednesday, May 29 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09 Meeting ID: 930 0863 4528 Passcode: 089440 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. - Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{m∆}, which improves on the previously best constants in the linearized form. - Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^{O(1/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. The next talk in our series will be: Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics 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

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 21 May '24

21 May '24

Dear scheduling researcher, We are delighted to announce the talk given by Matthias Mnich (TU Hamburg). The title is " New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines ". The seminar will take place on Zoom on Wednesday, May 29 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09 Meeting ID: 930 0863 4528 Passcode: 089440 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. - Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{m∆}, which improves on the previously best constants in the linearized form. - Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^{O(1/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. The next talk in our series will be: Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics 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

André Rossi (Universite PSL) | April 3 | Maximizing stability of assembly line balancing schedules under uncertain task duration
by Zdeněk Hanzálek 02 Apr '24

02 Apr '24

Dear scheduling researcher, We are delighted to announce the talk given by André Rossi (Universite PSL). The title is " Maximizing stability of assembly line balancing schedules under uncertain task duration ". The seminar will take place on Zoom on Wednesday, April 3 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/99589658637?pwd=NFU5Y255VUl1WjYwYUxpaFZGV3JUUT09 Meeting ID: 995 8965 8637 Passcode: 782996 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 variant of the simple assembly line balancing problem in which the number of workstations and the cycle time are fixed, but some tasks are subjected to uncertainty (processing times can increase). The purpose is to maintain the schedule feasibility when the duration of tasks increases. To achieve this, we consider two stability measures (to be maximized): the stability radius, and the stability factor, that correspond to different types of task duration increase. The scheduling problem is formulated as a mixed integer linear program, and this formulation is strengthened by an upper bound and a heuristic. More specifically, the allocation intervals of the tasks, that are based on precedence constraints, are narrowed, which in turn are used to improve the results of the heuristic and the mixed integer linear programming formulation. The next talk in our series will be: Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines 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

Pieter Smet (KU Leuven) | March 20 | Robustness in personnel rostering.
by Zdeněk Hanzálek 18 Mar '24

18 Mar '24

Dear scheduling researcher, We are delighted to announce the talk given by Pieter Smet (KU Leuven). The title is "Robustness in personnel rostering". The seminar will take place on Zoom on Wednesday, March 20 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09 <https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09> Meeting ID: 997 7514 8608 Passcode: 885832 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 study the problem of generating personnel rosters that are robust with respect to disruptions caused by employee absenteeism. If an employee unexpectedly becomes absent, they must be replaced by another employee. This in turn may affect the working hours of other employees, creating an undesirable ripple effect that changes a large part of the roster. We investigate how making use of on-call duties may avoid such large perturbations. We begin by first introducing a metric to quantify the robustness of a roster, which is then used to generate sufficiently robust rosters. In the second part of this talk, we discuss the conditions under which machine learning can lead to better solutions. A novel methodology is presented to determine the minimum prediction performance required to outperform the non-data-driven rostering approach. The next talk in our series will be: André Rossi (Universite PSL) | April 3 | Maximizing stability of assembly line balancing schedules under uncertain task duration 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