FMS scheduling using Petri nets and heuristic search

A method for scheduling of flexible manufacturing systems by merging Petri net modeling and heuristic search is presented. The method uses the Petri net model to generate and search a partial reachability graph, and presents an optimal or near-optimal schedule in terms of a firing sequence of transitions of the Petri net model of the system. This method can easily handle routing flexibility and shared resources. Taking this approach also relieves the analytical burden since it becomes less urgent to analyze the large net to guarantee freedom from deadlock, or liveliness once an optimal schedule is developed. Some heuristic functions to guide the search are explored, and preliminary results and the search algorithm are presented