reglas de prioridad

Comparando métodos heurísticos
para secuenciar tareas
en líneas de flujo
Mireya L. Valenzuela Luna
Departamento de Ingeniería de Sistemas, Instituto Tecnológico de Tepic
mireyalisset@yahoo.com.mx

Roger Z. Ríos Mercado
División de Posgrado en Ingeniería de Sistemas, FIME, UANL
roger@uanl.mx
RESUMEN
En este artículo se presenta un estudio computacional de una serie de métodos
paraencontrar secuencias de n tareas en un ambiente de líneas de ensamblado
o flujo (Flow Shop) de m máquinas con el objetivo de minimizar el tiempo en
el cual todas las tareas terminan de ser procesadas en el sistema. Este es un
problema derivado del área de secuenciamiento en sistemas de manufactura, de
los clasificados como difíciles de resolver. La evidencia computacional muestra
que el MétodoModificado de Palmer encuentra las mejores secuencias para el
caso general de m máquinas (m>3).
PALABRAS CLAVE:
Investigación de operaciones, sistemas de manufactura, problema de
secuenciamiento, línea de flujo, minimización de tiempo de terminación,
heurística
ABSTRACT
In this article a computational study of several methods for solving the mmachine flow shop with makespan minimization objective ispresented. Such
problem arises from manufacturing systems, and it is regarded as difficult to solve.
The empirical evidence shows that the Modified Palmer Sequence method finds
solutions of better quality for the general m-machine case (m>3).
KEYWORDS:
Operations research, manufacturing systems, scheduling problem, flow shop,
makespan minimization, heuristics
INTRODUCCIÓN
La ciencia de latoma de decisiones, mejor conocida como Investigación de
Operaciones (IO),2 nació hace más de 50 años por motivos de carácter militar, en
la segunda guerra mundial, cuando George Dantzig inventó el método simplex
para resolver problemas de optimización lineal. La IO se utiliza en todos los
niveles y en todo tipo de industrias. En éstas se busca solucionar problemas
donde se tome la mejordecisión sujeta a las restricciones tecnológicas existentes

Ingenierías, Octubre-Diciembre 2004, Vol. VII, No. 25

35

Comparando métodos heurísticos para secuenciar .../ Miryea L. Valenzuela Luna, et al

que reditúe en beneficios económicos mediante
el uso de modelos matemáticos, que sirven para
obtener una representación abstracta del problema a
resolver, y computadoras, que ayudan adesarrollar
e implementar las técnicas de solución.
Uno de los problemas que se presentan de forma
natural en algunas empresas es el de líneas de flujo
en sistemas de manufactura. El problema consiste
en cómo secuenciar las operaciones en las máquinas
de la forma más eficiente posible. Si no se hace
inteligentemente, esto puede representar un costo de
oportunidad (pérdida económica) para laempresa.
Por lo tanto, es importante encontrar el orden en el
cual se deben de procesar todas las tareas en todas
las máquinas con el fin de reducir al mínimo el
tiempo de terminación. Una excelente referencia
sobre problemas de secuenciamiento es el texto de
Pinedo.3
El objetivo de este estudio es evaluar
computacionalmente algunas de las técnicas de
solución que se usan para resolver esteproblema
de secuenciamiento en líneas de flujo e ilustrar que
hay técnicas de solución más efectivas que otras,
las cuales deben tomar en cuenta la estructura
matemática del problema.
En primera instancia se presenta una
descripción detallada del problema de líneas de
flujo y posteriormente se presentan algunas técnicas
populares de solución como es el caso de la regla
de Johnson, la cualencuentra la solución exacta en
problemas con 2 máquinas, y dos heurísticas para
problemas de m máquinas. Finalmente, se lleva a
cabo una evaluación computacional de las técnicas
estudiadas aplicándolas en la solución de varias
instancias del problema.
Al evaluar empíricamente el comportamiento de
cada heurística mediante un análisis comparativo, se
observó que una de las heurísticas (MPS)...