A genetic algorithm and variable neighborhood search for the unrelated parallel machine scheduling problem with sequence dependent setup time

Everton Tozzo, Syntia Lemos Cotrim, Edwin Vladimir Cardoza Galdamez, Gislaine Camila Lapasini Leal


This paper presents the evaluation of two metaheuristics to solve the Unrelated Parallel Machine Scheduling Problem with Sequence Machine Dependent Setup Time. Considering such a problem, there is no relation between the time to process each task and the machine; and this is why the machines are referred to as unrelated. Furthermore, the setup time between the executions of two tasks depends on both, the task sequence and its associated machine. A metaheuristic genetic algorithm and a variable neighborhood search were used in order to solve the problem due to the difference among their characteristics. The maximal time for the schedule to be completed, also called makespan, was the performance measure used to evaluate the solutions. The results obtained by both metaheuristics were directly compared according to their performance to try to reduce this makespan. The results showed that the variable neighborhood algorithm search outperformed the genetic algorithm regarding the solutions quality and execution time.



scheduling problem; machine scheduling; metaheuristic.

Texto completo:

PDF (English) (baixado

DOI: http://dx.doi.org/10.4025/actascitechnol.v40i1.36607

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

ISSN 1806-2563 (impresso) e ISSN 1807-8664 (on-line) e-mail: actatech@uem.br


Resultado de imagem para CC BY