Ordonnancement d'atelier

Une tâche i est une entité élémentaire de travail localisée dans le temps par une date de début t_i ou de fin c_i, dont la réalisation est caractérisée par une durée p_i (on a ci = ti + pi.) En outre, la tâche i utilise une (ou plusieurs) ressource k avec une intensité aik souvent supposée constante pendant l’exécution de la tâche.

Dans certains problèmes, les tâches peuvent être exécutées par morceaux, l’entrelacement des différents morceaux permettant de laisser le moins possible les ressources inactives. Dans d’autres, au contraire, on ne peut pas interrompre une tâche une fois commencée. On parle alors respectivement de problèmes préemptifs et non préemptifs.

Une ressource k est un moyen technique ou humain requis pour la réalisation d’une tâche et disponible en quantité limitée, sa capacité A_k.

On distingue plusieurs types de ressources. Une ressource est renouvelable si après avoir été utilisée par une ou plusieurs tâches, elle est à nouveau disponible en même quantité (les hommes, les machines, l’espace, etc.) ; la quantité de ressources utilisée à chaque instant est limitée. Dans le cas contraire, elle est consommable (matière première, budget, etc.) ; la consommation globale (ou cumul) au cours du temps est limitée.

On distingue par ailleurs les ressources disjonctives (ou non partageables) qui ne peuvent exécuter qu’une tache à la fois (machine-outil, robot manipulateur) et les ressources cumulatives (ou partageables) qui peuvent être utilisées par plusieurs tâches simultanément (équipes d’ouvriers, poste de travail).

Les contraintes temporelles intègrent en général :

• les contraintes de temps alloué, issues généralement d’impératifs de gestion et relatives aux dates limites des tâches (délai de livraison par exemple) ou à la durée totale d’un projet ;
• les contraintes d’antériorité et plus généralement les contraintes de cohérence technologique, qui décrivent le positionnement relatif de certaines tâches par rapport à d’autres (e.g contraintes de gammes dans le cas des problèmes d’ateliers) ;
• les contraintes de calendrier liées au respect d’horaires de travail, etc.

Ces contraintes peuvent toutes s’exprimer à l’aide d’inégalités de potentiels qui imposent une distance minimale entre deux instants particuliers associées aux tâches (le plus souvent les dates de début).

Les contraintes de ressources traduisent le fait que celles-ci sont disponibles en quantité limitée (leur capacité).
On distingue deux types de contraintes de ressources, liées à la nature disjonctive ou cumulative des ressources.

• Pour les ressources disjonctive, à tout couple de tâches (i,j) utilisant la même ressource est associée la paire de disjonction ${\displaystyle (i<j)\vee (j<i)}$. La paire de disjonction est traduite par : ${\displaystyle (t_{j}\geq t_{i}+p_{i})\vee (t_{i}\geq t_{j}+p_{j})}$. De façon plus simple, les tâches doivent être effectuées l’une après l’autre (i<j ou bien j<i).
• Pour les ressources cumulatives, la somme des besoins en ressource de tâches simultanées doit être inférieure à la capacité des ressources. Soit pour un ordonnancement donné l’ensemble des tâches qui consomment la ressource k à l’instant t : ${\displaystyle T_{k}(t)={i\in 1,...,n{\mbox{ avec }}t\in [t_{i},t_{i}+p_{i}[}}$. Soit a_i l’intensité avec laquelle la tâche i consomme une ressource (on la suppose constante pour chaque tâche i), et Ak la capacité de la ressource k (la quantité disponible k). Alors ${\displaystyle \forall t,\sum _{i\in T_{k}(t)}a_{i}\leq A_{k}}$

Dans ce cas, l’ensemble des tâches à réaliser est fait par une seule machine. Les tâches alors sont composées d’une seule opération qui nécessite la même machine. L’une des situations intéressantes où on peut rencontrer ce genre de configurations est le cas où on est devant un système de production comprenant une machine goulot qui influence l’ensemble du processus. L’étude peut alors être restreinte à l’étude de cette machine.

Dans ce cas, on dispose d’un ensemble de machines identiques pour réaliser les travaux. Les travaux se composent d’une seule opération et un travail exige une seule machine. L’ordonnancement s’effectue en deux phases : la première phase consiste à affecter les travaux aux machines et la deuxième phase consiste à établir la séquence de réalisation sur chaque machine.

Un atelier à cheminement unique est un atelier où le processus d’élaboration de produits est dit « linéaire », c'est-à-dire lorsque les étapes de transformation sont identiques pour tous les produits fabriqués. Selon les types de produits élaborés, on distingue la production continue et la production discrète. La production continue est caractérisée par la fluidité de son processus et l’élimination du stockage. C'est le cas notamment dans les raffineries, les cimenteries, les papeteries... La production discrète de masse s’applique principalement aux produits de grande consommation fabriqués à la chaîne (e.g automobile, la majorité du domaine du textile, machines-outils…).

Dans les deux cas, les machines peuvent être dédiées à une opération précise, et sont implantées en fonction de leur séquence d’intervention dans la gamme de production.

L’un des objectifs principaux dans le cas d’atelier à cheminement unique est de trouver une séquence des tâches en main qui respecte un ensemble de contraintes et qui minimise le temps total de production. Parmi les caractéristiques d’un problème de cette catégorie :

• il existe au minimum n! différentes solutions où n est le nombre de travaux à réaliser. Notons que n! = n*(n-1)*(n-2)….*1 ;
• le problème est NP-difficile à l’exception des versions avec deux machines et certains cas particuliers avec trois machines ;
• une grande productivité mais une faible flexibilité.

Les ateliers à cheminements multiples (ACM) sont des unités manufacturières traitant une variété de produits individuels dont la production requiert divers types de machines dans des séquences variées. L’une des caractéristiques d’un atelier à cheminement multiple est que la demande pour un produit particulier est généralement d’un volume petit ou moyen. Une autre caractéristique est la variabilité dans les opérations et un mix produit constamment changeant. Ainsi, il est nécessaire que le système soit de nature flexible. Dans un sens général, la flexibilité est la capacité d’un système de répondre aux variations dans l’environnement.

L’objectif le plus considéré dans le cas d’un atelier à cheminements multiples est le même que celui considéré pour un atelier à cheminement unique, à savoir trouver une séquence de tâches sur les machines qui minimise le temps total de production.

La figure suivante montre un exemple d’un atelier à cheminements multiples avec quatre travaux et six machines.

Parmi les caractéristiques d’un problème d’ordonnancement dans un atelier à cheminements multiples :

• le nombre de solutions possibles est de l’ordre de (n!)m, où n est le nombre de tâches à effectuer et m le nombre de machines. Notons qu’une tâche veut dire la même chose qu’un travail.
• le problème est NP-difficile et est considéré parmi les problèmes les plus difficiles à traiter.

Les principales catégories, que sont les ateliers à production linéaire (Flow Shop) et les ateliers à cheminement multiple (Job Shop) ne sont pas les seuls modèles dans l’industrie. Plusieurs autres catégories intermédiaires existent, dont les plus connues sont :

• les ateliers de type flow shop hybride : il s’agit d’ateliers flow shop dans lesquels un « étage » donné de la fabrication peut être assuré par plusieurs machines en parallèle. Dans ce genre d’ateliers, tout travail passe par chaque étage et l’ordre de passage sur les étages est le même pour chaque travail. Ce type d’ateliers est également appelé « atelier à cheminement unique avec machines en exemplaires multiples » ;
• les ateliers à cheminement libre (open shop) : chaque produit à traiter doit subir un ensemble d’opérations sur un ensemble de machines, mais dans un ordre totalement libre ;
• les ateliers flexibles : ces ateliers sont caractérisés par un niveau d’automatisation élevé, cherchant par là un compromis entre flexibilité et productivité. Ils sont à la base des ateliers à cheminements multiples où les principales tâches (stockage, traitement de pièces, manutention…) sont automatisées.