Modèle avec chemins et séquence fixée

Modèle avec chemins et séquence fixée

Afin de réduire la difficulté associée à la résolution du modèle intégré, nous utilisons une stratégie qui consiste à résoudre un sous-ensemble de problèmes de planification à séquence fixée. Une première version de cette approche a été proposée dans [233, 234, 235], et nous y avons apporté des modification jusqu’à obtenir une version améliorée que nous présentons dans la section 3.3. Cette approche est basée sur la résolution d’un modèle utilisant les chemins du graphe conjonctif associé à une séquence fixée. La première modification consiste à exprimer les contraintes de capacité, non pas en fonction de la date de début des opérations, mais en fonction de la date de disponibilité, c’est-à-dire la date minimale à laquelle une opération peut démarrer. Ces dates sont définies à travers les contraintes (3.13), (3.14), (3.15) et (3.16). Les contraintes (3.13) permettent d’établir que la première opération de gamme doit démarrer à une date garantissant le respect du délai d’obtention. À travers les contraintes (3.14), la dernière opération de chaque gamme est disponible à partir de la date de début de sa période associée (période de production du produit i(o)). Les contraintes (3.15) définissent la date de disponibilité pour les opérations comme étant à la fois la première et la dernière dans la gamme de fabrication. La date de disponibilité n’étant pas considérée pour les opérations intermédiaires, les contraintes (3.16) sont utilisées pour formaliser la définition. La différence par rapport au modèle intégré précédent est que la dernière opération de chaque gamme doit démarrer et finir dans sa période associée. Dans le modèle intégré, cette opération peut démarrer à une période différente.

La fonction objectif (3.4) et les contraintes d’équilibre des stocks (3.5) du modèle à séquence fixée sont similaires à celles du modèle intégré

La différence réside dans les contraintes (3.25), qui représentent les contraintes de capacité détaillées pour une séquence y, où c représente un chemin et C(y) est l’ensemble des chemins dans le graphe, et o f c et o l c sont les première et dernière 96 CHAPITRE 3. APPROCHE POUR DES PROBLÈMES MONO-NIVEAU opérations du chemin c, respectivement. La différence entre les contraintes (3.25) et (3.3) est que les premières considèrent la capacité des périodes, tandis que les deuxièmes respectent uniquement les contraintes de précédence. Finalement, de la même manière que dans le modèle intégré, les contraintes (3.9) relient les variables de production X aux variables de setup Y , les contraintes (3.10) assurent la non-négativité des variables et les contraintes (3.11) gèrent la valeur des variables binaires de setup. Ce modèle mathématique est une généralisation du CLSP, avec des contraintes de capacité détaillées qui servent à garantir le respect des contraintes de précédence pour une séquence fixée, en utilisant les informations dérivées du graphe conjonctif. Résoudre un problème de dimensionnement de lots avec des contraintes de capacité agrégées, comme le CLSP, est N Pdifficile pour les ateliers à une seule machine [31]. Donc, utiliser des contraintes de capacité détaillées pour des problèmes multi-ressources avec partage (de type job-shop), rend le problème encore plus difficile à résoudre. Le nombre de chemins dans le graphe conjonctif peut être très important (sa croissance est en effet exponentielle), et satisfaire toutes les contraintes de capacité peut devenir impossible. Notre stratégie de résolution consiste à appliquer une heuristique Lagrangienne pour résoudre le problème de dimensionnement de lots et d’ordonnancement avec séquence fixée, intégrée dans une recherche taboue qui permet d’améliorer la séquence.

 Méthode de résolution

La plupart des problèmes de dimensionnement de lots avec contraintes de capacité sont N P-difficiles. Si l’on ajoute des contraintes du type (3.1) et (3.2), le problème devient encore plus difficile à résoudre. Par ailleurs, le problème d’ordonnancement dans un atelier de type jobshop multi-périodes est l’un des problèmes les plus difficiles à résoudre (N P-difficile au sens fort). La combinaison des variables et des contraintes des deux problèmes est donc N P-difficile. L’implémentation d’une méthode exacte permettant de trouver des solutions optimales pour des problèmes de taille raisonnable paraît impossible. En outre, dans plusieurs cas, les solveurs commerciaux sont même incapables de trouver des solutions réalisables pour des problèmes de ce type. Face à ce constat, nous proposons une approche basée sur des heuristiques et illustrée dans la Figure 3.3. Premièrement, nous résolvons le problème de dimensionnement de lots avec contraintes de capacité détaillées pour une séquence fixée, et deuxièmement nous modifions le graphe conjonctif pour déterminer une nouvelle séquence. Cette procédure est répétée durant un certain nombre d’itérations

Heuristique Lagrangienne pour la résolution du problème à séquence fixée

Pour réduire la difficulté de résolution du problème de dimensionnement de lots avec séquence fixée, nous utilisons une heuristique Lagrangienne qui a pour but de : (i) calculer un plan de production optimal pour la séquence fixée avec contraintes de capacité relâchées, et (ii) réparer les contraintes de capacité non respectées afin de construire une solution réalisable. 3.3.1.1 Relaxation Lagrangienne La stratégie consiste à relâcher les contraintes de capacité, de façon à résoudre un ensemble de problèmes mono-produit à capacité infinie, en utilisant la propriété de Wagner et Whitin [231]. Seuls les coûts de setup et de stockage ont une influence sur le choix des variables de décision. Pour chaque problème à un produit, nous combinons l’algorithme dynamique de dimensionnement de lots proposé par Wagelmans et al. [230], où chaque problème peut être résolu en un temps O(T log T), avec la technique de la relaxation Lagrangienne, en utilisant la méthode des sous-gradients ([69] ; [146]). La fonction (3.26) est la fonction objectif du problème dual, où βc correspond au multiplicateur Lagrangien associé au chemin c ∈ C(y). Cette fonction est exprimée en termes des variables de décision X et Y et des multiplicateurs Lagrangiens β.