当前位置: 首页 >> 新闻动态 >> 新闻 >> 正文

实验室博士生徐宏云的论文被Journal of Scheduling录用

发布者: [发表时间]:2013-10-03 [来源]: [浏览次数]:

智慧计算与优化实验室博士生徐宏云,导师吕志鹏以及香港理工大学的郑大昭教授合作撰写的论文“Iterated Local Search for Single-machine Scheduling with Sequence-dependent Setup Times to Minimize Total Weighted Tardiness”日前已被Journal of Scheduling期刊正式录用,Journal of Scheduling是国际上调度领域内的权威级期刊。该论文采用迭代局部搜索算法来解决带准备时间的单机调度问题,文中提出了一种新的基于“块移动”的邻域结构,并提出了一种高效的加速算法用来评估该邻域结构,算法的测试结果跟其它一些优秀的启发式算法和精确算法比较,都具有一定程度的优势。

附:论文摘要

Abstract We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighbourhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighbourhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time and it outperforms the previous best known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighbourhood and the fast incremental evaluation technique.