|
Xu Gang
Wu Zhiming
College of Mechanical Engineering and Applied
Electronics,
Beijing University of Technology,
Beijing 100022, China |
|
|
DEADLOCK-FREE SCHEDULING
METHOD BASED ON PETRI NET
AND GA*
Abstract:
An efficient algorithm for finding an optimal deadlock-free schedule in a manufacturing system with very limited buffer is presented. This algorithm is based on the effective genetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect the token player assuring deadlock-free. In order to make the scheduling strategy generated by GA meet the required constraint of deadlock-free, Petri net is involved to make the implementation of the job scheduling in an FMS deadlock-free. The effectiveness and efficiency of the proposed approach is illustrated by using an example.
Key words: GA Petri net Deadlock-free scheduling |