|
|||||
|
|
An extraction algorithm for a set of elementary siphons based on mixed-integer programming |
|
| Authors: | Shaoyong Li Zhiwu Li Hesuan Hu Abdulrahman Al-Ahmari Aimin An |
| Institution: | 1. School of Electro-Mechanical Engineering, Xidian University, Xi'an 710071, P. R. China;School of Civil Engineering, Lanzhou University of Technology, Lanzhou 730050, P. R. China 2. School of Electro-Mechanical Engineering, Xidian University, Xi'an 710071, P. R. China 3. School of Electro-Mechanical Engineering, Xidian University, Xi'an 710071, P. R. China;College of Engineering, King Saud University, Riyadh 11421, Saudi Arabia 4. 2School of Civil Engineering, Lanzhou University of Technology, Lanzhou 730050, P. R. China |
| Abstract: | Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources (S3PR). At each iteration, by a mixed-integer programming (MIP) method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials. |
| Keywords: | Petri net flexible manufacturing system deadlock prevention mixed integer programming elementary siphon |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ | |