Análise de estruturas de vizinhança: um estudo de caso sobre o problema de programação de tarefas em ambiente Job Shop

Abstract

Uma das características mais importantes de uma busca local é a sua estrutura de vizinhança. Amplamente utilizada em problemas de otimização, uma vizinhança é um mapeamento que atribui para cada solução s ∈ S um conjunto de soluções vizinhas N(s). Procedimentos de busca local usam o conceito de vizinhanças para mover-se de uma solução s para uma outra solução vizinha s’ ∈ N(s). Nesta dissertação, realizamos uma análise experimental do desempenho de seis estruturas de vizinhança para o Problema de Programação de Tarefas em ambiente Job Shop. O objetivo desse problema consiste em planejar a execução de tarefas considerando um conjunto limitado de recursos e respeitando as restrições estabelecidas. Para uma análise efetiva das estruturas de vizinhança, foram utilizados quatro critérios de avaliação: Eficiência, Convergência, Força e Aprimoramento. Neste trabalho, vizinhanças foram apresentadas a partir da utilização de conceitos de teoria dos grafos. Os procedimentos de busca local aplicados foram desenvolvidos com base nas heurísticas Hill Climbing e Variable Neighborhood Descent, a última com o objetivo de estudar as interferências entre buscas realizando combinações de vizinhanças. A partir da análise dos resultados obtidos, foi possível correlacionar desempenhos das vizinhanças e obter informações úteis para entender por que certas vizinhanças apresentam desempenhos melhores que outras nos critérios de avaliação definidos.

One of the most crucial characteristics of a local search is its neighbourhood. Widely used in optimization problems, a neighbourhood is a mapping that assigns to each schedule s ∈ S, a set of schedules N(s) that are neighbours of s. Local search procedures use the concept of a neighbourhood to move from one schedule s to a neighbour schedule s’ ∈ N(s). In this project, we performed an experimental performance analysis of six neighbourhood structures for the Job Shop Scheduling Problem. The objective of this problem is to plan the execution of jobs considering a limited set of resources and respecting the established restrictions. For effective analysis of the neighbourhood structures, four evaluation criteria were considered: Efficiency, Convergence, Strength and Improvement. In this work, neighbourhoods were created from graph theory concepts. The local search procedures were developed based on Hill Climbing and Variable Neighborhood Descent methods, the latter to study the interferences in local search procedures by performing combinations of neighbourhoods. From the analysis of the results obtained, it was possible to demonstrate correlations of performance between the neighbourhoods and obtain useful information to understand why some neighbourhoods perform better than others in the defined evaluation criteria.