In this article, a hybrid Lagrangean metaheuristic is proposed for single machine scheduling problems with sequence-dependent setup times and due dates. The objective function considered throughout this work, is to minimize the total tardiness. Related works and taxonomies for hybrid metaheuristics are analyzed, through a thorough historical overview. The proposed hybrid Lagrangean metaheuristic is a Lagrangean relaxation integrated with a metaheuristic. The algorithm uses the information of the Lagrangean multipliers to construct and perturb feasible solutions. The algorithm performance is compared with previous works and we find that the upper bounds obtained were particularly good, proving optimality for several instances and tight gaps for others. Furthermore, to the best of our knowledge, the proposed methodology presents generally better results than previous related works.
Citation
Departamento de Engenharia de Produção, Universidade Federal de Minas Gerais, Av. Presidente Antônio Carlos, 6627, Cep 30161-010, Belo Horizonte, Minas Gerais, Brazil. Submitted for C&OR on 8/8/2014.