Problèmes d'ordonnancement avec contraintes cumulatives de groupes

The Infologic company develops an ERP, called Copilote, specialized for companies in the agri-food sector. It integrates several modules which allow to schedule different operations of the supply chain. These modules provide solutions to different scheduling problems with different constraints and objectives. Moreover, although the literature on scheduling problems is vast, a particular constraint encountered by Copilote users can only be modelled with difficulty using the elements known from the literature. In the problem encountered, the operations to be scheduled are divided into groups. The schedule must satisfy a constraint on these groups ensuring that at any given time there are no more than k groups such that some operations of these groups have been started while some others have not been completed. In this thesis, we study this new scheduling problem from a theoretical point of view, and we propose adaptations for the methods classically used for scheduling problems (integer linear programming, constraint programming, ant colony optimization, and local search). We also introduce a new approach hybridizing constraint programming and ant colony optimization to solve this problem. We experimentally compare these different algorithms on a test set constructed from real data, and we show that the best algorithm changes depending on the features of the instance to be solved. We then propose a method, which, depending on the features of the instance to be solved, automatically chooses the most suitable solving method. Finally, we evaluate, in a dynamic context, the cost of disrupting as little as possible the already established schedules when new data are revealed.La société Infologic développe un ERP, appelé Copilote, spécialisé pour les entreprises du secteur agro-alimentaire. Il intègre plusieurs modules permettant d'ordonnancer différentes opérations de la chaîne de production. Ces modules apportent des solutions à différents problèmes d'ordonnancement ayant des contraintes et des objectifs différents. Par ailleurs, bien que la littérature concernant les problèmes d'ordonnancement soit vaste, une contrainte particulière rencontrée par les utilisateurs de Copilote ne peut que difficilement être modélisée en utilisant les éléments connus de la littérature. Dans le problème rencontré, les opérations à ordonnancer sont réparties en groupes. L’ordonnancement doit satisfaire une contrainte sur ces groupes assurant qu’à tout moment il n’y a pas plus de k groupes pour lesquels des opérations ont été commencées tandis que d’autres ne sont pas terminées. Dans cette thèse, nous étudions ce nouveau problème d’ordonnancement d’un point de vue théorique, et nous proposons des adaptations pour les méthodes de résolution classiquement utilisées pour les problèmes d’ordonnancement (programmation linéaire en nombres entiers, programmation par contraintes, optimisation par colonies de fourmis, et recherche locale). Nous introduisons également une nouvelle approche hybridant programmation par contraintes et optimisation par colonies de fourmis pour résoudre ce problème. Nous comparons expérimentalement ces différents algorithmes sur un jeu d’essai construit à partir de données réelles, et nous montrons que le meilleur algorithme change en fonction des caractéristiques de l’instance à résoudre. Nous proposons donc une méthode, qui, selon les caractéristiques de l'instance à résoudre, choisit automatiquement la méthode de résolution la plus adaptée. Finalement, nous évaluons, dans un contexte dynamique, le coût engendré par le fait de perturber le moins possible les plannings déjà établis lorsque de nouvelles données sont révélées