The job sequencing and tool switching problem with sequence-dependent setup time

Abstract The job sequencing and tool switching (SSP) is a well-known combinatorial optimization problem that aims to minimize the number of tool switches. The problem mainly arises in a flexible manufacturing system, in which machines can be configured with various tools to process different jobs and tool switches will correspond to a reduction of productivity. While the general studies assume uniform setup time for tool switching, applications on the industries indicate that the setup time of a tool might depend on the previously installed tool of the same slot. Therefore, this article proposes two integer linear programming models for the sequence-dependent SSP, namely the five-index formulation and the multicommodity flow formulation. Experimental tests are executed to compare the sequence-dependent SSP with the uniform SSP and the results show the effectiveness of multicommodity flow formulation. Finally, several managerial discussions are derived from the results.