Exact algorithms for the job sequencing and tool switching problem

Abstract

The job Sequencing and tool Switching Problem (SSP) involves optimally sequencing jobs and assigning tools to a capacitated magazine in order to minimize the number of tool switches. This article analyzes two integer linear programming formulations for the SSP. A branch-and-cut algorithm and a branch-and-bound algorithm are proposed and compared. Computational results indicate that instances involving up to 25 jobs can be solved optimally using the branch-and-bound approach.

Acknowledgements

This research was partly supported by the Canada Research Chair in Distribution Management, by the Canadian Natural Sciences and Engineering Research Council under grant OGP00039682, by the Ministerio de Ciencia y Tecnología, Spain, and by the Nord-Pas-de-Calais region, France. This support is gratefully acknowledged. Thanks are also due to Éric Duchenne for his help with programming, to the reviewers for their valuable comments, and to Jacek Blazewicz for pointing out some useful references.