A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems

Zhi Wu Li; Meng Chu Zhou; Nai Qi Wu

doi:10.1109/TSMCC.2007.913920

A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems

Zhi Wu Li, Meng Chu Zhou, Nai Qi Wu

Electrical and Computer Engineering

Research output: Contribution to journal › Review article › peer-review

288 Scopus citations

Abstract

Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.

Original language	English (US)
Pages (from-to)	173-188
Number of pages	16
Journal	IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Volume	38
Issue number	2
DOIs	https://doi.org/10.1109/TSMCC.2007.913920
State	Published - Mar 2008

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Software
Information Systems
Human-Computer Interaction
Computer Science Applications
Electrical and Electronic Engineering

Keywords

Computational complexity
Deadlock prevention
Flexible manufacturing system (FMS)
Petri net

Access to Document

10.1109/TSMCC.2007.913920

Cite this

@article{920707762cca452b80c9f0fd36586548,

title = "A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems",

abstract = "Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.",

keywords = "Computational complexity, Deadlock prevention, Flexible manufacturing system (FMS), Petri net",

author = "Li, {Zhi Wu} and Zhou, {Meng Chu} and Wu, {Nai Qi}",

note = "Funding Information: Manuscript received November 12, 2006; revised February 23, 2007 and June 23, 2007. This work was supported in part by the National Nature Science Foundation of China under Grants 60474018, 60773001, and 60574066, in part by the National Research Foundation for the Doctoral Program of Higher Education, Ministry of Education of China under Grant 20070701013, in part by the Laboratory Foundation for the Returned Overseas Chinese Scholars, Ministry of Education, P. R. China under Grant 030401, in part by the Chang Jiang Scholar Program, Ministry of Education, P. R. China, and in part by the 2007–2008 Technion–Xidian Academic Exchange Program. This paper was recommended by Guest Editor M. Jeng.",

year = "2008",

month = mar,

doi = "10.1109/TSMCC.2007.913920",

language = "English (US)",

volume = "38",

pages = "173--188",

journal = "IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews",

issn = "1094-6977",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems

AU - Li, Zhi Wu

AU - Zhou, Meng Chu

AU - Wu, Nai Qi

N1 - Funding Information: Manuscript received November 12, 2006; revised February 23, 2007 and June 23, 2007. This work was supported in part by the National Nature Science Foundation of China under Grants 60474018, 60773001, and 60574066, in part by the National Research Foundation for the Doctoral Program of Higher Education, Ministry of Education of China under Grant 20070701013, in part by the Laboratory Foundation for the Returned Overseas Chinese Scholars, Ministry of Education, P. R. China under Grant 030401, in part by the Chang Jiang Scholar Program, Ministry of Education, P. R. China, and in part by the 2007–2008 Technion–Xidian Academic Exchange Program. This paper was recommended by Guest Editor M. Jeng.

PY - 2008/3

Y1 - 2008/3

N2 - Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.

AB - Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.

KW - Computational complexity

KW - Deadlock prevention

KW - Flexible manufacturing system (FMS)

KW - Petri net

UR - http://www.scopus.com/inward/record.url?scp=40949111905&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40949111905&partnerID=8YFLogxK

U2 - 10.1109/TSMCC.2007.913920

DO - 10.1109/TSMCC.2007.913920

M3 - Review article

AN - SCOPUS:40949111905

SN - 1094-6977

VL - 38

SP - 173

EP - 188

JO - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews

JF - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews

IS - 2

ER -

A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this