Les problèmes d'ordonnancement de type flow-shop hybride : état de l'art

École d'Ingénieurs en informatique pour l'Industrie, Université Laboratoire d'Informatique, 64 avenue J. Portalis, 37200 Tours, France, e-mail: vignier@univ-tours.fr

Received: September 1995

Abstract

A special class of scheduling problems is studied in this paper, named Hybrid Flowshop, n jobs have to be performed in a shop and each of them has the same routing (so this is a flowshop). A job consists in k different operations. A set of machines are able to perform each operation and this set is called a stage. So when a job consists in two operations, there are two stages in the shop. After introducing the scheduling generalities, we define our preocupations and we propose a notation in order to identify precisely and rapidly a problem. Then a state of the art is proposed and presented in two parts. The first one is dedicated to the 2-stage hybrid flowshops and the second to the general case of the k-stage. Then a summary puts to the fore that many problems remain unsolved.

Résumé

Nous nous proposons d'étudier ici une famille de problèmes d'ordonnancement, caractérisés par un ensemble de travaux comportant un enchaînement identique d'opérations sur différents étages d'un outil de production. Chaque étage, ou pool, est constitué d'un ensemble de machines, susceptibles de fabriquer les produits avec plus ou moins d'aptitude. Ce problème se nomme habituellement “flow-shop” hybride. Après une introduction aux problèmes d'ordonnancement en général, nous définissons plus précisément notre préoccupation, nous proposons une notation permettant d'identifier clairement et rapidement un problème donné, puis nous abordons un état de l'art comportant deux parties : les problèmes à deux étages, puis ceux à k étages. Un tableau de synthèse et une typologie mettent en évidence le peu de problèmes déjà traités.