Alberto Polidura

Project Description

The project titled Scatter Search and Path Relinking based metaheuristics to solve the Fuzzy Job Shop Scheduling Problem was the Final Year Project for my Computer Engineering BSc degree at University of Cantabria. It wouldn't have been possible without the help and support of my tutor, Professor Inés González Rodríguez of UC.

Project Details

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 different 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.