930 2970 1 PB

Programación de la producción en
sistemas de manufactura tipo taller
con el algoritmo combinado cuello de
botella móvil y búsqueda tabú
Production Programming in Manufacturing Systems
(Workshop Type) with a Combined Mobile Bottleneck
and Taboo Search Algorithm
Rodrigo Alberto Britto Agudelo**
Gonzalo Mejía Delgadillo***
Juan Pablo Caballero Villalobos****
Resumen: la programación de laproducció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 shiftingbottleneck 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
*



**

Fecha de recepción: 14 de junio de 2007. Fecha de aceptación para publicación: 10 de septiembre de
2007. Este artículose deriva del proyecto de investigación Programación de Job Shop a través del uso
de Tabu Search sobre las operaciones de ruta crítica del grafo disyuntivo, realizado en el marco de la
Maestría en Ingeniería Industrial de la Universidad de los Andes.


***

Ingeniero químico, Universidad Nacional de Colombia. Magíster en Ingeniería Industrial, Universidad
de los Andes, Colombia. Profesor,Facultad de Administración, Universidad de los Andes, Colombia.
Correo electrónico: rab@adm.uniandes.edu.co
Ingeniero mecánico, Universidad de los Andes, Colombia. Ph. D. in Industrial Engineering, Lehigh
University, Estados Unidos. Profesor asociado, Departamento de Ingeniería Industrial, Universidad
de los Andes, Colombia. Correo electrónico: gmejia@uniandes.edu.co

****

Ingeniero Industrial,Pontificia Universidad Javeriana, Colombia. Magíster en Ingeniería Industrial,
Universidad de los Andes, Colombia. Profesor asistente, Departamento de Procesos Productivos,
Pontificia Universidad Javeriana, Colombia. Correo electrónico: juan.caballero@javeriana.edu.co

Ing. Univ. Bogotá (Colombia), 11 (2): 203-224, julio-diciembre de 2007

203

rodrigo britto, gonzalo mejía, juan caballeroalgoritmos 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 enfoquesencontrados en la literatura
tanto en la calidad de las soluciones como en el tiempo computacional.
Palabras clave: sistemas flexibles de manufactura, programación de
la producción, algoritmos.
Abstract: Job Shop Scheduling has many applications in real production systems such as metal machining, printing, and textiles, among others. Commonly, in these manufacturing systems the main objective is thedelivery of the jobs on time. In this research we present a hybrid approach
that uses the Shifting Bottleneck (SB) and Tabu Search (TS) heuristics
with the purpose of minimizing the Total Weighted Tardiness. The Shifting
Bottleneck algorithm provides a feasible initial solution which is iteratively
improved by the TS method. Additionally, several improvements were performed on the classicalalgorithms SB and TS such as new criteria for the
selection of the critical machines and a number of innovative strategies
of diversification and intensification. The performance of the proposed
heuristic algorithm denominated CBBT was evaluated with 17 classical
problems found in the literature. The implemented heuristic algorithm
shows very competitive results compared with other approaches found in...