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