Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

Chapitre 2

Présentation des méthodes de

résolution

Présentation des méthodes de résolution 26

Introduction

Pour la résolution de notre problème, on a optépour les méthodes approchées étant donnéles avantages qu'elles offrent telles que la rapiditéde leurs exécutions, leurs flexibilité¹.

Dans le présent mémoire, on a travailléavec des méta-heuristiques bien confirmées notamment la recherche taboue et le recuit simulé. En ce qui concerne les heuristiques, on a adaptéet implémentédes heuristiques spécifiques très connues à savoir le fameux algorithme de Johnson, l'heuristique de Palmer, l'heuristique NEH et l'heuristique de Potts. On a aussi établie sept heuristiques qui se basent essentiellement sur les principes des heuristiques spécifiques de la littérature.

Afin d'évaluer les heuristiques et les méta-heuristiques, et en absence d'une approche exacte, on avait besoin de borner les résultats pour pouvoir évaluer leurs qualités, on a donc établie des bornes inférieures qui seront notre repère d'évaluation.

1. La possibilitéde l'adaptation d'une heuristique à plusieurs problèmes différents ainsi que la possibilitéd'hybridation avec d'autres méthodes.

Présentation des méthodes de résolution 27

2.1 Bornes Inférieures

On utilise la borne inférieure afin de pouvoir borner la solution optimale d'une instance et par la suite évaluer les solutions données par les heuristiques et les méta-heuristiques. Même dans les méthodes de résolution exactes notamment les procédures par séparation et évaluation, la notion de borne inférieure est primordiale car elle permet d'évaluer les racines non prometteuses et par la suite éviter de perdre un temps de calcul important.

En vue d'évaluer les heuristiques et les méta-heuristiques utilisées on a établie cinq bornes inférieures.

2.1.1 Borne inférieure 1

On part du principe qu'on ne peut pas échapper aux maximums des temps d'achèvement lorsque les jobs sont pris un à un.

BI1 = max{ri + ai + bi + qi} (2.1)

i?J

2.1.2 Borne inférieure 2

Il est clair qu'on ne peut pas échapper à l'ensemble des temps opératoires sur la machine commune. Cette borne est améliorépar la prise en compte des minimums des autres durées. Cette borne s'écrit comme suit :

BI2 = min{ri} + i?J

?n i=1

ai + min{bi + qi} (2.2) i?J

OùC* _max(1 ri _Cmax) est la date d'achèvement optimale si on considère uniquement la machine commune et la date de disponibilité.