Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

Abstract

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.

Keywords:

• flexible manufacturing system
• timed Petri net
• deadlock control
• scheduling
• genetic algorithm

Acknowledgements

The authors would like to thank the Editor, the Associate Editor, and all anonymous referees for their thoughtful comments and suggestions that helped to improve the quality of this study.