Skip to Main content Skip to Navigation
Theses

Modélisation et résolution de problèmes d'ordonnancement au sein du solveur d'optimisation mathématique LocalSolver

Léa Blaise 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : Solving a scheduling problem consists in organizing the realization of tasks in the course of time: determining their distribution on the various available resources as well as their execution dates. Scheduling problems are encountered in all domains of industry and services, and are often studied in the literature. This thesis focuses on disjunctive scheduling and/or packing problems, with or without flexibility on the resources. All the algorithmic contributions of this thesis have been implemented within the mathematical optimization solver LocalSolver, whose resolution techniques combine exact methods, such as linear, nonlinear and constraint programming, and heuristics, such as local search and constructive algorithms. This thesis addresses two main issues related to the treatment of this type of scheduling problems by LocalSolver. The first objective is to easily allow users to model many disjunctive scheduling problems. By taking advantage of LocalSolver's set-based modeling formalism, we propose generic formulations, adaptable to different disjunctive scheduling problem families, in order to simply express the concepts of tasks, precedence relations, or non-overlap constraints on the tasks assigned to the same disjunctive resource. These generic formulations are based on the combined use of two types of decision variables offered by LocalSolver: integer variables, representing the start dates and durations of tasks, and list variables, representing their order on the various disjunctive resources. The second objective of the thesis is to improve the performance of LocalSolver on the considered scheduling problems, by integrating different resolution algorithms, as generic as possible, to the local search component of the solver. The genericity of the contributions is crucial: indeed, we do not aim at improving the performance of the solver on a single problem, nor even only on scheduling problems, but on all problems presenting certain characteristic structures often encountered in disjunctive scheduling or in packing. The algorithmic contributions of this thesis can be grouped into three main categories: initialization algorithms, local search moves, and a constraint propagation algorithm. We present two constructive initialization algorithms for set and list variables, which help the solver to immediately find a feasible solution to problems such as the Aircraft Landing or Assembly Line Balancing Problems, and thus accelerate the search for good quality solutions. We also present several local search moves, based on the detection of specific structures in the model (non-overlap constraints, precedence relations, packing constraints). We also present a solution repair algorithm by constraint propagation, integrated into the solver's local search component, and called after each local move leading to an infeasible solution. Our algorithm differs from classical constraint propagation in several ways. For example, it only propagates domain reductions that exclude the current values of the va! riables, and can make arbitrary decisions when it encounters a constraint that can be repaired in different ways. We prove that in some cases the algorithm has properties that ensure that the propagation will succeed if the solution can be repaired. This algorithm overcomes the difficulties encountered by local search on tightly constrained scheduling problems (moving from a good solution to another requires making changes on a large number of variables). The integration of these local moves and this repair algorithm into LocalSolver's local search component brings significant performance gains on various problems (Job Shop and variants, Unit Commitment, Assembly Line Balancing, or Bin Packing).
Document type :
Theses
Complete list of metadata

https://hal.laas.fr/tel-03662149
Contributor : LAAS HAL-LAAS Connect in order to contact the contributor
Submitted on : Monday, May 9, 2022 - 9:58:50 AM
Last modification on : Wednesday, June 1, 2022 - 4:41:41 AM

File

Léa BLAISE.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03662149, version 1

Citation

Léa Blaise. Modélisation et résolution de problèmes d'ordonnancement au sein du solveur d'optimisation mathématique LocalSolver. Automatique. INSA Toulouse, 2022. Français. ⟨tel-03662149⟩

Share

Metrics

Record views

0

Files downloads

0