考虑缓冲区的自动生产单元的无死锁调度策略  

Deadlock-free scheduling method for automated production cell including buffer

作　　者：徐刚[1] 吴智铭[1] 

机构地区：[1]上海交通大学自动化系,上海200030

出　　处：《控制理论与应用》2005年第2期229-236,共8页Control Theory & Applications

基　　金：国家自然科学基金资助项目(60074011;70071017).

摘　　要：在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.Deadlock must be avoided in a manufacturing system.In this paper,an efficient algorithm for finding an optimal deadlock_free schedules in a Manufacturing System with very limited buffer is presented.First,the deadlock problem and its graph theory representation is introduced.Then based on the effective genetic algorithm (GA) search method,the graph theory is introduced to assure deadlock_free.In order to make the scheduling strategy generated by GA meet the required constrains,a deadlock detection procedure based on graph theory is involved as a condition to select deadlock-free scheduling,or to allocate the buffer.So the feasible scheduling result is obtained while the main performance indicator is guaranteed.Finally,a case is given to demonstrate the effectiveness of this method.

关 键 词：遗传算法 图论 无死锁调度 

分 类 号：TH165[机械工程—机械制造及自动化]