MIP–Based neighborhood search for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times
Revista de Administração da Universidade Federal de Santa Maria - ReA/UFSM
MIP–Based neighborhood search for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times
Autor Correspondente: F. M. Muller | [email protected]
Palavras-chave: vizinhança MIP, metaheurísticas híbridas, programação de máquinas paralelas não relacionadas, makespan.
Resumos Cadastrados
Resumo Português:
Neste trabalho é estudado o problema de programação de tarefas em máquinas paralelas com tempo de preparação dependente da sequência e da máquina. Como objetivo é considerado a minimização da duração total da programação, usualmente referido como makespan. É proposta uma nova heuristica MIP que combina movimentos atômicos, tais como inserção, ejeção e fecho, para gerar sequências destes movimentos que minimizem o makespan. Esta heurística utiliza um resolvedor comercial para realizar a busca na vizinhança em uma estrutura de algoritmo de múltiplos inícios. A abordagem apresenta um bom desempenho computacional considerando dois conjuntos de instâncias testes previamente publicados na literatura científica.
Resumo Inglês:
In this paper we study the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. We consider the objective of minimizing the maximum completion time of the latest job, usually referred to as makespan. We propose a new MIP-based heuristic combining atomic moves such as insertion, ejection and closure, in order to generate sequences of such atomic moves minimizing the makespan. This heuristic employs a commercial solver to search the neighborhood in a multi-start algorithm. Our approach performed well in computational experiments targeting two sets of benchmark instances previously used in the literature.
