TP1 Outils d'Aide À la Décision





télécharger 8.73 Kb.
titreTP1 Outils d'Aide À la Décision
date de publication22.09.2017
taille8.73 Kb.
typeDocumentos
m.20-bal.com > comptabilité > Documentos
TP1 Outils d'Aide À la Décision

Introduction et Heuristiques pour le Flowshop

Partie 1.

Télécharger le fichier .rar qui se trouve ici : http://www.isima.fr/~lacomme/TPRO/graphe.rar

Il s’agit d’un graphe qui ressemble au graphe suivant :

Faire un programme « simple » permettant de lire le graphe et de calculer le plus court chemin du nœud i au nœud j.

Partie 2.

Description : le Flowshop de permutation est un des problèmes d'ordonnancement en atelier les plus simples. On considère produits devant passer sur machines, dans le même ordre (par exemple découpe, ébavurage, polissage, traitement de surface, peinture, séchage). Le temps de passage du produit sur la machine est spécifique à chaque produit et chaque machine. Deux conditions sont nécessaires pour qu'un produit sur la machine puisse passer à la machine suivante : l'opération sur la machine courante doit être terminée et la machine doit avoir terminé l'opération sur le produit précédent (elle doit être libre). La séquence de passage des produits sur les machines est la même quelle que soit la machine. On cherche donc la séquence des produits optimisant un critère de production. On considèrera ici le critère du makespan (durée totale d'activité de l'atelier) que l'on cherchera à minimiser. Pour le Flowshop, le makespan correspond à la date de fin de traitement de la dernière machine sur le dernier produit de la séquence, si le premier produit commence sur la première machine à .

Instances : le jeu d'instances le plus connu pour le Flowshop de permutation a été généré par Éric Taillard. Il est disponible à l'adresse suivante : http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html ou recherche Google sur Éric Taillard. Chaque fichier contient 10 instances de même taille, avec des temps de traitement différents. Pour chaque instance, les deux premières lignes contiennent la description de l'instance (nombre de produits, nombre de machines ainsi qu'une borne inférieure et supérieure sur la makespan optimal)

Heuristique : parmi les nombreuses heuristiques proposées, on s'intéressera à l'heuristique NEH (Nawaz, Enscore, Ham) qui repose sur l'algorithme suivant

  • trier les produits selon leur temps total décroissant

  • prendre les deux premiers et les placer dans l'ordre le plus intéressant

  • pour chaque produit suivant, l'insérer dans la position la plus intéressante au sens du makespan

Travail à réaliser :

  1. télécharger les instances

  2. générer un code permettant de lire et afficher une instance et d'évaluer une séquence

  3. implémenter une heuristique basique ne faisant que la première étape de NEH

  4. implémenter NEH

  5. générer un script permettant de tester NEH sur toutes les instances

  6. produire un tableau reportant, pour chaque instance, les bornes inf et sup, la valeur obtenue par NEH, son temps de calcul et l'écart relatif par rapport à la borne inf.

  7. (facultatif) randomiser NEH en choisissant la place de chaque produit au hasard parmi les α% meilleurs

similaire:

TP1 Outils d\Cdd ingénieur pour coordination d’essais multi-locaux et de conception...
«Quels couverts de plantes de services associer au colza et au blé pour remplir un bouquet de services écosystémiques ?»

TP1 Outils d\Document d'aide à la décision pour les maitres
«bonne» décision, la meilleure est celle qui nous procure apaisement et sensation de respect de la relation et de la confiance de...

TP1 Outils d\Analyser les couts pour l’aide a la decision

TP1 Outils d\Outils de sélection / outils de création / outils vectoriels

TP1 Outils d\Programme 101
«aide juridictionnelle», IL s’agit de vérifier que les justiciables éligibles à l’aide juridictionnelle ont bien vu leur demande...

TP1 Outils d\TP1 : prise en main d’arcview 3

TP1 Outils d\Traitement de l’image (Photofiltre) : fonctionnement de la classe
«je l’ai déjà fait Chaque fois qu’un élève a besoin d’aide, IL doit vérifier dans le tableau si un de ses camarades peut lui apporter...

TP1 Outils d\Traitement du son (Audacity) : fonctionnement de la classe
«je l’ai déjà fait Chaque fois qu’un élève a besoin d’aide, IL doit vérifier dans le tableau si un de ses camarades peut lui apporter...

TP1 Outils d\Les conséquences de l’admission à l’aide sociale pour les prestations...

TP1 Outils d\L’entreprise verte et les boues rouges
«verte» en anticipant les éventuelles conséquences de cette décision. Pechiney entame ainsi un exercice de responsabilité sociétale...





Tous droits réservés. Copyright © 2016
contacts
m.20-bal.com