基于集束搜索和银行家算法的柔性制造系统无死锁调度  

A Deadlock Free Scheduling of Flexible Manufacturing System Based on Beam Search and Banker's Algorithm

作　　者：黄文婷[1] 吴智铭[1] 

机构地区：[1]上海交通大学CIMS实验室

出　　处：《微型电脑应用》2008年第6期23-24,16,共3页Microcomputer Applications

摘　　要：本文提出了一种基于启发式规则的无死锁调度算法,该算法基于集束搜索方法,局部评价函数和全局评价函数,在无缓冲区的情况下,采用单步前瞻的银行家算法来避免死锁。该算法可以迅速解决复杂制造系统的死锁和调度问题,折衷了计算时间的消耗和调度结果的质量。This paper proposes a deadlock free scheduling algorithm based on heuristic methods. The algorithms are based on beam search, local evaluation function and global evaluation function. In the system without buffer, we adopt a one-step look-ahead banker's algorithm to avoid deadlock. The algorithm can resolve the deadlock and scheduling problems of complex systems, and provide a tradeoff between computation expense and solution quality.

关 键 词：柔性制造系统(FMS) 有向图 银行家算法 集束搜索 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]