Information : cette page n'est pas traduite en français
ANR JCJC : Robust Scheduling With Budgeted Uncerainty
Scheduling is a very wide topic in combinatorial optimization with applications ranging from production and manufacturing systems to transportation and logistics systems. Stated generally, the objective of scheduling is to allocate optimally scarce resources to activities over time. More specifically, given a set of jobs and a set of machines, scheduling optimization problems look for schedules of the jobs on the machines that satisfy the side constraints and minimize the objective function f(s). We focus in this project on scheduling problems for which a schedule is completely characterized by the order in which the tasks are processed on the machines. For instance, we do not allow insertion of idle time between the processing of subsequent tasks.
Various sources of uncertainty affect real scheduling problems, among which machine breakdowns, working environment changes, worker performance instabilities, tool quality variations and unavailability. Ignoring these uncertainties usually yields schedules that perform poorly under real conditions. Hence, researchers have introduced frameworks where the uncertainty is directly taken into account,either by considering random variables as input or in a worst-case approach where the uncertainty parameters are constrained in a set. These frameworks are respectively denoted by Stochastic Programming and Robust Optimization (RO). We disregard the former in this project because of its requirement for a probabilistic distribution of the random inputs, which is very difficult to obtain in practice. We focus instead on Robust Scheduling, which can be defined as follows.We are given uncertainty set U and we look for a schedule s that minimizes the objective function under the most adverse circumstance represented by U.
Robust schedules are desirable from a practical perspective because they hedge against adverse conditions of the system. In spite of its practical relevance, robust scheduling has hardly become a practical tool since very simple scheduling problems become NP-hard as soon as U contains more than one scenario. This result is however not surprising because it is known that robust combinatorial optimization problems are, more often that not, harder than their deterministic counterpart. In this context, the positive results of Bertsimas and Sim (2003) opened a new avenue of research in robust combinatorial optimization. They introduced a new type of uncertainty set, denoted budgeted uncertainty, which keeps the complexity and approximability properties of the deterministic counterparts for robust combinatorial optimization that have a linear objective function and uncertain cost coefficients.
Despite its practical relevance and its desirable computational properties, the budgeted uncertainty set has not yet been used in the robust scheduling literature. Our objective in this project is to start filling this gap: we will investigate combinatorial algorithms and integer programming formulations for robust scheduling problems with processing time uncertainty assuming that the processing times belong to that set. We expect that the resulting algorithms can turn budgeted robust scheduling into an efficient tool to handle processing time uncertainty.
LIRMM, Montpellier: Michael Poss (PI, CNRS researcher), Marin Bougeret (associate professor), Rodolphe Giroudeau (associate professor), Vincent Boudet (associate professor), Eric Bourreau (associate professor), Marco Silva (PhD student), Maxime Savaro (PhD student)
Logis, UFF (Brazil): Artur Alves Pessoa (associate professor), Eduardo Uchoa (associate professor)
Realopt, INRIA Bordeaux: Boris Detienne (associate professor), Ruslan Sadykov (INRIA researcher)
Scientific advisory board
Klaus Jansen (full professor, TU Kiel, Germany), François Vanderbeck (INRIA team-project Realopt, Bordeaux), Jean-Claude König (LIRMM)
January 2017 - June 2020
- M. Bougeret, K. Jansen, M. Poss, L. Rohwedder: Approximation results for makespan minimization with budgeted uncertainty. Conditionally accepted at Theory of Computing Systems.
- A. Pessoa, M. Poss, R. Sadykov, and F. Vanderbeck: Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty. Operations research, In press.
- M. Silva, M. Poss, N. Maculan: Solution Algorithms for Minimizing the Total Tardiness with Budgeted Processing Time Uncertainty. EJOR, 283(1): 70-82 (2020)
- M. Bougeret, A. Pessoa, and M. Poss: Robust scheduling with budgeted uncertainty. Discrete Applied Mathematics 261: 93-107 (2019)
- M. Bougeret, K. Jansen, M. Poss, L. Rohwedder: Approximation results for makespan minimization with budgeted uncertainty. WAOA (2019)
- Y. Al Najjar, N. Goldberg, S. Karhi, M. Poss: Robust Two-Stage Packing into Designated and Multipurpose Bins. IFAC 2019
- A. Basu Roy, M. Bougeret, N. Goldberg, M. Poss: Approximating Robust Bin Packing with Budgeted Uncertainty. WADS 2019: 71-84
- Z. Alès, S. Nguyen, M. Poss: Minimizing the weighted sum of completion times under processing time uncertainty. INOC 2017
Dernière mise à jour le 03/11/2020