论文标题
改进的KTN算法用于工作测序和工具切换问题
An improved KTNS algorithm for the job sequencing and tool switching problem
论文作者
论文摘要
我们概述了一种新的Max Pipe Construction算法（MPCA），目的是减少CPU最早（KTNS）算法的CPU时间。使用KTNS算法来计算所有精确和近似算法的作业序列的目标函数值，以求解作业测序和工具切换问题（SSP）。我们的MPCA在CPU时间上至少要比KTNS算法的表现优于KTNS算法。由于解决SSP的所有精确和启发式算法都花费了大部分CPU用于应用KTNS算法，因此我们表明，与当前的Art Heuristics相比，我们的MPCA对于D的基准实例平均解决了整个SSP。
We outline a new Max Pipe Construction Algorithm (MPCA) with the purpose to reduce the CPU time for the classic Keep Tool Needed Soonest (KTNS) algorithm. The KTNS algorithm is applied to compute the objective function value for the given sequence of jobs in all exact and approximating algorithms for solving the Job Sequencing and Tool Switching Problem (SSP). Our MPCA outperforms the KTNS algorithm by at least an order of magnitude in terms of CPU times. Since all exact and heuristic algorithms for solving the SSP spend most of their CPU time on applying the KTNS algorithm we show that our MPCA solves the entire SSP on average 59 times faster for benchmark instances of D compared to current state of the art heuristics.
