Polynomial-complexity supervisory control for flexible assembly systems based on Petri nets

ABSTRACT

Flexible assembly systems (FASs) are a class of resource allocation systems with assembly processes as their inevitable components. Deadlock resolution and liveness enforcement play important roles in the supervisory control of FASs. Design of deadlock avoidance policies (DAPs) for FASs has received significant attention recently. The computational feasibility of real-time DAPs is of great importance for the policies’ online implementation in practical applications. However, there are difficulties brought by the existence of assembly processes. So far, nearly all known DAPs with polynomial-time complexity apply only to systems without assembly operations. This study focuses on the deadlock-avoidance control problem of a broader class of FASs as compared to those discussed in the existing work. Specifically, for an FAS addressed in this paper, each resource can be shared by any two operations, and it also allows multiple resource acquisition at each processing step. This work develops a novel DAP for such FASs, which is based on their Petri-net models and actually an improved Banker’s algorithm that consists of three executable algorithms. Moreover, the computational time complexity of the DAP is polynomial in the size of the system model. The application of the proposed method to some examples illustrates its effectiveness and efficiency.

KEYWORDS:

• Deadlock avoidance
• discrete event systems
• flexible assembly system (FAS)
• Petri nets

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant Nos. 61673228, 61374066, 61573265, and 61402216, the National Key Basic Research Program of China under Grant No. 2013CB035406, and China Postdoctoral Science Foundation funded project under Grant No. 2015M571894.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China under Grant Nos. [61673228], [61374066], [61573265], and [61402216], the National Key Basic Research Program of China under Grant No. [2013CB035406], and China Postdoctoral Science Foundation funded project under Grant No. [2015M571894].