An almost linear time complexity algorithm for the Tool Loading Problem
share
As shown by Tang, Denardo [9] the job Sequencing and tool Switching Problem (SSP) can be decomposed into the following two problems. Firstly, the Tool Loading Problem (TLP) - for a given sequence of jobs, find an optimal sequence of magazine states that minimizes the total number of tool switches. Secondly, the Job Sequencing Problem (JeSP) - find a sequence of jobs minimizing the total number of tool switches. Published in 1988, the well known Keep Tool Needed Soonest (KTNS) algorithm for solving the TLP has time complexity O(mn). Here m is the total number of tools necessary to complete all n sequenced jobs on a single machine. A tool switch is needed since the tools required to complete all jobs cannot fit in the magazine, whose capacity C < m. We hereby propose a new Greedy Pipe Construction Algorithm (GPCA) with time complexity O(Cn). Our new algorithm outperforms KTNS algorithm on large-scale datasets by at least an order of magnitude in terms of CPU times.
READ FULL TEXT