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

Daniele Vigo (Unibo CIRI-ICT) | March 12 | One Million ... and Beyond! Solving Huge-Scale Vehicle Routing Problems in a Handful of Minutes
by Zdenek Hanzalek 07 Mar '25

07 Mar '25

Dear scheduling researcher, We are delighted to announce the talk given by Daniele Vigo (Unibo CIRI-ICT). The title is "One Million ... and Beyond! Solving Huge-Scale Vehicle Routing Problems in a Handful of Minutes". The seminar will take place on Zoom on Wednesday, March 12 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96957110178?pwd=buNswAwkpAcTOreAfQ2qHG5yZr0kJd.1 Meeting ID: 969 5711 0178 Passcode: 723073 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Vehicle routing is a hard and extensively studied combinatorial optimization problem which has numerous practical applications in transportation and logistics. In the last two decades several effective solution methods were proposed for the heuristic solution of the vehicle routing problem (VRP) and its many variants but most of these methods do not scale well with respect to the computing time when the size of the problem grows. We discuss a family of approaches, originated from the FILO framework, which were explicitly designed to obtain a linear growth of the computing time making it possible to solve very large instances with up to one million customers within a very limited computing time. The next talk in our series will be: Christian Blum (IIIA-CSIC) | March 26 | CMSA: A Hybrid Metaheuristic for Combinatorial Optimization 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

Defeng Sun (DAO lab, NEU China) | February 12 | Combinatorial Benders approach to solve the Quay Crane Scheduling Problem
by Zdenek Hanzalek 10 Feb '25

10 Feb '25

Dear scheduling researcher, We are delighted to announce the talk given by Defeng Sun (DAO lab, NEU China). The title is " Combinatorial Benders approach to solve the Quay Crane Scheduling Problem". The seminar will take place on Zoom on Wednesday, February 12 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94791685557?pwd=p6XThOlSYXm8cT9n4db8dcjNSbiBiw.1 Meeting ID: 947 9168 5557 Passcode: 218539 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We propose an exact decomposition approach to solve the Quay Crane Scheduling Problem (QCSP) in container terminals. The problem is decomposed into two simpler problems: a sequencing master problem and a scheduling sub-problem. The master problem explores possible operation sequencing solutions for the tasks, while the sub-problem determines the completion times for each task to avoid collisions among quay cranes. A series of combinatorial cuts based on minimum infeasible systems and minimum sub-optimal systems are generated to accelerate the algorithm convergence. Furthermore, we provide a cut selection strategy to generate tighter multiple cuts. Computational tests on benchmark instances verify the effectiveness of the proposed approach. The next talk in our series will be: Daniele Vigo (Unibo CIRI-ICT) | March 12 | One Million ... and Beyond! Solving Huge-Scale Vehicle Routing Problems in a Handful of Minutes 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

Two postdoctoral positions in scheduling
by Zdeněk Hanzálek 10 Jan '25

10 Jan '25

We invite applications for the position of Postdoctoral Researcher in the Optimization Group at the Czech Technical University in Prague. The topics to be studied are: *Scheduling Algorithms for Energy-efficient Production* https://euraxess.ec.europa.eu/jobs/307376 <https://euraxess.ec.europa.eu/jobs/307376> *Hybridization of Constraint Programming**for Scheduling Problems with Complex Criteria * https://euraxess.ec.europa.eu/jobs/307390 <https://euraxess.ec.europa.eu/jobs/307390> The successful applicant will work in close collaboration with Zdenek Hanzalek within the large-scope project “Roboprox - Robotics and Advanced Industrial Production,” co-funded by the EU. The successful applicant will have, or be about to obtain, a Ph.D. degree in computer sciences or equivalent professional qualifications. Applicants should have research experience in a field closely related to scheduling, combinatorial optimization, and algorithm design/implementation. The position is up to 2 years. The jobs and application process are listedat Euraxess, with a deadline of 31st January 2025. -- 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

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