Deadlock-Free Scheduling Method for FMSs Using Beam Search

In this paper, we present a filtered beam search method to solve deadlock-free scheduling problems in FMSs, which are proven to be NP-hard. Some methods in literatures have been proposed to solve those problems, however, they are very time-consuming and not applicable in large scale systems. The algorithm presented in this paper is based on a fast and approximate heuristic method in searching decision trees, so it is very competitive in computation expense. With two evaluation functions, the proposed algorithm provides a trade-off between the solution quality and search effort. Siphon technology is used to prevent deadlock and reduce the complexity of the scheduling problem by searching only the necessary portion of the search graph