MIP–based heuristic for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times

Felipe Martins Muller, Olinto Bassi Araujo, Fernando Stefanello, Marcelo Zanetti

Abstract


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.


Full Text:

PDF


DOI: http://dx.doi.org/10.5902/1983465913305



Licença Creative Commons
Este obra está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.

  

  

Revista de Administração da UFSM. Brazilian Journal of Management

Universidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil, eISSN 1983-4659