Cyclic scheduling of timed petri nets: Efficient exact algorithms and heuristic method

Abstract

This paper addresses the branch-and-price algorithm for cyclic scheduling of timed Petri nets (TPN) and the branch-and bound method with tighter lower limits. Specifically, a TPN was employed to model the scheduling problem of cluster tools, a type of semiconductor manufacturing equipment. Cluster tools are typical single wafer process equipment used in most semiconductor processes, capable of performing multiple processes within one facility. Not only are cluster tools very costly, but they also frequently carry out bottleneck processes such as etching and deposition. Solving scheduling problems for efficient operation of cluster tools is vital in the semiconductor industry. Robotic cluster tools often have periodic scheduling, repeating the same work cycle, and we utilize TPN to address this issue. Firstly, we improved the problem-solving speed compared to existing methods by using the branch-and-price algorithm and new modeling. Modeling with assignment problem further enhanced efficiency by providing a lower bound superior to the existing branch and bound method.