Minimisation de la somme des retards pour les problèmes d'ordonnancement à une machine

Dans cet article, nous démontrons un théorème qui présente une condition suffisante d'optimalité locale pour le problème d'ordonnancement du type n/1/ri/\sumTi. Cette condition nous permet de définir un nouveau sous-ensemble dominant de solutions pour ce problème qui est NP-difficile. Nous utilisons les résultats obtenus pour construire un algorithme approché polynômial et donnons une majoration de l'erreur commise par cet algorithme dans le pire des cas