Abstract FR:

La plupart des travaux sur l'ordonnancement avec contraintes de ressources (problème RCPSP) sont liés à des problèmes où les tâches utilisent des quantités constantes de ressources durant toute leur exécution. Cependant, dans de nombreux problèmes pratiques, les consommations des tâches en ressources sont variables avec le temps. Ces variations peuvent être discrètes (besoin de main d'oeuvre) ou continues (électricité, pétrole). En général, de tels profils de consommation sont approximés par des suites de rectangles liés par des contraintes de contigüités mais un nombre élevé de rectangles élémentaires et de contraintes sont alors nécessaires. Dans cette thèse, nous présentons dans un premier temps, une extension du problème RCPSP classique : la consommation en ressource d'une tâche est une fonction du temps linéaire par morceaux et sa durée peut être variable. Une tâche est représentée par une suite de sous-tâches trapézoïdales contigus. Nous présentons ensuite les limites des méthodes de résolution exactes par séparation et évaluation proposées dans la littérature et nous proposons une résolution de cette généralisation du RCPSP en utilisant le langage de Programmation Par Contraintes CHIP. Pour cela, une nouvelle contrainte globale cumulative traitant globalement ce modèle de tâche a été créée et ajoutée au langage CHIP. Elle se nomme cumulative_trapèze et a nécessité l'écriture d'algorithmes efficaces pour le calcul de la partie obligatoire et pour l'élagage des domaines des variables d'une tâche. Les principales difficultés rencontrées lors de sa réalisation contrainte ont résidé dans le traitement de suites d'objets plûtot que de rectangles individuels et dans la gestion d'un profil cumulé des consommations non entier. Enfin, les principales applications sont présentées : modèle Producteur/Consommateur pour la gestion de stock et problèmes de placements