Une Recherche par faisceaux avec récuperation des erreurs pour le 
problème d'ordonnancement à une machine de type juste-a-temps.

Bertrand Estève et Vincent T'kindt. 
Ecole Polytechnique de l'Université de Tours.
Département Informatique.

Mots clefs : Ordonnancement de type Juste-a-Temps; Optimisation
multicritere; Recherche par faisceaux avec recuperation des erreurs.

Dans cette etude, nous considerons les problemes d'ordonnancement de type
Juste-A-Temps en apprehendant la notion de Juste-A-Temps au moyen de
multiples criteres conflictuels. Le calcul d une solution strictement non
dominee pour ces critères est realise en resolvant une extension du probleme
d ordonnancement à une machine et dates dues donnees et distinctes ou l on
cherche a minimiser la somme ponderee des deviations ( avance ou retard dans
l execution de chaque travail ). En fait l'extension reside en deux donnees
supplementaires par travail : une date de disponibilite et une date de fin
imperative. Ce probleme est NP-difficile au sens fort et nous proposons des
heuristiques pour le resoudre. Les resultats experimentaux vont dans le sens
d une efficacite particuliere de l heuristique appelee parfois RBS (
Recovering Beam Search ) : PSE en largeur d abord, tronquee, amelioree.
Cette recherche par faisceaux filtree est amelioree par une phase de
recuperation des erreurs potentielles à chaque niveau de l arborescence. Une
comparaison avec un modèle mathématique sous Cplex pour les petits jeux de
données et avec une descente locale est discutée.