A hybrid Lagrangean metaheuristic for single machine scheduling problem with sequence-dependent setup times and due dates
Thiago Henrique Nogueira (thnogueira.ufvgmail.com)
Abstract: 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.
Keywords: Hybrid Metaheuristic, Metaheuristic, Single Machine Scheduling Problem, Sequence-dependent Setup Times, Lagrangean Relaxation
Category 1: Applications -- OR and Management Sciences (Scheduling )
Category 2: Combinatorial Optimization (Meta Heuristics )
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.
Entry Submitted: 08/08/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|