Optimization Online


A hybrid Lagrangean metaheuristic for single machine scheduling problem with sequence-dependent setup times and due dates

Thiago Henrique Nogueira (thnogueira.ufv***at***gmail.com)
Gabriel Pinheiro Alves Santos (gabriel.santos***at***ufv.br)
Carlos Roberto Venâncio de Carvalho (crvcarvalho***at***gmail.com)
Martín Gómez Ravetti (gravetti.martin***at***gmail.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.

Download: [PDF]

Entry Submitted: 08/08/2014
Entry Accepted: 08/08/2014
Entry Last Modified: 08/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society