Un algoritmo de enumeración basado en el ordenamiento parcial para resolver el problema de minimización de interruptores de herramientas

An enumeration algorithm based on partial ordering to solve the minimization of tool switches problem

En el problema de minimización de cambios de herramienta, se busca una secuencia para procesar un conjunto de tareas de forma que el número de cambios de herramienta requeridos sea el menor posible. En este trabajo se propone un algoritmo para resolver este problema basado en una ordenación parcial de las tareas. Se obtiene una secuencia óptima expandiendo las secuencias parciales enumeradas. Se presentan pruebas computacionales.

1. INTRODUCCIÓN

Consideremos un entorno de producción en el que se tiene un conjunto de tareas T = {1, ..., N} que deben procesarse secuencialmente y sin interrupción en una única máquina de fabricación flexible y un conjunto de herramientas F = {1, ..., M}. Sea Tf el conjunto de tareas que requieren la herramienta f ∈ F. Cada tarea t ∈ T requiere que se coloque en la máquina un subconjunto de herramientas Ft y sólo cuando todo este subconjunto de herramientas está en la máquina es posible procesar la tarea t. Consideremos que la máquina es capaz de albergar como máximo C herramientas a la vez, donde C > maxt{|Ft|}. Supongamos que la capacidad de almacenamiento de herramientas C de la máquina es menor que el número total de herramientas necesarias para procesar todas las tareas. De lo contrario, el problema es trivial porque todas las herramientas se pueden cargar en la máquina y todas las tareas se pueden procesar sin necesidad de cambios de herramienta. Si la capacidad es inferior, será necesario cambiar las herramientas. Un cambio de herramienta consiste en retirar una herramienta de la máquina y añadir otra en su lugar. El orden de las herramientas en la máquina es irrelevante. El Problema de Minimización de Cambios de Herramienta (MTSP) consiste en determinar una secuencia de tareas de procesamiento para minimizar el número de cambios de herramienta necesarios.

Belady (1966), McGeoch y Sleator (1991) y Privault y Finke (2000) describen aplicaciones del MTSP relativas a la gestión de la memoria en sistemas informáticos. Este problema se produce cuando es necesario transferir páginas (herramientas) de una memoria secundaria a la memoria principal (compartimento de herramientas de la máquina) para realizar algunas tareas. Blazewicz y Finke (1994), Crama (1997), Balakrishnan y Chakravarty (2001), VanHop (2005) y Crama et al. (2007) presentan variaciones y extensiones del MTSP. Oerlemans (1992) y Crama et al. (1994) presentan una prueba formal de que MTSP es NP-difícil para C > 2 (GAREY; JOHNSON, 1979).