Minimisation de la somme des retards pour les problèmes dordonnancement à une machineReport as inadecuate




Minimisation de la somme des retards pour les problèmes dordonnancement à une machine - Download this document for free, or read online. Document in PDF available to download.

1 SAGEP - Simulation, analyse et gestion des systèmes de production INRIA Lorraine

Résumé : 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.

Mots-clés : ordonnancement séquencement arrivées échelonnées minimisation somme des retards propriétés de dominance méthodes approchées analyse dans le pire des cas





Author: Chengbin Chu - Marie-Claude Portmann -

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



DOWNLOAD PDF




Related documents