Scheduling flexible manufacturing systems containing assembly operations based on Petri net structures and dynamics

A new heuristic search approach for scheduling two classes of flexible manufacturing systems (FMSs) that contains assembly operations is proposed. The FMSs are modeled by two classes of Petri nets, called generalized symmetric and asymmetric nets. In the paper, the problem of minimizing makespan is transformed into searching the reachability graph for the optimal (minimal time) firing sequence from the initial marking (state) to the goal marking. A solution of the state equation constitutes a part of the heuristic function. The dynamic information of the nets, such as concurrency and synchronization, is used to adjust the heuristic function since the solution of the state equation may over-estimate the real cost