TITRE : Maximiser la flexibilité sur une machine et dans un 
job shop à l'aide d'un ordonnancement de groupes.

AUTEURS : C. ESSWEIN, C. ARTIGUES et J-C. BILLAUT

Résumé :
Il n'est plus guère nécessaire de débattre de la nécessité 
d'apporter de la flexibilité à la solution d'un problème 
d'ordonnancement. Nous proposons d'apporter cette flexibilité 
en caractérisant un ensemble d'ordonnancements, sans avoir à 
énumérer ses éléments. Ceci peut se faire en déterminant, 
plutôt qu'un ordonnancement unique, un ordonnancement de 
groupes, c'est-à-dire en définissant une séquence de groupes 
d'opérations permutables sur chaque machine. Toute combinaison 
des permutations des opérations au sein de chaque groupe conduit 
à une solution faisable et dont la qualité reste inférieure à une 
valeur garantie.

Dans un premier temps nous présentons des méthodes permettant de 
maximiser la flexibilité dans deux problèmes à une machine : l'un 
avec des deadlines et l'autre avec des dates de disponibilités et 
des deadlines. Dans un second temps nous proposons une heuristique 
utilisant ces méthodes et permettant de déterminer une solution de 
compromis entre qualité et flexibilité dans un environnement de 
type job shop. Des résultats expérimentaux sur des benchmarks de la 
littérature montrent l'intérêt de la méthode.