Introducción:
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 losalgoritmos 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.
Cuello de botella
móvil
El cuello de botella móvil (CBM) o shifting bottleneck,
desarrollado por Adams, Balas y Zawack (1989), es una de las heurísticas para
programación de talleres más exitosas (Pinedo y Singer, 1999). Su idea
principal es secuenciar una a una las máquinas del taller según su grado de
criticidad. Este último es calculado de acuerdo con la secuenciación de las
máquinas que afecta la función objetivo. El algoritmo inicia con la
determinación del cuello de botella inicial y establece una secuencia de
trabajos óptima para esa máquina. Una vez se ha hecho esta operación, se
imponen nuevas restricciones que afectan la secuenciación de las máquinas
restantes. Se determina y se secuencia la nueva máquina cuello de botella entre
aquellas no secuenciadas y el proceso se repite hasta que no haya máquinas sin
secuenciar.
Heurística cuello de
botella móvil
La heurística CBM se
basa en la idea empírica de que el desempeño de un sistema depende del ritmo de
la estación con mayor utilización. Descompone el problema tipo taller en un
número m de subproblemas de una sola máquina y la secuenciación de trabajos se
hace iterativamente en el recurso más crítico. Los principales pasos de una
iteración en el algoritmo CBM son:
• Identificación y secuenciación en cada iteración de la
máquina cuello de botella. Esto es, se resuelven m–i problemas de una sola
máquina, donde i es el número de máquinas ya secuenciadas.
• En este caso, la
máquina cuello de botella es la que causa un mayor aumento en la tardanza
ponderada total.
• Reoptimización de la secuencia local para las máquinas ya
secuenciadas. Esto es resolver de nuevo los problemas de una sola máquina en
cada una de dichas máquinas para intentar una mejora en la función objetivo.
Solución.
Se suman los tiempos para cada trabajo en cada máquina. Las
sumas de los trabajos con-sisten en la cantidad total de procesado que debe
realizarse en ese trabajo. Si no ocurren esperas, el trabajo terminará en ese
tiempo. De la tabla 10-7 se observa que el trabajo 4 toma 34 minutos de procesado; así, el lapso debe ser al menos 34
minutos. De las sumas de la máquina, la 3 debe procesar al menos durante 44
minutos, por lo que 44 es una mejor cota sobre el lapso. La máquina 3 parece
ser el cuello de botella. Si ocurren tiempos ociosos en ella, el lapso
aumentará. El procedimiento comienza con la suposición de que el lapso es 44.
Con la máquina 3 como cuello de botella, se calculan las
fechas de entrega y los tiempos de liberación para el problema de una sola
máquina; los tiempos de procesado son los de la máquina 3. La ruta para el
trabajo 1 es 1-2-3-4, entonces se procesa en la máquina 3 después de las
máquinas 1 y 2. Lo más pronto que puede procesarse el trabajo 1 en la máquina 3
es p11 + p12= 6 + 8 = 14, y el tiempo de liberación para el trabajo 1 en la
máquina 3 será /j = 14.
De manera similar, si el trabajo 1 termina para el tiempo
44, su última operación (en la máquina 4) debe terminar en el tiempo 44. Co-mo
P\ A= 5 minutos, la operación anterior debe terminar para el tiempo 44 - 5 =
39, entonces Dx= 39. El trabajo 6 tiene
la ruta 3-1 -2-4, por lo que su primera operación se hace en la máquina 3, es
decir, su tiempo de liberación es cero. La fecha de entrega del trabajo 6 es la
estimación del lapso menos el tiempo de procesado de todas sus operaciones que
siguen a la máquina 3; d 6 = 44-2-4-5 = 33.
Los datos del resto de los trabajos en la máquina 3 se
encuentran en la tabla 10-9.
Algoritmos de
búsqueda local
En forma general, una heurística local es un procedimiento
que parte de una solución inicial (s0) que pertenece a un conjunto finito de
soluciones (S) y procede iterativamente a modificar esa solución s0 para encontrar
nuevas soluciones (s’). Una solución s’ se obtiene a partir de otra solución s
mediante una modificación parcial definida lo cual se denomina un movimiento.
El algoritmo se detiene cuando se cumple con un criterio de terminación que
típicamente es un número predefinido de iteraciones. Allí se recupera la mejor
solución s* ∈S. Entre las heurísticas de búsqueda local, el enfoque
de la búsqueda tabú (BT) se ha destacado por su eficiencia y calidad de sus
soluciones (Glover y Laguna, 1997). Un algoritmo de búsqueda tabú inicia con
una solución factible s0. A continuación se examina el vecindario de la
solución actual y se escoge el vecino cuya función objetivo sea la mejor. En
ocasiones —definidas por el programador— se puede escoger un vecino con el cual
se obtenga un valor peor de la solución objetivo solamente si esto contribuye a
escapar de mínimo locales. Muchos autores (Pezzella y Merelli, 2000; Nowicki y
Smutnicki, 1996) han observado que tanto la escogencia de una buena solución
inicial como el establecimiento del vecindario son los aspectos más importantes
del desempeño del algoritmo en términos de la calidad de la solución y del
tiempo computacional. Por ejemplo, en Armentano y Scrich (2000) se usaron
varias reglas de despacho como solución inicial a la heurística BT en ambientes
job shop, y se inicia la búsqueda con la solución que produjo el mejor
resultado. En este trabajo se propone una nueva heurística compuesta, basada en
la heurística CBM y el enfoque de BT.
El algoritmo híbrido
cuello de botella-búsqueda tabú
En esta sección se
describe con detalle el algoritmo propuesto. Está compuesto por dos módulos
fundamentales: en el primero se implementa la heurística CBM con el objetivo de
generar la solución inicial, en el segundo se realiza una búsqueda local basada
en la BT y en el tercero se reoptimiza localmente la secuencia de cada máquina
cuando una solución mejor es generada por la BT. La integración de los dos
módulos se muestra en la Figura 2.
Solución inicial
La solución inicial
se halló con el algoritmo del CBM para tardanza ponderada total. 4.2
Movimientos
Un vecino se genera a través de un movimiento que consiste
en la inversión de un arco disyuntivo en el camino crítico (ruta más larga) de
un bloque dado. Un bloque es un camino en la ruta crítica de arcos disyuntivos.
Elementos de memoria corta
En la presente aplicación se utilizaron los siguientes
elementos de memoria corta: vecindario, lista tabú y criterio de aspiración.
• Vecindario: se
obtuvo la ruta crítica para cada trabajo, basada en la información inicial. Con
este camino se buscar crear nuevas soluciones mediante la inversión de los
arcos que pertenecen a éste. Van Laarhoven, Aarts y Lenstra (1992) demostraron
que no se generan ciclos al invertir un arco en el camino crítico desde el nodo
inicial al nodo final; por lo tanto, invertir arcos en el camino crítico de
cualquier trabajo tampoco generará ciclos. Se destaca que solamente se pueden
invertir los arcos disyuntivos.
·
Lista tabú: sirve para almacenar el conjunto de
los arcos que se invirtieron. Su propósito es evitar que se caiga en óptimos
locales o que se formen ciclos.
Tamaño lista tabu:
En este algoritmo se implementó un tamaño de lista tabú
dinámica a partir de la idea de Taillard (1994). Ésta sugiere un tamaño de
lista tabú que depende de la naturaleza del problema, el tamaño se fija en
(n+m)/2 (cuando m y n son iguales). Para valores diferentes se propone calcular
L como una función de n y m, razón por la cual el tamaño verdadero de la lista
es aleatoriamente escogido entre una distribución uniforme entre Lmin=[,8L] y
Lmin=[1,2L] y se cambia después de cierto número de iteraciones.
Elementos de memoria larga: diversificación
Después de ejecutar la memoria corta se aplica nuevamente el
CBM utilizando las otras reglas de despacho. Se comienza con MDD (modified due
date), seguido de MODD (modified operation due date) y CR+SPT (critical
ratio+shortest processing time) y ACT con diversos factores de escalamiento.
Esto con el fin de que el algoritmo no quede atrapado en regiones planas de
soluciones y pueda recorrer otras regiones donde puede encontrarse el óptimo.
Las definiciones de las reglas de despacho definidas se muestran a
continuación.
Para definir dichas reglas de despachos se utilizará la
siguiente notación: programación de la producción en sistemas de manufactura
tipo taller... Ing. Univ. Bogotá (Colombia), 11 (2): 203-224, julio-diciembre
de 2007 215 • t: tiempo en que se toma la decisión de programar.
• l: la l-ésima operación del trabajo j.
• oj : número total de operaciones del trabajo j.
• pij: tiempo de proceso de la operación i del trabajo j.
• dj :tiempo de entrega del trabajo j.
• dlj: tiempo de entrega de la l-ésima operación del trabajo
j. Las reglas que se implementaron fueron:
• MDD. El tiempo de entrega modificado para el trabajo j es
definido como:
MODD. El tiempo de entrega de la operación modificada
CR+SPT. Esta regla selecciona la operación con menor valor
de d’lj que es la seudofecha de entrega de la l-ésima operación del trabajo j
0 comentarios :
Publicar un comentario