A Heuristic for Minimizing the Number of Tool Switches on a Flexible Machine

Publisher Website
Google Scholar
Abstract
This paper addresses the problem of scheduling N jobs on a single machine equipped with an automatic tool interchange mechanism. We consider the case where the total number of tools required to process all N jobs is greater than the capacity of the tool magazine, and where processing times and switching times are independent. The underlying problem is to find the job sequence and tool replacement policy that minimizes the total number of switches. This is equivalent to minimizing the makespan. Two industrial applications of the model are cited. The problem is formulated as a nonlinear integer program and solved with a dual-based relaxation heuristic designed to quickly find good local solutions. An example is given to highlight the computations and a series of test cases is examined to gauge the performance of the proposed methodology. The results demonstrate that in almost all cases global optimality is obtained, but in notably less time than current techniques admit. This points up the practicality of using the algorithm for real time control. Extensions to the L-machine scheduling problem are also discussed.

This publication has 19 references indexed in Scilit: