Petri Nets based Deadlock-free Scheduling for Flexible Manufacturing Systems

An efficient search algorithm for scheduling flexible manufacturing systems modeled by timed Petri nets is presented in this paper. The algorithm is based on the application of the A* algorithm and combines the structure theory of Petri nets. The proposed heuristic function can guarantee the optimal deadlock-free schedule can be obtained by applying the algorithm. Structural analysis of Petri nets is used as an truncation technique for the proposed algorithm. The efficiency of the proposed method is illustrated using an example of FMS scheduling problem