Optimization Online


Analysis of mixed integer programming formulations for single machine scheduling problems with sequence dependent setup times and release dates

Thiago Henrique Nogueira (thnogueira.ufv***at***gmail.com)
Carlos R. V. Carvalho (carlos***at***dep.ufmg.br)
Marti­n Gomez Ravetti (martin.ravetti***at***dep.ufmg.br)
Mauricio Cardoso de Souza (prof.mauriciodesouza***at***gmail.com)

Abstract: In this article, six different mixed integer programming (MIP) formulations are proposed and analyzed. These formulations are based on the knowledge of four different paradigms for single machine scheduling problems (SMSP) with sequence dependent setup times and release dates. Each formulation reflects a specific concept on how the variables and parameters are defined, requiring particular settings and definitions. A thorough historical overview of a variety of formulations for this family of problems is provided. All MIP formulations studied are implemented and tested, considering, as objective functions, the weighted completion time and the total weighted tardiness. For the \citeauthor{Sousa1992} based formulation, a set of constraints to improve its lower bound value is adapted and evaluated. Extensive computational experiments are performed considering a variety of instances to capture several aspects of practical situations. Based on the results, recommendations are made for the best adaptation of the MIP formulation paradigm for the considered problems.

Keywords: Mixed integer programming, Single machine scheduling, Sequence dependent setup times, Valid inequalities

Category 1: Applications -- OR and Management Sciences (Scheduling )

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 Pesquisa Operacional on 18/04/2018.

Download: [PDF]

Entry Submitted: 07/15/2014
Entry Accepted: 07/15/2014
Entry Last Modified: 04/03/2019

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