Analyse dintervalles pour lordonnancement dactivitésReport as inadecuate




Analyse dintervalles pour lordonnancement dactivités - Download this document for free, or read online. Document in PDF available to download.

1 LAAS-MOGISA LAAS - Laboratoire d-analyse et d-architecture des systèmes Toulouse

Abstract : This work focuses on the interests of interval analysis in scheduling. The analysis of intervals considers the order relation Allen-s algebra among the execution intervals of the tasks or their processing time intervals in order to deduce useful problem properties. For several kinds of scheduling problems, we particularly show how interval analysis allows defining dominance-based optimality conditions or sufficient conditions of feasibility, which characterize remarkable sets of schedules. Using these conditions, taking an interest in some one machine scheduling problems, we establish new and efficient integer-linear-programming formulations. Since the dominance conditions are relatively insensitive to variations of schedule parameters, we also show the interest of such conditions for characterizing a set of robust schedules. We also present some other works also based on interval analysis.

Résumé : Ce travail s-attache à décrire l-intérêt de l-analyse d-intervalles en ordonnancement. L-analyse d-intervalles considère les relations d-ordres existantes algèbre de Allen entres certains intervalles caractéristiques des tâches à ordonnancer. On montre comment, pour certains problèmes particuliers, elle permet de définir des conditions de dominance ou des conditions suffisantes d-optimalité, caractérisant des ensembles remarquables de solutions. Dans le cas de certains problèmes à une machine réputés difficiles, nous montrons comment de telles conditions peuvent être utiles pour déduire des nouvelles formulations de programmation linéaire en nombres entiers très efficaces. De plus, les conditions étant relativement indépendantes des valeurs numériques du problème, on montre aussi leur intérêt pour la caractérisation d-ensembles flexibles et robustes de solutions. D-autres travaux seront également évoqués dans lesquels la notion d-intervalle est centrale.

en fr

Keywords : Scheduling Integer linear programming Dominance conditions Uncertainty

Mots-clés : Ordonnancement Programmation linéaire en nombres entiers Conditions de dominance Incertitudes





Author: Cyril Briand -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents