Scheduling seminar
Objective of a virtual seminar on scheduling research and applications is to discuss both the field’s newest advancements and survey traditional areas. Seminars take place typically on every second Wednesday through three different time zones (Europe, the Middle East & Africa, North America & South America, and Asia, Australia & Oceania).
Currently, new talks are being planned, and the seminar will start again in September 2024.
Upcoming seminars
Scheduling divisible loads
Presenter: Maciej Drozdowski (Poznań U. of Tech.)
Oct 23, 2024 15:00 CET
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.
Operational scheduling in automotive industry
Presenter: Hugo Chareyre (Artelys)
Nov 6, 2024 15:00 CET
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.
Hexaly Optimizer for Scheduling
Presenter: Philippe Laborie (Hexaly)
Nov 20, 2024 15:00 CET
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.
Recent seminars
Machine Learning meets Selection Hyper-heuristics
Presenter: Ender Ozcan (Uni of Nottingham)
June 12, 2024 15:00 CET
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.
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
Presenter: Matthias Mnich (TU Hamburg)
May 29, 2024 15:00 CET
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.
Maximizing stability of assembly line balancing schedules under uncertain task duration
Presenter: André Rossi (Universite PSL)
April 3, 2024 15:00 CET
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.
Robustness in personnel rostering
Presenter: Pieter Smet (KU Leuven)
March 20, 2024 15:00 CET
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 CP-SAT solver
Presenter: Laurent Perron (Google France)
March 6, 2024 15:00 CET
The CP-SAT solver is developed by the Operations Research team at Google and is part of the OR-Tools open-source optimization suite. It is an implementation of a purely integral Constraint Programming solver on top of a SAT solver using Lazy Clause Generation. It draws its inspiration from the chuffed solver, and from the CP 2013 plenary by Peter Stuckey on Lazy Clause Generation. The CP-SAT solver improves upon the chuffed solver in two main directions. First, it uses a simplex alongside the SAT engine. Second, it implements and relies upon a portfolio of diverse workers for its search part. The use of the simplex brings the obvious advantages of a linear relaxation on the linear part of the full model. It also started the integration of MIP technology into CP-SAT. This is a huge endeavour, as MIP solvers are mature and complex. It includes presolve — which was already a part of CP-SAT –, dual reductions, specific branching rules, cuts, reduced cost fixing, and more advanced techniques. It also allows the tight integration of the research from the Scheduling on MIP community along with the most advanced scheduling algorithms. This has enabled breakthroughs in solving and proving hard scheduling instances of the Job-Shop problems and Resource Constraint Project Scheduling Problems. Using a portfolio of different workers makes it easier to try new ideas and to incorporate orthogonal techniques with little complication, except controlling the explosion of potential workers. These workers can be categorized along multiple criteria like finding primal solutions — either using complete solvers, Local Search or Large Neighborhood Search –, improving dual bounds, trying to reduce the problem with the help of continuous probing. This diversity of behaviors has increased the robustness of the solver, while the continuous sharing of information between workers has produced massive speedups when running multiple workers in parallel. All in all, CP- SAT is a state-of-the-art solver, with unsurpassed performance in the Constraint Programming community, breakthrough results on Scheduling benchmarks (with the closure of many open problems), and competitive results with the best MIP solvers (on purely integral problems).
Scheduling in the e-commerce era: New scheduling problems in order fulfilment and warehousing
Presenter: Nils Boysen (University of Jena)
February 21, 2024 15:00 CET
Driven by the success of e-commerce, today’s warehouses are evolving into fully automated fulfillment factories. Many of them follow the parts-to-picker paradigm, using mobile shelf-lifting robots or conveyors to deliver stock keeping units (SKUs) to stationary order pickers working in picking workstations. This talk aims to structure and review the family of fulfillment-related scheduling problems that arise in this environment: On the input side, the sequence in which totes of SKUs are delivered to a workstation must be synchronized with the orders that are being assembled there at the same time on the output side. In this way, a more efficient fulfillment process can be achieved, and the bin supply system can be relieved. This talk classifies the family of slightly different order fulfillment scheduling problems that arise with different workstation setups in alternative warehouses. This classification scheme is used to survey the existing literature, analyze the computational complexity, and systematically quantify the gains of alternative workstation setups. The talk also highlights valuable future research ideas for this emerging area of scheduling research.
A Matheuristic for the Generalized Order Acceptance and Scheduling Problem
Presenter: Ceyda Oğuz (Koç University)
February 7, 2024 15:00 CET
Firms operating on a make-to-order basis may not satisfy the entire demand due to limited capacity and tight delivery times. This necessitates selecting only part of customer orders to maximize the total revenue, which gives rise to the order acceptance and scheduling (OAS) problems. In this study, we investigate a generalized version of the OAS (GOAS) problem originating from a real- life setting. Due to several components of the problem, such as release times, due dates, deadlines and sequence dependent setup times, finding an exact solution to GOAS problem, that determines which orders to accept and how to schedule them simultaneously to maximize the revenue, in reasonable time even in a single machine environment is difficult. Hence, we develop an effective and efficient matheuristic, which consists of a time-bucket based mixed integer linear programming model, a variable neighborhood search algorithm and a tabu search algorithm, for the GOAS problem. Computational results show that the proposed matheuristic outperforms the state-of-the- art algorithms developed for the GOAS problem. The boundary of optimally solved instance size is pushed further and near optimal solutions are obtained in reasonable time for instances falling beyond this boundary. Joint work with İstenç Tarhan.
Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
Presenter: Klaus Heeger (Ben Gurion Uni)
January 24, 2024 15:00 CET
We consider the 1 || ∑ wj Uj problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. We prove that 1 || ∑ wj Uj is W[1]-hard with respect to the number of different processing times in the input, as well as with respect to the number of different weights in the input. This, along with previous work, provides a complete picture for 1 || ∑ wj Uj from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH). Based on joint work with Danny Hermelin.