Quelles contraintes prendre en compte à l’étape de l’ordonnancement ?
L’ordonnancement au sens large a pour objectif d’allouer des ressources à des tâches et de définir la date de début de chaque tâche. Les 2 notions fondamentales sont donc :
- Les tâches ou événements : il s’agit d’opérations nécessitant des ressources et ayant une certaine durée
- Les ressources : machines, matières premières… ayant une disponibilité connue dans le temps
Une première typologie des problèmes d’ordonnancement découle de celle de chacune de ces 2 notions de base :
- Les ressources peuvent être renouvelables (équipements) ou consommables (matières)
- Les tâches peuvent être fractionnables ou non. On retrouve les tâches fractionnables dans les industries de processus continus ou semi-continus
A celle-ci s’ajoutent les types de contraintes propres au procédé de fabrication dont notamment :
- Les contraintes de disponibilité des ressources ou des demandes à satisfaire en fonction du temps
- Les contraintes portant sur les tâches : précédence, contraintes disjonctives (non-recouvrement)…
- Autres : temps de transit, limites sur les encours…
Enfin, le type de marché détermine la nature du processus d’ordonnancement, selon qu’il s’agisse de demandes connues à l’avance (statiques) ou qu’il faille répondre à des demandes qui arrivent en temps réel (dynamiques).
Trois familles de procédés répondent à des approches de résolution distinctes
En combinant ces différents critères de classification, on peut identifier les 3 grandes familles de procédés et les approches de résolution appropriées à chacune :
- Les procédés continus qui se caractérisent par la présence de ressources consommables et des tâches fractionnables, ainsi que des limites sur les stocks. L’approche appropriée dans ce cas est la programmation mathématique quand la taille du problème le permet, et la simulation des flux pour les cas de grande taille (approches par essais et erreurs)
- Les industries manufacturières, ateliers mécaniques… qui se caractérisent par des ressources renouvelables, des tâches non fractionnables et des contraintes portant sur le séquencement des tâches. Dans cette catégorie, on retrouve les problèmes dits de flow-shop (les produits doivent passer par une séquence fixe de machines, comme les chaînes de montage) et les job-shop (où chaque pièce doit visiter une séquence spécifique de machines). L’approche appropriée dans ces cas est la programmation par contrainte pour les cas très contraints, ou les métaheuristiques (cas moins contraints)
- Les procédés semi-continus où il existe un fonctionnement en campagnes ou lots et qui combinent des aspects des 2 familles précédentes, dont les suivants :
- Existence de ressources consommables
- Limites sur les encours
- Tâches fractionnables mais sous pénalité, dans le sens ou la taille des lots est une variable, mais où les coûts de changement de campagne nécessitent de trouver un compromis entre la taille des lots et la quantité de stocks immobilisé
- Les pénalités de changement de série dépendent de la nature et de l’ordre des lots
Ces problèmes relèvent des approches de recherche locale et des métaheuristiques : recuit simulé, algorithmes évolutionnaires, souvent combinés avec des règles de priorité propres à chaque industrie.
