Deadlock-free scheduling method using genetic algorithm and timed S/sup 3/PR nets

In this paper, a new kind of deadlock-free scheduling method based on genetic algorithm and reachability analysis of timed S/sup 3/PR nets is proposed to solve the scheduling problems of job shop without buffers. Under the framework of timed Petri nets model, the scheduling problem can be described as finding a feasible transition firing sequence in the Petri nets model to avoid deadlock situations and to minimize the makespan. In order to satisfy the deadlock free constraint, a repair procedure is imbedded into the genetic algorithm to improve the quality of infeasible solutions and a penalty item is involved in the fitness computation procedure to prevent the search process from converging to infeasible solutions. The method proposed in this paper can get a feasible scheduling strategy as well as enable the system achieve good performance, and this is empirically shown by simulation results.