Scheduling seminar

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.

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.

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 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).

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.

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.

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.