Abstract: In order to achieve deadlock avoidance and make the most use of resource in Flexible Manufacturing System（FMS）, this paper presents the branch and bound method for optimal supervisor. The method builds the distributed monitor through multi control sites, detects the global state space through the behavior-feasible and distribution-feasible, builds the linear programming model to gain maximum legal state set. Finally, the model of FMS is built with Petri net. Based on the occupation and release of resource in the machining process, the centralized supervisor and distributed supervisors are designed, respectively. The distributed supervisors can effectively avoid deadlock.

Key words: partial controllable Petri nets, distributed supervisors, deadlock avoidance, branch and bound method, linear programming

摘要： 研究了部分可控Petri网柔性制造系统中的死锁避免的问题。为了保证死锁避免和资源最大允许利用，提出了基于分支定界法的Petri网死锁监控器的优化设计方法，采用多个子控制节点对全局状态建立分布式监控器，通过行为可行和分布可行对分布式监控器下合法状态空间进行检测，对最大行为可行子集建立线性规划模型求解最大分布可行合法状态集，得到分布式监控器下的最大合法状态子空间。最后，建立了柔性制造系统的部分可控Petri网模型，针对系统的死锁避免等多个行为特性要求，分别设计了集中式监控器和分布式监控器，分布式监控器能有效地避免死锁。

关键词: 部分可控Petri网, 分布式监控器, 死锁避免, 分支定界法, 线性规划