Issue |
RAIRO-Oper. Res.
Volume 35, Number 2, April June 2001
ROADEF'99
|
|
---|---|---|
Page(s) | 143 - 163 | |
DOI | https://doi.org/10.1051/ro:2001109 | |
Published online | 15 August 2002 |
Multicriteria scheduling problems: a survey
1
Laboratoire d'Informatique, École d'Ingénieurs en Informatique pour
l'Industrie, 64 avenue Jean Portalis, 37200 Tours, France; tkindt@e3i.univ-tours.fr.
2
Laboratoire d'Informatique, École d'Ingénieurs en Informatique pour
l'Industrie, 64 avenue Jean Portalis, 37200 Tours, France; billaut@e3i.univ-tours.fr.
Received:
May
1999
This paper presents a state-of-the-art survey on multicriteria scheduling and introduces a definition of a multicriteria scheduling problem. It provides a framework that allows to tackle multicriteria scheduling problems, according to Decision Aid concepts. This problem is decomposed into three different problems. The first problem is about obtaining a model. The second one is how to take criteria into account and the third one is about solving a scheduling problem. An extension to an existing notation for scheduling problems is proposed for multicriteria scheduling problems. Then, basic results from the literature on multicriteria optimization are presented. These results are used to build the final scheduling problem to solve. Finally a survey is presented for one-machine, parallel machines and flowshop multicriteria scheduling problems.
Résumé
Ce travail présente un état de l'art sur les problèmes d'ordonnancement multicritères et introduit une nouvelle définition de ces problèmes. Nous proposons également une démarche, conforme aux principes de l'aide multicritère à la décision, pour aborder les problèmes d'ordonnancement multicritères. Ces problèmes sont décomposés en trois sous-problèmes. Le premier concerne la modélisation du problème d'ordonnancement considéré. La résolution du second sous-problème conduit à répondre à des questions : comment prendre en compte les critères pour calculer des optima de Pareto ? Quel type d'algorithme faut-il mettre au point ? Le troisième sous-problème concerne la résolution du problème d'ordonnancement qui découle des deux sous-problèmes précédent. Nous proposons également dans ce travail une extension de la notation classique des problèmes d'ordonnancement au cas multicritère. Nous présentons ensuite les résultats de base de l'optimisation multicritère avant de détailler notre état de l'art sur les problèmes d'ordonnancement multicritères à une machine, à machines parallèles et de type flowshop.
Key words: Scheduling / multicriteria optimization / state-of-the-art.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.