SPECIAL ISSUE: Learning Under Uncertain Environment and Its Application to Pattern Recognition; Edited by X. Wang, Y. Tang and D. YeunNo Access
A SIMULATED ANNEALING BASED BEAM SEARCH ALGORITHM FOR THE FLOW-SHOP SCHEDULING PROBLEM
https://doi.org/10.1142/S0218001408006077Cited by:2 (Source: Crossref)
Abstract
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 scheduling problem (FSP) 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 the search tree can be greatly reduced. Based on a simple simulated annealing algorithm, partial schedules are globally evaluated. Numerical experiments show that good solutions of large-scale FSPs could be found with the proposed algorithm in a short time.
Keywords:
