Metaheurísticas basadas en Scatter Search y Path Relinking para resolver el Problema del Fuzzy Job Shop Scheduling

Abstract

El presente Proyecto de Fin de Carrera tiene como objetivo aplicar una metaheurísitca conocida como Scatter Search con Path Relinking al problema de planificación de tareas conocido como Job Shop Scheduling Problem (JSP) con duraciones inciertas. Esto es, al problema de planificación clásico del Job Shop, que ha sido tratado desde diversos enfoques tradicionalmente, le añadiremos un grado de incertidumbre mediante el uso de intervalos difusos para modelar las duraciones inciertas de las tareas. Para la búsqueda de soluciones utilizaremos el mencionado esquema algorítmico de búsqueda evolutiva Scatter Search (o Búsqueda Dispersa) que orienta la exploración del espacio de búsqueda tomando como referencia un conjunto de “buenas” soluciones. Al mismo, le incorporaremos la estrategia de Path Relinking (o reenlazado de caminos) para explorar en más detalle las trayectorias que conectan estas "buenas" soluciones. Para ello, estudiaremos cómo adaptar los operadores genéricos de este esquema de búsqueda al problema bajo consideración. Como resultado del proyecto se pretende obtener una implementación de los algoritmos de búsqueda mencionados para la resolución del problema de planificación JSP. El método resultante se evaluará sobre una batería de problemas de referencia (benchmarks), con el correspondiente análisis de los resultados obtenidos. El lenguaje de programación utilizado será C++ y para la implementación se utilizará un desarrollo basado en componentes, adoptando una metodología iterativa e incremental.

The main goal of this Final Year Project is to apply a metaheuristic known as Scatter Search with Path Relinking to the Job Shop Scheduling Problem (JSP) with fuzzy durations. This means that, to the classic Job Shop Scheduling Problem commonly studied from di_erent points of view, we will add a degree of uncertainty using fuzzy intervals in order to model the uncertain duration of the tasks. In order to explore the solution space, we will use the so called evolutive Scatter Search algorithm scheme, which directs the exploration using a set of "good"solutions. This will be combined with the Path Relinking strategy to explore in more detail the paths that connect these "good"solutions. To do this, we will study how to adapt the generic operators from this search algorithm to the problem under consideration. As a result of the project we get an implementation of the search algorithms previously discussed for the resolution of the Job Shop Scheduling Problem. The resulting method will be evaluated with a benchmark of reference problems with the corresponding analysis of the obtained results. The programming language used will be C++ and we will use a component based development adopting an incremental and iterative methodology.