Palabras clave
programación de la producción
algoritmos
Cómo citar
Resumen
La programación de la producción en manufacturas tipo taller (job shop) encuentra muchas aplicaciones en sistemas reales de producción, como empresas metalmecánicas, de impresión, de textiles y otras más. En general, en estos sistemas de manufactura, el objetivo principal es entregar los trabajos a tiempo. En esta investigación se propone un enfoque híbrido que utiliza la heurística del cuello de botella móvil (CBM) o shifting bottleneck y la búsqueda tabú (BT) con el objetivo de minimizar la tardanza ponderada total. La heurística CBM provee una solución inicial factible que sucesivamente es mejorada por el método de BT. Adicionalmente, en este trabajo se realizaron varias mejoras sobre los algoritmos clásicos CBT y BT, como nuevos criterios para la escogencia de las máquinas críticas o cuello de botella y novedosas estrategias de diversificación e intensificación. El desempeño de la heurística propuesta (denominada CBBT) se evaluó con 17 problemas clásicos de la literatura sobre el tema. La heurística implementada muestra resultados muy competitivos comparados con otros enfoques encontrados en la literatura tanto en la calidad de las soluciones como en el tiempo computacional.
ADAMS, J.; BALAS, E. and ZAWACK, D. The Shifting Bottleneck Producer for Job Shop Scheduling. Management Science, 1988, (34): 391-401.
AKTURK, M. S. and OZDEMIR, D. A New Dominance Rule to Minimize Total Weighted Tardiness with Unequal Release Dates. European Journal of Operational Research, 2001, 135 (2): 394-412.
ANDERSON, E. J. and NYIRENDA, J. C. Two New Rules to Minimize Tardiness in a Job Shop. International Journal of Production Research, 1990, 28 (12): 2277-2292.
ARMENTANO, V. A. and SCRICH, C. R. Taboo Search for minimizing total Tardiness in a Job Shop. International Journal Production Economics, 2000, (63): 131-140.
ASANO, M. and OHTA, H. A Heuristic for Job Shop Scheduling to minimize total weighted Tardiness. Computers and Industrial Engineering, 2002, 42 (11): 137-147.
BAKER, K. R. and HAYYA, J. C. Priority Dispatching with Operation due Dates. Journal of Operations Management, 1982 (2): 167-175.
BARNES, J. W. and LAGUNA, M. A Tabu Search Experience in Production Scheduling. Annals of Operations Research, 1993 (41): 141-156.
CARLIER, J. and PISON, E. An Algorithm for Solving the Job-Shop Problem. Managing Science, 1989, 35: 164-176.
GLOVER, F. and LAGUNA, M. Tabú Search. Amsterdam: Kluwer Academic Publishers, 1997.
GRAHAM, R. L. et al. Optimization and Approximation in Deterministic Sequencing and Scheduling: A survey. Annals of Discrete Mathematics, 1979 (5): 287-326.
HOLSENBACK, J. E. et al. An Improved Heuristic for the Single-Machine, Weighted-Tardiness Problem. Omega, 1999, 27 (4): 485-495.
HOLTSCLAW, H. H. and UZSOY, R. Machine Criticidadity Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study. Journal of the Operational Research Society, 1996 (47): 666-677.
MASON, S. J., FLOWER, J. W. and CARLYLE, W. M. A Modified Shifting Bottleneck Heuristic for Minimizing Total Weighted Tardiness in Complex Job Shops. Journal of Scheduling, 2002 (5): 247-262.
NOWICKI, E. and SMUTNICKI, C. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 1996 (42): 797-813.
PEZZELLA, F. and MERELLI, E. A Taboo Search Method guided by Shifting Bottleneck for the Job Shop Scheduling Problem. European Journal of Operational Research, 2000, 120 (2): 297-310.
PINEDO M. and CHAO, X. Operations Scheduling with Applications in Manufacturing and Service. Boston: Irwin/McGraw-Hill, 1999.
PINEDO, M. and SINGER, M. A Shifting Bottleneck Heuristic for Minimizing the Total Weighted Tardiness in a Job Shop. Naval Research Logistics, 1999, 46 (1): 1-17.
PONNAMBALAM, S. G.; ARAVINDA, P. and SREENIVASA, R. P. Comparative Evaluation of Genetic Algorithms for Job-Shop Scheduling. Production Planning and Control, 2001, 12 (6): 560-574.
TAILLARD, É. Parallel Taboo Search Techniques for the Job-Shop Scheduling Problem. ORSA Journal on Computing, 1994, 16 (2): 108-117.
VAN LAARHOVEN, O.; AARTS, E. and LENSTRA, J. Job Shop Scheduling by Simulated Annealing. Operations Research, 1992 (40): 113-125.
VEPSALAINEN, V. and MORTON, T. Priority Rules for Job Shops Weighted Tardiness Cost. Management Science, 1987, 33 (8): 1035-1047.
WANG, T. Y. and WU, K. B. A Revised Simulated Annealing Algorithm for Obtaining the Minimum Total Tardiness in Job Shop Scheduling Problems. International Journal of Systems Science, 2000, 31 (4): 537-542.
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Derechos de autor 2020 Rodrigo Alberto Britto-Agudelo, Gonzalo Mejía-Delgadillo, Juan Pablo Caballero-Villalobos