Scheduling of Flexible Manufacturing Systems Based on Place-Timed Petri Nets and Basis Reachability Graphs

Scheduling is a key decision-making process to improve the performance of flexible manufacturing systems (FMSs). Place-timed Petri nets (PNs) provide a formal method for graphically modeling and analyzing such systems. By generating reachability graphs (RGs) and combining intelligent search algorithms, operation sequences from the initial state to the target state can be found for the underlying system. However, the RG grows exponentially with the system size increase, which is the main challenge of existing methods for scheduling large systems. To this end, we develop an efficient improved beam search algorithm to optimize the makespan based on a compact representation of RG called basis RG (BRG). The key idea behind the proposed method is to form a state together with the basis markings and their corresponding transition sequences, and evaluate the cost of the state based on the resource idle time. The experimental results are conducted on several benchmark systems, which show that the developed method improves the search efficiency while ensuring the quality of the solution compared with existing methods.