WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

L'utilisation de la programmation mathématique pour la résolution d'un problème « car-sequencing »

( Télécharger le fichier original )
par Attafi Meriem & Zghidi Imen
FSEGS -  2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

CHAPITRE 3

LES METHODES DE RESOLUTION DU PROBLEME D'ORDONNACEMENT

3.1 Introduction :

Plusieurs auteurs [Mac Cathy & Liu 93, ESSWEIN 03] partitionnent les méthodes de résolution en 3 classes : les méthodes optimales efficaces, les méthodes énumératives et les méthodes heuristiques.

· Les méthodes optimales énumératives sont aussi des algorithmes exactes elles fournissent en pratique sur des problèmes de taille moyenne, des solutions optimales en un temps raisonnable .Dans cette classe, on peut distinguer :

ü Les procédures par séparation et évaluation progressive (SEP) (Branch&Bound) qui énumèrent par une recherche arborescente un ensemble de solution en éliminant les branches de l'arbre de recherche montrées non-optimales (utilisation de bornes inférieure et supérieure du critère)

ü Les méthodes de programmation linéaires (PL) modélisant les critères et les contraintes comme des fonctions linéaires de variables mixtes (réelle, entier).

ü Les méthodes basées sur la programmation dynamique (PD) qui se décomposent en sous problème, que l'on résout optimalement à rebours, en tenant compte du sous-problème précèdent.

· Les méthodes heuristiques sont souvent utilisées pour traiter des problèmes que les méthodes optimales sont incapables de les résoudre en un temps acceptable .Elles produisent généralement une solution faisable de bonne qualité en un temps relativement court. La qualité d'une heuristique doit être évaluée sur plusieurs jeux d'instance de taille variable afin de mesurer d'une part la déviation moyenne du critère par rapport à sa valeur optimal et d'autre part l'évolution du temps de calcul en fonction de la taille ou de la structure du problème. Ces heuristiques sont classifiées en trois grands types :

ü les algorithmes gloutons dans lesquels les décisions d'ordonnancement sont prises progressivement, à temps croissant, au fur et à mesure que les ressources se libèrent, grâce à des règles de priorité simples de type SPT(Shortest Processing Time), EDD(Earliest Due Date), etc. ; et pour lesquels on ne remet jamais en cause une décision qui a été prise.

ü les méthodes de recherche locale (tabou, recuit simulé, algorithmes génétiques, etc.) qui, partant d'une solution initiale, définissent un voisinage, qui est ensuite exploré pour trouver des solutions meilleures ; (en s'autorisant parfois à dégrader la solution courante pour augmenter la chance d'obtenir une solution meilleure).

ü les méthodes de recherche arborescente tronquée, proches des PSE, excepté que l'arbre de recherche est volontairement restreint, quitte à perdre des solutions optimales, afin de gagner en temps de calcul.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Nous devons apprendre à vivre ensemble comme des frères sinon nous allons mourir tous ensemble comme des idiots"   Martin Luther King