Resumen

El problema de minimización del cambio de herramientas (MTSP) busca una secuencia de procesamiento de un conjunto de tareas con el fin de minimizar el número de cambios de herramientas necesarios. Este trabajo presenta una nueva heurística para el MTSP, capaz de producir buenos límites superiores para un algoritmo enumerativo. Esta heurística consta de dos fases: una fase constructiva que se basa en un grafo donde los vértices corresponden a herramientas y existe un arco k = (i, j) que conecta los vértices i y j si y sólo si las herramientas i y j son necesarias para la ejecución de alguna tarea k; y una fase de refinamiento basada en la metaheurística de Búsqueda Local Iterativa. Los resultados computacionales muestran que la heurística propuesta funciona bien para los problemas probados, contribuyendo a una reducción significativa del número de nodos generados de un algoritmo enumerativo.

1. INTRODUCCIÓN

Consideremos un entorno de producción en el que existe 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 T_f el conjunto de tareas que requieren la herramienta f ∈ F. Cada tarea t ∈ T requiere un subconjunto de herramientas F_y sólo puede procesarse cuando todo este subconjunto de herramientas está en la máquina. Consideremos que la máquina es capaz de albergar como máximo C herramientas a la vez, donde C ≥ max_t{|F_t|}. Se supone que la capacidad C de almacenamiento de herramientas de la máquina es menor que el número total de herramientas necesarias para procesar todas las tareas. Esto se debe a que, de lo contrario, el problema es trivial, ya que todas las herramientas se pueden cargar en la máquina y, a continuación, se pueden procesar todas las tareas sin necesidad de cambiar de herramienta. Si la capacidad es inferior al número total de herramientas, será necesario cambiar de herramienta. 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 se considera irrelevante en este trabajo. El Problema de Minimización de Cambios de Herramienta (MTSP) consiste en determinar una secuencia para procesar las tareas de forma que se minimice el número total de cambios de herramienta.

El MTSP está clasificado como un problema NP-duro (CRAMA et al., 1994). Este problema ha sido estudiado por varios autores, la mayoría de los cuales han propuesto heurísticas. A continuación se presenta una revisión bibliográfica de algunos de estos trabajos.

• Materias:Algoritmos metaheurísticos Programación de la producción Resolución de problemas Técnica heurística
• Subjects:Metaheuristic algorithms Production scheduling Troubleshooting Metaheuristic technique
• Palabras claves:Programación; Cambios de herramienta; Heurística; Grafo; Metaheurística
• Keywords:Scheduling; Tool switches; Heuristic; Graph; Metaheuristic