论文标题
工具加载问题的几乎线性时间复杂性算法
An almost linear time complexity algorithm for the Tool Loading Problem
论文作者
论文摘要
如Tang所示，Denardo [9]作业测序和工具切换问题（SSP）可以分解为以下两个问题。首先，工具加载问题（TLP） - 对于给定的作业序列，找到一个最佳的杂志序列指出，该顺序将工具开关总数最小化。其次，作业测序问题（JESP） - 找到一系列作业序列最小化工具开关总数。 1988年出版的最著名的保留工具（KTNS）算法解决了TLP的时间复杂性$ O（MN）$。这里$ m $是完成单台计算机上所有$ n $测序作业所需的工具总数。需要工具开关，因为完成所有作业所需的工具不能适合其容量$ C <m $。我们在此提出了一种新的贪婪管道结构算法（GPCA），并具有时间复杂性$ O（CN）$。我们的新算法在大规模数据集上的ktns算法的表现至少在CPU时至少一个数量级。
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.
