Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
复制标题
DOI：
10.1287/ijoc.6.2.108
复制
发表时间：
1994-05
期刊：
影响因子：
--
通讯作者：
É. Taillard
中科院分区：
文献类型：
--
作者：
É. Taillard
将禁忌搜索的全局优化技术应用于作业车间调度问题，结果表明我们的方法比转移瓶颈算法更有效，也比最近提出的模拟退火法更有效。我们还确定了一类问题，在实践中，禁忌搜索在多项式平均时间内提供了最优解，而转移瓶颈过程的实现似乎花费了指数级的计算时间。包括为文献中的一些基准问题建立新的最佳解决方案的计算结果。最后，我们给出了一个快速的并行算法，它在很短的计算时间内就能很好地解决非常大的问题。信息计算杂志，ISSN 1091-9856，在ISSN 0899-1499下于1989至1995年间以ORSA计算杂志的形式出版。
We apply the global optimization technique called taboo search to the job shop scheduling problem and show that our method is typically more efficient than the shifting bottleneck procedure, and also more efficient than a recently proposed simulated annealing implementation. We also identify a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice, while an implementation of the shifting bottleneck procedure seems to take an exponential amount of computation time. Included are computational results that establish new best solutions for a number of benchmark problems from the literature. Finally, we give a fast parallel algorithm that provides good solutions to very large problems in a very short computation time. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.