Groupe d’études et de recherche en analyse des décisions


Exact Algorithms for the Job Sequencing and Tool Switching Problem

, et

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.

, 16 pages