In the Job Sequencing and Tool Switching Problem (SSP) a number of part types, each requiring a set of tools, are to be manufactured on a single flexible machine with a capacitated tool magazine. The SSP aims at determining the processing sequence as well as the tools present in the magazine for each part, in order to minimize the total number of tools switches. In this paper, we cast the SSP as a nonlinear least cost Hamiltonian cycle problem. A branch-and-cut algorithm is proposed and compared to previous exact procedures. Computational results indicate that the algorithm is able to solve much larger instances than those reported in the literature.
Solving the job sequencing and tool switching problem as a nonlinear least cost Hamiltonian cycle problem
GHIANI, GIANPAOLO;GRIECO, Antonio Domenico;GUERRIERO, Emanuela
2010-01-01
Abstract
In the Job Sequencing and Tool Switching Problem (SSP) a number of part types, each requiring a set of tools, are to be manufactured on a single flexible machine with a capacitated tool magazine. The SSP aims at determining the processing sequence as well as the tools present in the magazine for each part, in order to minimize the total number of tools switches. In this paper, we cast the SSP as a nonlinear least cost Hamiltonian cycle problem. A branch-and-cut algorithm is proposed and compared to previous exact procedures. Computational results indicate that the algorithm is able to solve much larger instances than those reported in the literature.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
