Resumen

Este artículo aborda el problema de la secuenciación de tareas en un entorno de una sola máquina con posibilidad de externalización. El problema presentado trata de minimizar la suma ponderada de los costes totales de externalización y la suma de los tiempos de ejecución de cada tarea y se define en la literatura como 1 / Presupuesto / (1 δ) Σ Cj + δ. OC. Para resolver este problema se propone un método en dos etapas: en la primera se propone secuenciar las tareas utilizando la regla SPT (Shortest Processing Time) para reducir el espacio de búsqueda en el grafo generado, mientras que en la segunda etapa se propone un algoritmo basado en ACO (Ant Colony Optimisation). El algoritmo aquí propuesto incorpora al ACO cuatro características específicas del problema estudiado, a saber: i) una representación del grafo para problemas de programación que implican subcontratación, obtenida mediante la aplicación de la primera etapa del método; ii) una regla de preselección, que garantiza la viabilidad de la solución; iii) una nueva regla de visibilidad específica para el problema; y iv) una estrategia de búsqueda local. Los resultados obtenidos en este trabajo muestran que el algoritmo basado en ACO desarrollado es más eficiente que el algoritmo de Lee y Sung (2008a), que era el único trabajo encontrado en la literatura que trataba el problema analizado. Además, la búsqueda local propuesta mejoró los resultados para problemas medianos y grandes.

1. INTRODUCCIÓN

Desde el trabajo publicado por Colorni, Dorigo y Maniezzo (1991), muchos investigadores han utilizado las llamadas "hormigas artificiales" para resolver problemas combinatorios complejos. Esta clase de algoritmos, denominada ACO (Ant Colony Optimisation), se basa en el comportamiento de las hormigas reales y ya ha mostrado buenos resultados en problemas combinatorios descritos en la literatura como NP-duros. Algunos ejemplos son Dorigo, Maniezzo y Colorni, (1996) y Gambardella y Dorigo (1996), que proponen un algoritmo para resolver el problema del viajante de comercio simétrico y asimétrico, Gambardella y Dorigo (2000), que tratan el problema del orden secuencial, Bullnheimer, Hartl y Strauss (1997), que trabajan con el problema del encaminamiento de vehículos con capacidad limitada, y Bauer et al. (2000), que tratan problemas de programación. Se pueden encontrar más problemas e investigaciones sobre ACO en Dorigo y Stutzle (2004), que presentan más de 60 publicaciones sobre el tema.

También hay varios estudios que utilizan ACO para resolver una amplia variedad de problemas de programación. Los ejemplos incluyen investigaciones centradas en la programación de una sola máquina (ZAPFEL; BOGL, 2008; HOLTHAUS; RAJENDRAN, 2005; MERKLE; MIDDENDORF, 2000); máquinas paralelas (ARNAOUT; MUSA; RABADI, 2008); flow-shop (AHMADIZAR; BARZINPOUR; ARKAT, 2007; MARIMUTHU; PONNAMBALAM; JAWAHAR, 2009) y job-shop (ZHOU; LEE; NEE, 2008; ZHUO; ZHANG; CHEN, 2007).

• Materias:Programación de la producción Optimización de procesos Simulación secuencial
• Subjects:Production scheduling Process optimization Sequential simulation
• Palabras claves:Programación; Optimización basada en colonias de hormigas; Subcontratación
• Keywords:Scheduling; Ant colony optimization; Outsourcing