Optimisation logique du fonctionnement d’un atelier

 Ordonnancement : définitions et notations

Largement étudiés dans la littérature, les problèmes liés à la gestion de la production au sein d’un atelier, où les décisions sont relatives à l’ordre de passage des tâches sur un ensemble de serveurs (machines) sont décrits comme des problèmes d’ordonnancement de tâches. Ce type de problèmes fait partie des décisions comprises dans la gestion opérationnelle à court terme, qui inclut également des décisions de gestion de stock, personnel, emplacement des équipements, la conception des lignes de production, entre autres.

Plusieurs définitions de l’ordonnancement ont été établies dont celle donnée par Graham et al. [54] qui a introduit une classification utilisant une nomenclature sur trois champs. Le concept d’ordonnancement est toujours lié à un ensemble de tâches N qui doivent être affectées à des machines, tout en respectant des contraintes au niveau des caractéristiques des tâches ou machines, ainsi que relatives à l’organisation de l’atelier. C’est ainsi que la classification sur trois champs [54] propose une structure α/β/γ, où le champ α décrit la structure du problème, le champ β contient les contraintes d’ordonnancement à respecter, et le champ γ présente l’objectif à optimiser.

L’environnement des machines (le champ α)

Le type de problème est représenté par deux sous-champs. Le premier sous-champ contient la configuration de l’atelier : – Ø→ Une seule machine – P → machines identiques en parallèle : pour une tâche i et M machines, pi,j = pi (j = 1, …, M) 22 Chapitre 1 : Introduction : Contexte de recherche – Q → machines uniformes en parallèle : pour une tâche i et M machines, pi,j = qjpi (j = 1, …, M), avec qj un facteur de vitesse relatif à chaque machine.

– R → machines indépendantes en parallèle : pour une tâche i et une machine j, le temps de traitement de la tâche i est donné par pi,j – O → machines travaillant sur la structure Openshop (à cheminement libre) – F → les machines effectuent des opérations en suivant un cheminement unique (Flowshop) pour tout produit – J → les machines effectuent des opérations avec un cheminement qui dépend du produit (Jobshop) Le deuxième sous-champ contient le nombre de machines à considérer. Si cette valeur est un entier fixe, le nombre de machines est égal à cette valeur. Si ce sous champ contient m, le nombre de machines est variable, mais supérieure à 1. Si le premier sous-champ est vide, le deuxième sous-champ reste vide ou égale à 1. 

Les contraintes d’ordonnancement (le champ β)

Six sous-champs peuvent être utilisés pour définir les contraintes d’ordonnancement. En fait, cela résume l’information des tâches et des machines qui peut limiter l’espace de solutions possibles. Les sous-champs sont les suivants : – pmtn, Ø→ Le cas où les tâches peuvent être interrompues est marqué avec pmtn. Pour tout autre cas, le sous-champ est laissé vide. – res, res1, Ø→ La présence des ressources (res, res1) supplémentaires est compris. Pour le cas sans ressources supplémentaires, le sous-champ est laissé vide. – prec, treee, Ø→ Les relations de précédence (prec) sont marquées, avec des précisions le type de précédences (tree) considérées.

– rj , Ø→ Les dates de disponibilité des tâches sont indépendantes pour chaque tâche (rj ) ou supposées identiques (0). – pi,j → Les temps de traitement sont définis par tâche et machine, par machine, par tâche ou identiques dans tous les sens.

Les objectifs (le champ γ)

Le dernier champ correspond à l’objectif fixé pour le problème d’ordonnancement. Ces objectifs sont nombreux, et dépendent de l’environnement étudié. Dans le chapitre 2 « État de l’art », nous présentons les objectifs les plus couramment étudiés dans les types d’atelier considérés dans ce mémoire.

Optimisation logique du fonctionnement d’un atelier

D’autres définitions et classifications sont apparues dans la littérature. Brucker [27] a proposé de nouvelles classifications pour certains cas qui n’étaient pas décrits dans l’article de Graham et al. [54]. Ainsi, dans son ouvrage, l’auteur a considéré les cas où une machine peut traiter plusieurs tâches en parallèle, mais aussi le cas où des machines sont dédiées exclusivement à certains types de tâche. Également, d’autres propriétés des problèmes d’ordonnancement sont comprises :

des différentes types de précédences, la production par lots, les systèmes réentrants, et les différences entre un «Flowshop» avec et sans permutation (les tâches suivent un même ordre sur toutes les phases de production). Les définitions des fonctions objectives régulières et non régulières sont aussi comprises. A cela s’ajoute aussi le comportement des données utilisées. En fait, ces données, qui correspondent aux caractéristiques des tâches et machines, peuvent être connues à l’avance de manière déterministe, ou peuvent suivre des lois de probabilité, et générer les problèmes stochastiques.

De la même manière que pour les autres problèmes d’optimisation combinatoire, les problèmes d’ordonnancement peuvent être classés selon leurs complexités [99], [78], [50]. En fait, la théorie de la complexité fournit un cadre mathématique qui permet la classification de problèmes entre faciles et difficiles. Pour la résolution de problèmes combinatoires, ces notions apparaissent facilement en analysant les temps de résolution obtenus.