A NEW BEAM SEARCH ALGORITHM FOR THE LARGE-SCALE PERMUTATION FSP
Beam Search algorithm, as an adaptation of branch and bound method, is regarded as one of the effective approaches in solving combinational optimization problems. In this paper,a new beam search algorithm for the large-scale permutation flow shop problem is proposed. A new branching scheme is addressed and compared with the traditional branching scheme. With the new branching scheme, the number of partial schedules in search tree can be greatly reduced. To balance the computational effort and solution quality, partial schedules are evaluated with a new approximate function based on forecast. Numerical experiments show that good solutions of large-scale FSPs could be found in a short time with the proposed algorithm.
Beam search algorithm flow shop scheduling problem branching scheme NEH algorithm
FENG JIN SHI-JI SONG CHENG WU
Department of Automation, Tsinghua University, Beijing 100084, China
国际会议
2006 International Conference on Machine Learning and Cybernetics(IEEE第五届机器学习与控制论坛)
大连
英文
1-6
2006-08-13（万方平台首次上网日期，不代表论文的发表时间）