A deadlock-free scheduling method for automated manufacturing systems using dynamic-edge graph with tokens

The deadlock-free scheduling problems of automated manufacturing systems are discussed in this paper. A new dynamic-edge graph with tokens is designed to model the AMS, to identify distinct part flows, to represent the states and capture the concurrent behavior of the AMS and then an efficient algorithm based on the graph-theoretic approach and genetic algorithm for finding optimal deadlock-free schedules in the automated manufacturing systems is presented. The scheduling problem introduced in this paper consists in sequencing the job operations on resources to avoid the deadlock situation and to minimize the makespan. With the help of dynamic-edge graph models of automated manufacturing systems, a deadlock avoidance policy is proposed to supervise the release and acquisition of resources. In order to satisfy the deadlock-free constraint of chromosomes, the proposed deadlock avoidance policy is imbedded into the decoding procedure of genetic algorithm to reschedule the gene sequences and in the fitness computation procedure, a penalty item for the infeasible solution is involved to prevent the search process from converging to the infeasible solution. The scheduling problems for some automated manufacturing systems with special structures are also discussed. The effectiveness and efficiency of the proposed algorithm is illustrated by several examples.