一种运用图论进行FMS无死锁调度的方法

A Kind of Deadlock-Free Scheduling Method Using Directed-Graph

在制造系统中 ,必须防止死锁的发生。本文提出一种在制造系统 (带有限缓冲区 )中搜索最优的无死锁调度算法。此算法建立在遗传算法的基础上 ,运用图论算法来保证无死锁调度结果。为了保证遗传算法生成的调度策略能够满足所要求的约束 ,运用图论方法选择无死锁个体 ,添加缓冲区 ,从而在保证了系统的主要性能指标的同时 ,得到系统可行的无死锁的调度结果。本文的主要创新之处在于提出了一种考虑系统缓冲区的无死锁调度方法。

Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding an optimal deadlock-free scheduling in a manufacturing system with very limited buffer is presented. This algorithm is based on the effective Genetic Algorithm (GA) search method, and graph theory is introduced to assure deadlock-free. In order to make the scheduling strategy generated by GA meet the required constraints, a deadlock detection procedure based on graph theory is involved as a condition to select deadlock-free scheduling, and to allocate the buffer. So the feasible scheduling result is obtained while the main performance indicator is guaranteed. The effectiveness and efficiency of the proposed approach is demonstrated using an example at the end of the paper.