An almost linear time complexity algorithm for the Tool Loading Problem
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 . Here is the total number of tools necessary to complete all 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 . We hereby propose a new Greedy Pipe Construction Algorithm (GPCA) with time complexity . Our new algorithm outperforms KTNS algorithm on large-scale datasets by at least an order of magnitude in terms of CPU times.