Deadlock-free scheduling method using Petri net model analysis and GA search

In this paper, an efficient algorithm for finding optimal deadlock-free schedules in a Flexible Manufacturing System (FMS) modeled by a kind of Petri net, Systems of Simple Sequential Processes with Shared Resources (S⁴R) nets, is presented. This algorithm is based on an effective Genetic Algorithm (GA) search method, and the structural elements analysis of the Petri net. In order to find the optimum and deadlock-free scheduling strategy from the population generated by the GA, a Petri net structural analysis procedure is involved as a criterion to select among the populations and to make the job scheduling deadlock-free. The effectiveness and efficiency of the proposed approach is illustrated using an example.