Flow-shop

Flow-shop

Le flow-shop est un problème d'ordonnancement d'atelier.

Sommaire

Description

Le flow-shop définit un ensemble de n tâches et m machines. Les contraintes du problème sont de deux types :

  • les contraintes de gamme, toutes les tâches doivent passer sur toutes les machines, de la machine 1 à la machine m ;
  • les contraintes de ressource, une machine ne peut traiter qu'une tâche à la fois.

En général, on cherche des solutions telles que les tâches ne peuvent pas se doubler, elles passent dans le même ordre sur toutes les machines, c'est ce qu'on appelle flowshop de permutation.

Dans le cas le plus simple, les données du problème sont les temps que chaque tâche passe sur chaque machine, soit une matrice dans M_{nm}(\mathbb{R}^{+}), dont les coefficients seront nommés pij (temps pour passer par la tâche i sur la machine j).

Les fonctions objectif sont généralement :

  • Cmax, date de fin de la dernière tâche sur la machine m, soit le temps total passé à exécuter tous les travaux ;
  • \Sigma^{n}_{i=1} c_i, somme des dates de fin des tâches sur la machine m.

Algorithmes de minimisation de cmax

Les algorithmes présentés dans cette section ont pour but de minimiser la durée totale du traitement.

Flowshop à deux machines

Le problème se résout de manière optimale par l'algorithme de Johnson[1].

Soient deux partitions de l'ensemble des tâches U = {i / pi1 < pi2} et V = \{i / p_{i1} \geq p_{i2}\}

  • trier les tâches de U par pi1 croissant
  • trier les tâches de V par pi2 décroissant
  • la séquence optimale est constituée de la concaténation des séquences U et V ainsi triées

L'algorithme a une complexité de l'ordre en nlog(n), puisqu'il consiste avant tout à exploiter des algorithmes de tri.

Cas à plus de deux machines

Au-delà de deux machines, le flow-shop est un problème NP-difficile, il n'existe pas l'algorithme menant à une solution optimale en temps polynomial, des heuristiques permettent néanmoins d'obtenir des solutions intéressantes.

Nawaz-Enscore-Ham (NEH)

  • Trier les travaux par \sum_{j=1}^{n} p_{ij}
  • Ordonnancer les deux premiers dans l'ordre le plus intéressant
  • Pour i = 3 à n Faire
    • Insérer le travail i dans la position k \in [1,i] la plus intéressante
  • Fin Pour

Campbell Dudek Smith

Notes et références

  1. ↑ S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

Voir aussi

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Flow-shop de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Flow table test — These images show a flow test with very fluid concrete for a special application which made compression impossible.The flow table test or flow test is a method to determine the consistence of fresh concrete.ApplicationWhen fresh concrete is… …   Wikipedia

  • The Little Shop of Horrors — Infobox Film name = The Little Shop of Horrors image size = caption = Theatrical release poster. director = Roger Corman producer = Roger Corman writer = Charles B. Griffith narrator = starring = Jonathan Haze Jackie Joseph Mel Welles Dick Miller …   Wikipedia

  • Zanka Flow — Zanka Flow, Muslim Et Yes N est un groupe de Rap Underground Marocain (Rap Arabe). Muslim Nom de naissance Mohamed Mezouri (arabe  …   Wikipédia en Français

  • Zanka flow — Zanka Flow, Muslim Et Yes N est un groupe de Rap Underground Marocain (Rap Arabe). Muslim Nom de naissance Mohamed Mezouri (arabe  …   Wikipédia en Français

  • Global Shop Solutions — is an Enterprise Resource Planning software (ERP) company that targets small to medium sized manufacturers, job shops, or make to order companies. Located in The Woodlands, Texas, Global Shop Solutions also has offices in Boston, Chicago, Los… …   Wikipedia

  • Job shop — Job shops are typically small manufacturing operations that handle specialized manufacturing processes such as small customer orders or small batch jobs. Job shops typically move on to different jobs (possibly with different customers) when each… …   Wikipedia

  • The Butcher Shop — Infobox Album | Name = The Butcher Shop Presented By Esham Type = Compilation Artist = Various Artists Released = March 25th 2008 Recorded = 2008 Genre = Acid rap, horrorcore, Midwest hip hop Length = 77:58 Label = Reel Life Productions Gothom… …   Wikipedia

  • Tony Flow & The Miraculously Majestic Masters of Mayhem — Red Hot Chili Peppers Die Red Hot Chili Peppers live im Jahre 2006 Gründung 1983 Genre Funk Rock, Alternative Rock, Crossover Webs …   Deutsch Wikipedia

  • Ordonnancement d'atelier — L ordonnancement d atelier consiste à organiser dans le temps le fonctionnement d un atelier pour utiliser au mieux les ressources humaines et matérielles disponibles dans le but de produire les quantités désirées dans le temps imparti. Sommaire… …   Wikipédia en Français

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”