Avant les problèmes de job shop sont considérés comme des problèmes simples dont les déplacements des pièces d’une machine à une autre n’étaient pas pris en compte dans le calcul de l’ordonnancement ou bien sont considérés intégrés dans la tâche elle-même. Or, cette hypothèse est souvent non justifiée en pratique. En effet, le transport des tâches doit être intégré aux données du problème.

Le Problème d’ordonnancement Job-Shop

Atelier à cheminement multiple (job shop)

Dans un atelier de type job shop chaque tâche emprunte un chemin qui lui est propre, En effet les tâches ne s’exécutent pas sur toutes les machines dans le même ordre. Ce type d’organisation correspond généralement à une production par lot, notamment dans une unité de production disposant de moyens polyvalent utilisés suivent des séquences différentes afin de réaliser des produit divers .

Si, pour chaque machine, on dispose d’un et un seul exemplaire, on dit que l’organisation est un Job Shop simple. Si, au contraire, pour un au moins des machines (postes de travail), on dispose de plus d’un exemplaire, on l’appelle Job Shop Hybride.

Types de job shop 

Job shop classique
Le problème d’ordonnancement de job shop constitue l’un des problèmes d’ordonnancement d’atelier les plus étudié dans la littérature, les variations autour du problème de job shop sont nombreuses et il n’est pas possible de trouver dans la littérature une formulation unique de celuici. Nous présentons ici la formulation la plus générale possible du problème de job shop simple. Le problème d’ordonnancement de type job shop consiste à réaliser un ensemble de n jobs sur un ensemble de m machines. En cherchent d’attendre certains objectifs. Chaque job Ji est composé d’une suite de ni opérations devant être exécutées sur les différentes machines selon un ordre préalablement défini. Par ailleurs, un ensemble de contraintes concernant les machines et les tâches souvent existées, comme :
– Les machines sont indépendantes les unes des autres.
– Une machine ne peut exécuter qu’une seule opération à la fois à un instant donné.
– Les machines sont disponibles pendant toutes la durée de l’ordonnancement.
– Les jobs sont indépendants les uns des autres. En particulier, il n’existe aucun ordre de priorité attaché aux jobs.

Job shop flexible
Le job shop flexible est une extension du modèle job shop classique. Sa particularité essentielle réside dans le fait que chaque opération peut être exécutée sur plusieurs machines. Dans ce modèle, les machines qui effectuent la même opération sont groupées dans un même étage. Il s’ensuit qu’il offre plus de flexibilité par rapport au job shop classique grâce à la polyvalence de ces machines. Toutefois, cela induit une complexité supplémentaire due à la nécessité de la détermination des affectations adéquates avant d’établir l’ordre de passage des différentes opérations sur les machines.

Une remarque importante dans les problèmes de type job-shop hybride est que le nombre de machines peut varier d’un étage à l’autre, ainsi que les performances des machines qui ne sont pas forcément les mêmes pour toutes les machines d’un même étage. Ces performances nous permettent de classer les systèmes avec machines parallèles en trois groupes, à savoir :
– Machines identiques : La durée d’exécution d’une tâche est la même sur toutes les machines.
– Machines uniformes : La durée d’exécution d’une tâche est similaire sur toutes les machines.
– Machines indépendantes : La durée d’exécution d’une opération dépend de la machine sur laquelle elle est exécutée.