Philippe Chrétienne (LIP6, Paris)

"Introduction à l'ordonnancement sans temps mort"

Cet exposé introduit d'abord la notion générale d'ordonnancement sans temps-mort. Pour  le problème à une machine,
quelques propriétés concernant la complexité et la structure des solutions sont établies, en particulier l'existence
pour toute instance d'une date absolue de début au plus tôt de tout ordonnancement sans temps mort. On s'intéresse
alors aux problèmes pour lesquels chaque instance possède une solution optimale commençant à sa date absolue au plus
tôt et l'on établit que les problèmes préemptifs et les problèmes non-préemptifs pour lesquels les ordonnancements
sans attente "forcée" sont dominants satisfont cette propriété. Certains problèmes à durée commune sont également
résolus polynomialement. Pour le problème à machines identiques parallèles, on montre que les versions sans-temps
mort de certains problèmes classiques restent polynomiales mais que le problème reste ouvert pour d'autres problèmes
très basiques comme P/p(i)=1,r(i),d(i)/?