An advanced tabu search algorithm for the job shop problem
An advanced tabu search algorithm for the job shop problem
复制标题
DOI：
10.1007/s10951-005-6364-5
复制
发表时间：
2005-04-01
影响因子：
2
通讯作者：
Smutnicki, C
中科院分区：
文献类型：
--
作者：
Nowicki, E;Smutnicki, C
具有最大完工时间准则的作业车间调度问题是OR理论中的一类NP难问题，具有很好的实际应用价值。这个问题经过多年的研究，也被视为先进调度算法质量的一个指标。在本文中，我们提出了一种新的近似算法，该算法基于大谷现象，利用了路径重连技术的一些元素以及邻域的新的理论性质。该算法具有史无前例的精度，可在PC机上快速实现，并经过广泛的计算机测试得到了证实。
The job shop scheduling problem with the makespan criterion is a certain NP-hard case from OR theory having excellent practical applications. This problem, having been examined for years, is also regarded as an indicator of the quality of advanced scheduling algorithms. In this paper we provide a new approximate algorithm that is based on the big valley phenomenon, and uses some elements of so-called path relinking technique as well as new theoretical properties of neighbourhoods. The proposed algorithm owns, unprecedented up to now, accuracy, obtainable in a quick time on a PC, which has been confirmed after wide computer tests.