The complexity of single machine scheduling problems under scenario-based uncertainty
Della Croce, Federico; Aloulou, Mohamed Ali (2008), The complexity of single machine scheduling problems under scenario-based uncertainty, in Paschos, Vangelis, Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADE, Wiley : Hoboken NJ, p. 23-36
Type
Chapitre d'ouvrageExternal document link
http://hal.archives-ouvertes.fr/hal-00115501/en/Date
2008Book title
Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADEBook author
Paschos, VangelisPublisher
Wiley
Published in
Hoboken NJ
ISBN
978-1-8482-1021-9
Number of pages
515Pages
23-36
Metadata
Show full item recordAbstract (FR)
Nous considérons des problèmes d'ordonnancement où certains paramètres des tâches sont incertains. Cette incertitude est modélisée au travers d'un ensemble fini de scénarios bien définis. Nous cherchons une solution qui soit acceptable pour l'ensemble des scénarios considérés. Plusieurs critères ont été utilisés dans la littérature pour sélectionner la “meilleure” solution. Nous utilisons ici le critère appelé robustesse absolue. Nous présentons des résultats algorithmiques et de complexité pour quelques problèmes classiques d'ordonnancement sur une machine.Abstract (EN)
We consider scheduling environments where some job characteristics are uncertain. This uncertainty is modeled through a finite set of well-defined scenarios. In such a context, we search for a solution that is acceptable for any considered scenario. For this purpose, several criteria can be applied to select among solutions. We use here the so-called absolute robustness criterion. We present algorithmic and computational complexity results for several single machine scheduling problems.Subjects / Keywords
Absolute robustness; Scenario-based uncertainty; Scheduling; robustesse absolue; Scénarios; Données incertaines; OrdonnancementRelated items
Showing items related by title and author.
-
Della Croce, Federico; Aloulou, Mohamed Ali (2008) Article accepté pour publication ou publié
-
Portmann, Marie-Claude; Kovalyov, Mikhail Y.; Aloulou, Mohamed Ali (2007) Article accepté pour publication ou publié
-
Aissi, Hassene; Aloulou, Mohamed Ali; Kovalyov, Mikhail Y. (2011) Article accepté pour publication ou publié
-
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2004) Article accepté pour publication ou publié
-
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2003) Communication / Conférence