Greedy Randomized Adaptive Search Procedure (GRASP) : una alternativa valiosa en la minimización de la tardanza total ponderada en una máquina

Greedy randomized adaptive search procedure (GRASP) : a valuable alternative for minimizing machine total weighted tardiness

Este artículo presenta los resultados experimentales obtenidos de secuenciar trabajos en una máquina, a fin de minimizar la tardanza total ponderada mediante un algoritmo GRASP. Los resultados se compararon con los valores óptimos o mejores valores reportados hasta el momento para cada una de las instancias de OR-Library y se encontró una excelente relación entre la calidad de los resultados (93% de las instancias se solucionaron con una desviación máxima del 1% respecto a estos valores) y el esfuerzo computacional y de implementación requerido. El algoritmo se implementó usando macros en una hoja de cálculo. La fase de postoptimización se realizó mediante una estrategia de Búsqueda Local que utilizó reglas de dominancia que, aun cuando sencillas, permitieron mejorar sustancialmente la tardanza total ponderada de las secuencias obtenidas en la fase constructiva del algoritmo.

INTRODUCCIÓN

El problema aquí considerado se conoce como el problema de secuenciación en una máquina para la tardanza total ponderada, el cual se define así: sean n trabajos J₁,J₂,…,J_n y una sola máquina que puede procesar un solo trabajo a la vez. Cada trabajo J_j tiene un tiempo de procesamiento p_j, una fecha de entrega d_jy un costo de penalización por cada unidad de tiempo de retraso w_j. Todos los trabajos están disponibles en el tiempo a efectos de ser procesados. Para cada trabajo, dada una secuencia propuesta de procesamiento _π, se obtiene un tiempo C_j(π) en el que dicha tarea será completada. La tardanza de cada trabajo se define como T_j(π) = max(0,C_j(π) – d_j) y la tardanza ponderada de la secuencia completa de trabajos f(π) está dada por f (π) = Σⁿ_j=1 w_j T_j (π). El objetivo es minimizar f(π) (Cheng et al., 2005; Bilge, Kurtulan y Kirac, 2007).

El problema se conoce como n/1/ Σ w_j T_j en la notación de Conway (Conway, Maxwell y Miller, 1967) o como 1|| Σⁿ_j=1 w_j T_j en la notación de Graham (Graham et al., 1979), y será mencionado a lo largo del artículo como el problema SMTWT (por su sigla en inglés).