Novos algoritmos para o problema de sequenciamento em M?quinas Paralelas n?o relacionadas com tempos de prepara??o dependentes da sequ?ncia.

Programa de P?s-Gradua??o em Ci?ncia da Computa??o. Departamento de Ci?ncia da Computa??o, Instituto de Ci?ncias Exatas e Biol?gicas, Universidade Federal de Ouro Preto.Este trabalho trata o Problema de Sequenciamento em M?quinas Paralelas N?o- Relacionadas com Tempos de Prepara??o Dependentes da Sequ?ncia (UPMSPST, do ingl?s Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolv?-lo foram desenvolvidos tr?s algoritmos heur?sticos e um algoritmo h?brido. O primeiro algoritmo heur?stico, denominado HIVP, tem uma solu??o inicial gerada por um procedimento construtivo parcialmente guloso baseado no m?todo Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solu??o e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como m?todo de busca local. Al?m disso, periodicamente a busca ? intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heur?stico, denominado GIAP, a solu??o inicial ? criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solu??o ? refinada por um procedimento ILS que utiliza como m?todo de busca local o procedimento Adaptive Local Search { ALS. A busca _e tamb?m intensificada e diversificada por meio de um procedimento PR. O terceiro e ?ltimo algoritmo heur?stico, denominado AIRP, tem sua solu??o inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solu??o ? refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma an?loga aos algoritmos anteriores, a busca tamb?m passa por uma intensifica??o ao e diversifica??o periodicamente por meio de um procedimento PR. O algoritmo h?brido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heur?stico AIRP, diferindo deste por acrescentar um m?dulo de programa??o linear inteira mista. Para a aplica??o desse m?dulo s?o selecionados um par de m?quinas e subconjuntos de tarefas nessas m?quinas. Esses subconjuntos s?o combinados e passam por uma busca local que consiste em acionar um resolvedor de programa??o matem?tica aplicado a melhor das formula??es de programa??o matem?tica dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi poss?vel concluir que o AIRP obteve os melhores resultados dentre os algoritmos heur?sticos propostos, conseguindo superar v?rios outros algoritmos da literatura. Tamb?m foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o m?dulo de programa??o matem?tica, esses experimentos utilizaram um tempo maior de execu??o. Observou-se, no entanto, que a adi??o do m?dulo de programa??o matem?tica n?o melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes tamb?m mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores solu??es.This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times { UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time { ASPT rule. This solution is then refined by the Iterated Local Search { ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking { PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search { ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these experiments utilized a higher runtime. It was observed, however, that the addition of the mathematical programming module does not improved the performance of the AIRMP algorithm in the tested time and in the used structure of subsets of jobs. These tests also showed that increasing the processing time of the AIRP, the algorithm is able to find better solutions