Approche intégrée pour des problèmes à un niveau

Approche intégrée pour des problèmes à un niveau

Ce chapitre présente une méthode d’optimisation permettant de résoudre de manière inté- grée le problème de planification et d’ordonnancement de la production mono-niveau, dans des systèmes de production complexes de type job-shop 1. L’approche permet d’obtenir des solutions réalisables proches de l’optimum pour différentes tailles de problèmes, avec des temps de calcul raisonnables.Comme montré dans le chapitre précédent, peu de travaux dans la littérature ont étudié l’intégration des décisions de planification et d’ordonnancement de la production dans des sys- tèmes complexes, afin de déterminer au niveau tactique des plans de production réalisables au niveau opérationnel, i.e. des plans qui respectent les contraintes de capacité détaillées. Parmi les approches présentées, nous nous intéressons à celle de Wolosewicz et al. [233, 234, 235], qui est une version évoluée de plusieurs approches et qui, contrairement aux autres travaux, considère le problème d’ordonnancement sur tout l’horizon de planification, permettant ainsi d’utiliser efficacement la capacité de production.

L’approche de Wolosewicz et al., bien qu’elle offre une bonne performance par rapport au solveur commercial IBM ILOG CPLEX, peut être améliorée en termes de qualité de la solution et de temps de calcul, en modifiant plusieurs parties de l’algorithme, comme nous allons le constater dans ce chapitre. En fait, nous proposons, dans ce qui suit, une nouvelle approche basée sur le principe de combinaison d’une heuristique Lagrangienne et d’une recherche taboue pour résoudre le problème intégré dans des systèmes complexes multi-produits, multi-opérations et multi-ressources avec partage de ressources et avec une politique d’ordonnancement sur tout l’horizon de planification.Nous commençons ce chapitre par une description du problème auquel nous nous intéressons, ainsi que sa modélisation, dans la Section 3.2. Ensuite, dans la Section 3.3, nous expliquons les principes de la méthode de résolution. Dans la Section 3.4, nous décrivons les différentes améliorations qui ont été apportées à la méthode de Wolosewicz et al., ainsi que les différentes analyses réalisées. Puis, dans la Section 3.5, nous comparons les résultats obtenus avec ceux de l’approche de Wolosewicz et al. et ceux du solveur IBM ILOG CPLEX. Enfin, nous concluons dans la Section 3.6 sur la pertinence de cette approche.

Description du problème

Le problème d’ordonnancement est modélisé à travers un graphe disjonctif, où les nœuds cor- respondent aux opérations des jobs et les arcs représentent les contraintes entres les opérations. Les arcs reliant les opérations des gammes de produit ont toujours la même orientation (arcs conjonctifs) ; tandis que l’orientation des arcs reliant les opérations traitées sur la même res- source doit être définie (arcs disjonctifs). Le problème d’ordonnancement consiste donc à trouver la meilleure orientation pour tous les arcs disjonctifs, i.e. déterminer un graphe conjonctif sans créer des circuits. La Figure 3.1 présente un exemple de graphe disjonctif, ainsi qu’un graphe conjonctif possible pour ce graphe disjonctif.Nous nous intéressons à la résolution du problème intégré dans des systèmes de type job- shop. Nous voulons planifier la production de N produits sur T périodes à capacité finie, en utilisant M machines, tout en ordonnançant O opérations qui composent les étapes de production (gamme) des différents ordres de fabrication (jobs). Le but est de satisfaire les demandes des différents clients dans les délais (la rupture de stock n’est pas autorisée) au moindre coût, incluant la somme des coûts de production, de stockage et de setup (ou lancement de la production). Le traitement d’une opération ne peut pas être arrêté avant que celle-ci ne soit terminée (la préemption n’est pas autorisée), et une machine ne peut traiter qu’une opération à la fois. Des délais d’obtention sont définis pour chaque produit. La demande est dynamique et connue à l’avance. La capacité de production du système est limitée, et la capacité de stockage est considérée infinie. Les durées unitaires opératoires et de setup des opérations sont connues à l’avance. Les coûts et les temps de setup sont indépendants de la séquence. Les notations utilisées pour définir les données considérées dans ce problème sont les suivantes :