A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times

Abstract

In this paper, we study Open Shop Scheduling Problems (OSSPs) that involve (1) travel times between machines and/or (2) sequence-dependent setup times. First, we propose a new decoding scheme on the well-known permutation list representation and study its properties. Second, we describe an effective Variable Neighborhood Search (VNS) algorithm which incorporates the proposed decoding scheme and that uses a self-tuning routine to set its most important parameter. Last, we tested the performance of the algorithm on several sets of instances: the first two sets consisted of classical instances of OSSPs extended with randomly generated both travel times and anticipatory sequence-dependent setup times. The third set of problems were instances of OSSPs with travel times previously presented in the literature. The last set of problems consisted of classical OSSP of the literature and was used mainly to corroborate our results. The solutions of the proposed VNS were compared with the solutions of constraint programming (CP) algorithms, previous solutions and with the optimal solutions where available. The results revealed three important things: First, the decoding strategy was the factor that had the greatest influence on the performance of the VNS algorithm. Second, the proposed self-tuning VNS algorithm was robust and very easy to adapt to a variety of OSSPs. Third, the algorithm exhibited consistent and very competitive performance in terms of computer time and solution quality in all sets of instances.

En este artículo, estudiamos problemas de programación de taller abierto (OSSP) que implican (1) tiempos de viaje entre máquinas y/o (2) tiempos de preparación dependientes de la secuencia. En primer lugar, proponemos un nuevo esquema de decodificación sobre la conocida representación de lista de permutaciones y estudiamos sus propiedades. En segundo lugar, describimos un algoritmo eficaz de búsqueda de vecindario variable (VNS) que incorpora el esquema de decodificación propuesto y que utiliza una rutina de autoajuste para establecer su parámetro más importante. Por último, probamos el rendimiento del algoritmo en varios conjuntos de instancias: los dos primeros conjuntos consistían en instancias clásicas de OSSP ampliadas con tiempos de viaje generados aleatoriamente y tiempos de configuración anticipados dependientes de la secuencia. El tercer conjunto de problemas fueron instancias de OSSP con tiempos de viaje previamente presentados en la literatura. El último conjunto de problemas consistió en OSSP clásico de la literatura y se utilizó principalmente para corroborar nuestros resultados. Las soluciones del VNS propuesto se compararon con las soluciones de algoritmos de programación de restricciones (CP), soluciones anteriores y con las soluciones óptimas donde estaban disponibles. Los resultados revelaron tres cosas importantes: primero, la estrategia de decodificación fue el factor que tuvo la mayor influencia en el rendimiento del algoritmo VNS. En segundo lugar, el algoritmo VNS autoajustable propuesto era robusto y muy fácil de adaptar a una variedad de OSSP. En tercer lugar, el algoritmo exhibió un desempeño consistente y muy competitivo en términos de tiempo de computadora y calidad de la solución en todos los conjuntos de instancias.