A suboptimal deadlock control policy for designing non-blocking supervisors in flexible manufacturing systems


Zhao M., UZAM M.

INFORMATION SCIENCES, vol.388, pp.135-153, 2017 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 388
  • Publication Date: 2017
  • Doi Number: 10.1016/j.ins.2017.01.021
  • Title of Journal : INFORMATION SCIENCES
  • Page Numbers: pp.135-153
  • Keywords: Petri net, Deadlock control, Elementary siphons, Resource partial order, Generalized mutual exclusion constraints, LIVENESS-ENFORCING SUPERVISORS, PETRI-NET MODELS, PREVENTION POLICY, ELEMENTARY SIPHONS, DEPENDENT SIPHONS, AVOIDANCE, CONTROLLABILITY, CONSTRAINTS, COMPUTATION, RESOLUTION

Abstract

This work aims to resolve deadlock problems in flexible manufacturing systems. A novel deadlock control policy in the frame of Petri nets formalism is presented for a class of generalized Petri nets, namely G-systems, which can usually model assembly and disassembly operations of multiple resource acquisition. Based on the concept of elementary siphons, all strict minimal siphons (SMS) in an uncontrolled net system are first divided into elementary siphons and dependent ones. After that, a set of linear inequality constraints expressed by state vectors can be formalized for elementary siphons. After being modified by utilizing the conjunctive/disjunctive resources upstream neighborhood policy, a set of generalized mutual exclusion constraints expressed by marking vectors can be obtained. Then, the additional monitors are only designed for elementary siphons, whose control depth variables can be obtained by solving a linear programming problem. As a result, the controllability of dependent ones can be ensured by properly supervising its elementary siphons. Finally, all strict minimal siphons are max'-controlled and no insufficiently marked siphon is generated, which indicates that the sequential resources are allocated reasonably to guarantee the absence of deadlock states. The proposed method can usually lead to a near-optimal non-blocking supervisor with simple structure. A G-system example prone to deadlocks is used to illustrate the applicability and the effectiveness of the proposed method. (C) 2017 Elsevier Inc. All rights reserved.