Un nuevo enfoque de descomposición de programación de restricciones para el problema de programación de taller de grupo fijo de tiempo de flujo total

10 páginasThis work addresses a particular case of the group shop scheduling problem (GSSP) which will be denoted as the fixed group shop scheduling problem (FGSSP). In a FGSSP, job operations are divided into stages and each stage has a set of machines associated to it which are not shared with the other stages. All jobs go through all the stages in a specific order, where the operations of the job at each stage need to be finished before the job advances to the following stage, but operations within a stage can be performed in any order. This setting is common in companies such as leaf spring manufacturers and other automotive companies. To solve the problem, we propose a novel heuristic procedure that combines a decomposition approach with a constraint programming (CP) solver and a restart mechanism both to avoid local optima and to diversify the search. The performance of our approach was tested on instances derived from other scheduling problems that the FGSSP subsumes, considering both the cases with and without anticipatory sequence-dependent setup times. The results of the proposed algorithm are compared with off-the-shelf CP and mixed integer linear programming (MILP) methods as well as with the lower bounds derived from the study of the problem. The experiments show that the proposed heuristic algorithm outperforms the other methods, specially on large-size instances with improvements of over 10% on averageEste trabajo aborda un caso particular del problema de programación de talleres grupales (GSSP) que se denotará como el problema de programación de talleres grupales fijos (FGSSP). En un FGSSP, las operaciones de trabajo se dividen en etapas y cada etapa tiene un conjunto de máquinas asociadas que no se comparten con las otras etapas. Todos los trabajos pasan por todas las etapas en un orden específico, donde las operaciones del trabajo en cada etapa deben finalizar antes de que el trabajo avance a la etapa siguiente, pero las operaciones dentro de una etapa se pueden realizar en cualquier orden. Esta configuración es común en empresas como los fabricantes de ballestas y otras empresas automotrices. Para resolver el problema, proponemos un procedimiento heurístico novedoso que combina un enfoque de descomposición con un solucionador de programación de restricciones (CP) y un mecanismo de reinicio tanto para evitar los óptimos locales como para diversificar la búsqueda. El desempeño de nuestro enfoque fue probado en instancias derivadas de otros problemas de programación que el FGSSP subsume, considerando tanto los casos con y sin tiempos de preparación anticipados dependientes de la secuencia. Los resultados del algoritmo propuesto se comparan con métodos estándar de CP y programación lineal entera mixta (MILP), así como con los límites inferiores derivados del estudio del problema. Los experimentos muestran que el algoritmo heurístico propuesto supera a los otros métodos, especialmente en instancias de gran tamaño con mejoras de más del 10% en promedio