Modeling and solving scheduling problems inside the mathematical optimization solver LocalSolver
Modélisation et résolution de problèmes d’ordonnancement au sein du solveur d’optimisation mathématique LocalSolver
Résumé
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 variables, 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).
Résoudre un problème d'ordonnancement consiste à organiser la réalisation de tâches au cours du temps : déterminer leur répartition sur les différentes ressources disponibles ainsi que leurs dates d'exécution. Le travail de cette thèse se concentre sur les problèmes d’ordonnancement de type disjonctif et/ou packing, avec ou sans flexibilité des ressources. L'ensemble des contributions algorithmiques de la thèse ont été implémentées au sein du solveur d'optimisation mathématique LocalSolver, dont les techniques de résolution combinent des méthodes exactes, telles que la programmation linéaire, non linéaire et par contraintes, et heuristiques, comme la recherche locale et des algorithmes constructifs.Le travail de cette thèse répond à deux problématiques principales, liées au traitement de ce type de problèmes d'ordonnancement par LocalSolver. Le premier objectif se dégageant de ces problématiques consiste à permettre aux utilisateurs du solveur de modéliser simplement un grand nombre de problèmes d'ordonnancement disjonctif. En tirant profit du formalisme de modélisation ensembliste de LocalSolver, on propose des formulations génériques, adaptables à différentes familles de problèmes d'ordonnancement, permettant d'exprimer simplement les notions de tâches, de relations de précédence, ou encore de non-chevauchement des tâches. Les formulations génériques choisies reposent sur l'utilisation combinée de variables entières, modélisant les dates de début et durées de tâches, et de variables de listes, représentant leur ordre sur les différentes ressources disjonctives.Le second objectif de la thèse consiste à améliorer les performances de LocalSolver sur les problèmes d'ordonnancement étudiés, en intégrant différents algorithmes de résolution les plus génériques possibles à la composante de recherche locale du solveur. Cette généricité des contributions est cruciale : on ne cherche pas à améliorer les performances du solveur sur un unique problème, ni même seulement sur les problèmes d'ordonnancement, mais sur tous les problèmes présentant des structures caractéristiques de l'ordonnancement disjonctif.Les contributions de cette thèse sont regroupées en trois catégories : des algorithmes d'initialisation, des mouvements de recherche locale, et un algorithme de propagation de contraintes. On présente deux algorithmes constructifs d'initialisation des variables ensemblistes, aidant le solveur à trouver une solution réalisable immédiatement sur des problèmes comme ceux de l'Aircraft Landing ou de l'Assembly Line Balancing, et accélérant ainsi la recherche de solutions de bonne qualité sur ces problèmes. On présente également des mouvements de recherche locale, reposant sur la détection de structures spécifiques dans le modèle (non-chevauchement des tâches, précédences…). On présente également un algorithme de réparation de solutions par propagation de contraintes, appelé au cours de la recherche locale après chaque mouvement conduisant à une solution infaisable. Notre algorithme diffère de la propagation classique de la programmation par contraintes par plusieurs points. Par exemple, il ne propage que les réductions de domaine excluant la valeur courante des variables, et peut prendre des décisions arbitraires lorsqu'il rencontre une contrainte pouvant être réparée de différentes manières. On démontre que dans certains cas l’algorithme présente des propriétés lui assurant de trouver une réparation s'il en existe une. Cet algorithme permet de pallier les difficultés rencontrées par la recherche locale sur les problèmes d'ordonnancement aux contraintes très serrées (passer d'une bonne solution à une autre nécessite de réaliser des changements sur un grand nombre de variables). L'intégration de ces mouvements et de cet algorithme de réparation au sein de la recherche locale de LocalSolver apporte des gains de performance importants sur divers problèmes (Job Shop et variantes, Unit Commitment, Assembly Line Balancing, Bin Packing).
Domaines
Automatique / Robotique
Origine : Version validée par le jury (STAR)