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.
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.