A branch and bound algorithm based on Petri nets for diverse complex cluster tool scheduling problems

This paper proposes an efficient algorithm to deal with various scheduling requirements of diverse structure cluster tools. Cluster tools not only have complex flow patterns such as parallel PMs, wafer residency time constraints and dual-arm robot, but also have different structures such as the equipment front-end module which consists of an aligner, a signal-arm robot and two load locks. Different solutions for different requirements may be impractical. To solve this problem, the Petri net models of different configured cluster tool with diverse scheduling requirements is developed first. Then, based on the Petri net models the state search tree is presented, which can efficiently determine the local optimal scheduling sequence. Through experiments, the effectiveness of the branch and bound algorithm proposed in this paper is verified.