A new multicommodity flow model for the job sequencing and tool switching problem

Abstract

In this paper a new multicommodity flow mathematical model for the Job Sequencing and Tool Switching Problem (SSP) is presented. The proposed model has an LP relaxation lower bound equal to the number of tools minus the tool machine's capacity. Computational tests were performed comparing the new model with the models of the literature. The proposed model performed better, both in execution time and in the number of instances solved to optimality.

Keywords:

• combinatorial optimisation
• job sequencing and tool switching
• multicommodity flow
• integer programming
• linear programming relaxation

Acknowledgments

We are grateful to Dr Daniele Catanzaro for sending us the code and instances for model CGL from Catanzaro, Gouveia, and Labbé (2015), and we thank the three anonymous reviewers for valuable comments and suggestions that improved the quality of the presentation of this paper. This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001, FAPESP (grants 2018/15417-8 and 2016/01860-1), and CNPq (grants 423694/2018-9, 303736/2018-6, and 303144/2014-9).

Disclosure statement

No potential conflict of interest was reported by the author(s).

ORCID

Tiago Tiburcio da Silva  http://orcid.org/0000-0002-0700-3445

Additional information

Funding

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001, FAPESP (grants 2018/15417-8 and 2016/01860-1), and CNPq (grants 423694/2018-9, 303736/2018-6, and 303144/2014-9).