关键词: 自动制造系统, 死锁预防, 基本信标, 混合整数规划法

Abstract: To solve the deadlock problem arising in automated manufacturing systems，an iterative deadlock prevention policy via the combination of Mixed Integer Programming (MIP) and Petri nets was proposed. According to such a policy， any one of the 0/1 variables in an MIP model could be employed to detect whether or not a place or transition in the corresponding Petri net was related to a maximally emptied siphon， from which one strict minimal siphon could be easily extracted. Subsequently， this policy could derive a set of elementary siphons without enumeration of all the strict minimal siphons so that its time complexity was remarkably decreased. Furthermore， the control of such a set of elementary siphons would lead to a more permissive system with a much simpler supervisor. Experimental results validated the effectiveness and efficiency of the proposed policy.

Key words: automated manufacturing systems, deadlock prevention, elementary siphon, mixed integer programming