Le 30/03/2009 par ali :

Salut,
Je voudrais savoir que dois -je déterminer une borne supérieur (UB) ou une borne inférieur(LB) pour le problème d'ordonnancement des taches sur deux machines parallèles?
Excusez mon ignorance et merci pour vos explications.

Le 31/03/2009 par medali :

Qu'est ce que vous cherchez à résoudre ?

Le 31/03/2009 par Nassim :

Cela dépend du critère que vous voulez optimiser. Pour un ordonnancement de tâches sur deux machines parallèles, on veut généralement minimiser des critères liés au temps (date de fin d'éxécution, retards, nombre de tâches en retard, stock d'encours). Il faut donc chercher une borne inférieure. Mais, on peut aussi vouloir maximiser certains critères comme le bénéfice ou le retour sur investissement). Là il faut chercher une borne supérieure.
http://www.lix.polytechnique.fr/~durr/query/ est un site qui donne des références bibliographiques et des résultats de complexité en fonction du problème d'ordonnancement à résoudre.

Le 12/05/2009 par ali :

Merci pour votre réponse.

En fait, je n'ai pas compris la méthode exacte (B&B) pour la résolution du problème d'ordonnancement sur machine parallèle avec minimisation des retards.
Mes questions sont : faut il déterminer en premier les règles de dominance ou le schéma de branchement? Ce dernier que s'agit il? Quel algorithme utilisé pour déterminer la borne inférieur? Quand est ce que on utilise le branch and bound?
C'est vrai j'ai de tas de question...Je deviens fou...
Voilà, si vous pouvez m'expliquer par un exemple je serai reconnaissant.
Merci d'avance

Le 27/05/2009 par amine :

Bonsoir,
Le calcul de la borne inférieure et la borne supérieure se diffère selon l'objectif du problème.
Par exemple en cas de maximisation d'un problème en nombre entier, on peut calculer LB en utilisant une heuristique gloutonne et pour calculer UB on peut utiliser le méthode de simplexe en relaxant les variables de décision.
Bon courage

Le 11/06/2009 par ali :

bonjour,
Merci amine pour votre réponse.
D'après ce que j'ai compris, on calcule une borne inférieur (le cas de la minimisation) à l'aide de la relaxation lagrangienne. Après, comment peut-on intégrer cette borne dans l'algorithme branch and bound?
Une autre question peut etre vous parait bete, j'ai trouvé dans quelque papiers que la borne inférieur est une équation et non pas une valeur, comment peut-on la déterminer?
Merci d'avance