Hybrid tabu search and beam search algorithm for job shop scheduling

被引：0

作者：

Liu, Min ^{[1
]}

Sun, Yuankai ^{[1
]}

Wu, Cheng ^{[1
]}

机构：

[1] Dept. of Automat., Tsinghua Univ., Beijing 100084, China

来源：

Qinghua Daxue Xuebao/Journal of Tsinghua University | 2002年 / 42卷 / 03期

关键词：

Estimation - Heuristic methods - Information retrieval - Iterative methods - Scheduling;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

A scheduling algorithm using search tree creation and a search policy based on the problem structure information is proposed for solving larger scale Job Shop problems by minimizing the makespan using a tabu search and a beam search. The beam search mechanism for the algorithm iteration selectively divaricates the solution space and selectively evaluation the corresponding divisions. The tabu search with a strong local search is used to evaluate each division to determine the ideal divisions suitable for the Beam Search iteration to reduce the possibility of the Beam Search cutting off good solutions. Numerical results with 40 benchmark examples of Job Shop problems minimizing the makespan show that the algorithm is efficient and that the solution quality is satisfactory so the algorithm is suitable for large scale scheduling problems.

引用

页码：424 / 426