Deconstructing Nowicki and Smutnicki's i-TSAB tabu search algorithm for the job-shop scheduling problem
Deconstructing Nowicki and Smutnicki's i-TSAB tabu search algorithm for the job-shop scheduling problem
复制标题
DOI：
10.1016/j.cor.2005.07.016
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
J. Watson;A. Howe;L. D. Whitley
中科院分区：
文献类型：
--
作者：
J. Watson;A. Howe;L. D. Whitley
在过去的十五年中，机器调度的禁忌搜索算法已经获得了近乎神话般的声誉，因为它在一系列学术和现实问题上始终等同于或建立了最先进的性能水平。然而，尽管取得了这些成功，很少有研究致力于发展为什么禁忌搜索在这类问题上如此有效的理解。在本文中，我们报告的结果，在这个方向上取得了重大进展。我们考虑Nowicki和Smutnicki的i-TSAB禁忌搜索算法，它代表了当前最先进的经典作业车间调度问题的最大完工时间最小化形式。通过一系列受控实验，我们确定了i-TSAB的那些组件，使其能够达到最先进的性能水平。在这样做的过程中，我们暴露了一些误解的行为和/或禁忌搜索和其他本地搜索元算法的车间作业问题的好处。我们的研究结果还有助于通过确定最有可能进一步提高性能的具体方向来关注未来的研究。
Over the last decade and a half, tabu search algorithms for machine scheduling have gained a near-mythical reputation by consistently equaling or establishing state-of-the-art performance levels on a range of academic and real-world problems. Yet, despite these successes, remarkably little research has been devoted to developing an understanding of why tabu search is so effective on this problem class. In this paper, we report results that provide significant progress in this direction. We consider Nowicki and Smutnicki's i-TSAB tabu search algorithm, which represents the current state-of-the-art for the makespan-minimization form of the classical job-shop scheduling problem. Via a series of controlled experiments, we identify those components of i-TSAB that enable it to achieve state-of-the-art performance levels. In doing so, we expose a number of misconceptions regarding the behavior and/or benefits of tabu search and other local search metaheuristics for the job-shop problem. Our results also serve to focus future research, by identifying those specific directions that are most likely to yield further improvements in performance.