Décomposition de Benders basée sur la logique pour le problème de job-shop flexible préemptif Carla Juvin1 , Laurent Houssin1,2 , Pierre Lopez1 1 LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France {carla.juvin,pierre.lopez}@laas.fr 2 ISAE-SUPAERO, Université de Toulouse, France laurent.houssin@isae-supaero.fr Mots-clés : Job-shop flexible, préemption, décomposition de Benders, méthodes exactes. 1 Introduction On sŠintéresse au problème dŠordonnancement de production du type job-shop Ćexible préemptif (preemptive flexible job-shop scheduling problem, pFJSSP). Trois approches sont proposées pour le résoudre : la programmation linéaire en nombres entiers (MILP), la programmation par contraintes (CP), la décomposition de Benders basée sur la logique (LBBD). Dans le problème de job-shop (JSSP), on a un ensemble de jobs composés dŠopérations et chacune dŠelles doit être traitée sur une machine prédéterminée. Pour lŠobjectif de minimisation de la durée totale que lŠon considère ici, le problème est NP-difficile. Le problème du job-shop Ćexible (FJSSP) est une extension du problème de job-shop classique dans lequel plusieurs machines sont en capacité dŠexécuter une même opération, cette Ćexibilité permet alors de sŠadapter aux variations du marché. Un grand nombre de méthodes, exactes et heuristiques, ont été proposées pour résoudre le FJSSP (voir [5] pour un travail récent). Ici, nous considérons une version préemptive de ce problème. Quand elle est possible, la préemption dŠopérations en cours de traitement peut permettre de réduire les durées de fabrication. Cependant, les problèmes de job-shop préemptif ont reçu peu dŠattention [2], et, à notre connaissance, personne ne sŠest encore intéressé à la résolution du problème de job-shop Ćexible et préemptif. 2 Définition du problème Le problème étudié consiste à ordonnancer un ensemble de n jobs J = {1, . . . , n} sur un ensemble M de machines. Chaque job i est déĄni comme une séquence de ni opérations Oi = (i1 , . . . , ini ). Une opération Oi,j ∈ Oi doit être traitée par exactement une des machines parmi un ensemble Mi,j ⊆ M de machines éligibles. On note pi,j,m le temps de traitement de lŠopération Oi,j si elle est effectuée sur la machine m ∈ Mi,j . Chaque machine peut traiter au plus une opération à la fois et la préemption est autorisée : il est possible dŠinterrompre le traitement dŠune opération et de la reprendre plus tard, sur la même machine, sans pénalité. LŠobjectif est de minimiser le temps de traitement de lŠensemble des opérations (makespan). 3 Méthodes de résolution On propose trois méthodes exactes pour résoudre le problème décrit. La première méthode utilise la programmation linéaire en nombres entiers. Pour ce faire, on se base sur une formulation indexée sur le temps proposée par Bowman [1] pour le problème de job-shop préemptif. On lŠadapte pour y intégrer la notion de Ćexibilité dans le choix des machines. Le modèle intègre deux variables binaires, xi,j,m liée à lŠexécution de lŠopération Oi,j sur la machine m, et yi,j,t liée à lŠexécution de lŠopération en période t. La deuxième méthode de résolution sŠappuie sur la programmation par contraintes. La formulation que nous proposons sŠinspire de celle développée par Polo-Mejía et al. [4] pour un problème dŠordonnancement de projet, que nous avons adaptée à notre problème. Nous exploitons pour cela les fonctionnalités du solveur IBM CP Optimizer (CPO) en utilisant une décomposition dŠune opération Oi,j en pi,j,m parties de durée unitaire et Ii,j une variable intervalle entre le début et la Ąn de traitement de lŠopération. EnĄn, nous proposons de résoudre le problème avec un algorithme de décomposition de Benders basée sur la logique [3]. Pour cela, on décompose le problème en : • un problème maître dŠallocation des ressources résolu à lŠaide de la programmation linéaire en nombres entiers, intégrant les variables xi,j,m décrites plus haut et une relaxation du sous-problème ; • un sous-problème dŠordonnancement des opérations sur les machines (job-shop préemptif) résolu soit (1) à lŠaide de la programmation par contraintes, soit (2) par une version adaptée à notre problème du branch-and-bound proposé par Ebadi et Moslehi [2], et générant itérativement une coupe ajoutée au problème maître. 4 Résultats expérimentaux et conclusion Dans ce travail, nous proposons trois méthodes exactes de résolution pour le problème dŠordonnancement du job-shop Ćexible préemptif. Des expérimentations numériques menées sur 276 instances réparties en 8 jeux de données classiques du FJSSP1 en 10 mn de temps de calcul ont montré : dŠune part, quŠune décomposition du problème est bénéĄque et permet dŠobtenir de meilleurs résultats que la programmation mathématique (5% dŠinstances résolues à lŠoptimum) ou la programmation par contraintes (9%) seule ; dŠautre part, que la résolution du sousproblème par le branch-and-bound est plus rapide et permet donc de résoudre plus dŠinstances à lŠoptimum (LBBD/B&B, 36%) que par programmation par contraintes (LBBD/CP, 16%). Notre travail actuel consiste à améliorer ces méthodes, en particulier la méthode de décomposition pour résoudre les instances les plus difficiles (Dauzère-Pérès&Paulli et Chambers&Barnes, les seules pour lesquelles aucune méthode ne permet une résolution optimale dans le temps imparti), et à les étendre pour dŠautres fonctions objectif telles que la minimisation de la somme des dates de Ąn des jobs. References [1] E. H. Bowman. The schedule-sequencing problem. Operations Research, 7(5):621Ű624, 1959. [2] A. Ebadi and G. Moslehi. An optimal method for the preemptive job shop scheduling problem. Computers & Operations Research, 40:1314Ű1327, 2013. [3] J. Hooker. Planning and scheduling by logic-based Benders decomposition. Operations Research, 55:588Ű602, 2007. [4] O. Polo-Mejía, C. Artigues, P. Lopez, and V. Basini. Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility. International Journal of Production Research, 58:7149Ű7166, 2020. [5] L. Shen, S. Dauzère-Pérès, and J. S. Neufeld. Solving the Ćexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265:503Ű516, 2018. 1 http://opus.ub.hsu-hh.de/volltexte/2012/2982/ – Dernier accès octobre 2021