Application of a Cutting/Packing Method for Solving a Job Scheduling Problem in a Line of Machines
Nous considérons un problème particulier d'ordonnancement de production pour lequel nous définissons une méthode de résolution inspirée de celles utilisées dans le domaine de découpe. Le problème est modélisé sous forme d'un programme non linéaire en nombres entiers. Un survol des approches de résolution des problèmes de découpe nous permet de justifier du choix d'une heuristique pour le calcul de la solution de départ ainsi que d'une fonction d'évaluation spécifique en vue d'une résolution optimisée par une méthode exacte du type séparation et évaluation. Les performances sont analysées à la lumière d'un certain nombre d'expérimentations.
We consider an industrial scheduling problem for which we define a resolution method inspired from those used in the Cutting/Packing domain. The mathematical problem specification is given as an integer non-linear programming model. The overview of resolution approaches of the Cutting/Packing problems allows us to justify the choice of a heuristic for calculating the upper bound as well as a specific evaluation function to have an optimized resolution by an exact algorithm of the branch and bound type. The heuristic and the branch and bound algorithm are evaluated by experimental tests.
M.TLILI, M.MOALLA, P.BAPTISTE
ordonnancement, makespan, problèmes de découpe, séparation et évaluation.
Scheduling, Makespan, Cutting/Packing problems, Branch and Bound.
Anglais
|
