Enumération en ordonnancement multicritère : application à un problème bicritère à machines parallèles
Institution:
ToursDisciplines:
Directors:
Abstract EN:
Numerous scheduling problems were the subject of many studies in the literature. But the majority of them are related to the solutions of problems with a single criterion, although real life is quite different since problems often involves multiple criteria. The solution of this kind of problem consists in finding a set of points corresponding to the best tradeoffs between different criteria. These points are called Pareto Optima. Numerous solutions methods are present in the literature to solve multicriteria scheduling problems. Some of these methods are based on the determination of only one Pareto optimum. Others are based on the enumeration of all the Preto optima. A synthesis of these methods is presented in [T4Kindt and Billaut 2006]. In this PhD thesis we start by tackling an important point of combinatorial optimisation : that of complexity theory when dealing with the counting or enumeration of pareto optima in the case of multicriteria optimisation. A synthesis of this part was proposed in [T'Kindt et al. , 2005]. Then we focus on the comparison of threee methods of enumeration of strict Pareto Optima for the uniform parallel machines scheduling problem, Q|ri,di,Cmax,Lmax. The first is based on the e-constraint approach ([Klein and Hannan, 1982]), the seconde method is the two phases method which was initialy proposed by [ulungu and Teghem, 1995] to solve a bicriteria knapsack problem. The last method is the branch, bound and delay procedure which is based on the exploration of a search tree whose nodes are built only once.
Abstract FR:
Les problèmes d'ordonnancement ont fait l'objet de nombreuses études dans la littérature. Mais la plupart d'entres elles portaient sur la résolution de problèmes à critère unique, malgré que la réalité est bien différente et que les domaines d'application font intervenir différents critères. Dans un contexte appliqué un problème d'ordonnancement est par nature multicritère ([Roy, 1985]). La résolution de ce type de problème consiste à trouver un ensemble de points correspondant aux meilleurs compromis possibles entre les différents critères, ces points sont appelés optima de pareto. De nombreuses méthodes de résolution ont vu le jour pour résoudre des problèmes d'ordonnancement multicritères. Certaines de ces méthodes sont basées sur la détermination d'un seul optimum de Pareto. D'autre sont basées sur l'énumération de tous les optima de Pareto. Un panorama de telles méthodes est disponible dans [T'Kindt and Billaut, 2006]. Dans le cadre de notre étude nous nous sommes concentré sur la comparaison de trois méthodes d'énumération des optima de Pareto stricts pour résoudre un problème d'ordonnancement bicritère à machines parallèles uniformes Q\ri, di\Cmax, Lmax. La première méthode de base sur l'approche e-contrainte ([Klin and Hannan, 1982]), la deuxième méthode est la méthode à deux phases proposée, initialement par [Ulungu and Teghem, 1995] pour résoudre un problème de sac à dos bicritère. La dernière méthode d'énumération est la procédure par séparation, évaluation et retardement qui se base sur l'exploration d'un arbre de recherche dont les noeuds ne sont construits qu'une seule fois. Il s'agit d'une méthode que nous proposons.