Deadlock-free scheduling method for automated manufacturing systems using genetic algorithm and Petri nets

A class of flexible manufacturing systems is modeled by timed Petri nets, and a new deadlock free scheduling method based on genetic algorithm and timed Petri net model is proposed. Under the framework of timed Petri nets model, the scheduling problem can be formulated as finding a feasible transition firing sequence to avoid the deadlock situation and to minimize the makespan. In the genetic algorithm, Petri net transition sequence is coded and a deadlock detection method based on siphon technology is addressed to reschedule the sequence of transitions, and thus the quality of solutions can be improved. In the fitness computation procedure, a penalty item for the infeasible solution is involved to prevent the search process from converging to the infeasible solutions. The method proposed In this work can get a feasible scheduling strategy as well as enable the system to achieve good performance, and this is shown by simulation results.