A new MIP test for S3PGR2

Yu Ying Shih; D. Y. Chao; Chui Yu Chiu

doi:10.1007/978-1-84882-762-2_4

A new MIP test for S³PGR²

Yu Ying Shih
, D. Y. Chao
, Chui Yu Chiu

Department of Industrial Engineering and Management

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

For general Petri nets such as S³PGR² (systems of simple sequential processes with general resources requirement), the mixed integer programming (MIP) test by Chu et al. is no longer valid. Park et al. modified MIP test and claimed that it can determine the net is live if there are no feasible solutions. However, the net can have livelocks even though it is deadlockfree. The set of places with dead input transitions may not form a siphon and cannot be detected by the above modified MIP test which detects siphons and not their subsets. We show one counter example to confirm this and propose a revised MIP test to fix the problem.

Original language	English
Title of host publication	Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering
Publisher	Springer-Verlag London Ltd
Pages	41-52
Number of pages	12
ISBN (Print)	9781848827615
DOIs	https://doi.org/10.1007/978-1-84882-762-2_4
State	Published - 2009
Event	16th ISPE International Conference on Concurrent Engineering, CE 2009 - Taipei, Taiwan Duration: 20 Jul 2009 → 24 Jul 2009

Publication series

Name	Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering

Conference

Conference	16th ISPE International Conference on Concurrent Engineering, CE 2009
Country/Territory	Taiwan
City	Taipei
Period	20/07/09 → 24/07/09

Keywords

Deadlocks
MIP
Petri nets
Siphons

Access to Document

10.1007/978-1-84882-762-2_4

Cite this

Shih, Y. Y., Chao, D. Y., & Chiu, C. Y. (2009). A new MIP test for S³PGR². In Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering (pp. 41-52). (Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering). Springer-Verlag London Ltd. https://doi.org/10.1007/978-1-84882-762-2_4

Shih, Yu Ying ; Chao, D. Y. ; Chiu, Chui Yu. / A new MIP test for S³PGR². Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering. Springer-Verlag London Ltd, 2009. pp. 41-52 (Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering).

@inproceedings{4801f566bb2a499e9f335dfdfb055c24,

title = "A new MIP test for S3PGR2",

abstract = "For general Petri nets such as S3PGR2 (systems of simple sequential processes with general resources requirement), the mixed integer programming (MIP) test by Chu et al. is no longer valid. Park et al. modified MIP test and claimed that it can determine the net is live if there are no feasible solutions. However, the net can have livelocks even though it is deadlockfree. The set of places with dead input transitions may not form a siphon and cannot be detected by the above modified MIP test which detects siphons and not their subsets. We show one counter example to confirm this and propose a revised MIP test to fix the problem.",

keywords = "Deadlocks, MIP, Petri nets, Siphons",

author = "Shih, \{Yu Ying\} and Chao, \{D. Y.\} and Chiu, \{Chui Yu\}",

year = "2009",

doi = "10.1007/978-1-84882-762-2\_4",

language = "???core.languages.en\_GB???",

isbn = "9781848827615",

series = "Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering",

publisher = "Springer-Verlag London Ltd",

pages = "41--52",

booktitle = "Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering",

note = "16th ISPE International Conference on Concurrent Engineering, CE 2009 ; Conference date: 20-07-2009 Through 24-07-2009",

}

Shih, YY, Chao, DY & Chiu, CY 2009, A new MIP test for S³PGR². in Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering. Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering, Springer-Verlag London Ltd, pp. 41-52, 16th ISPE International Conference on Concurrent Engineering, CE 2009, Taipei, Taiwan, 20/07/09. https://doi.org/10.1007/978-1-84882-762-2_4

A new MIP test for S³PGR². / Shih, Yu Ying; Chao, D. Y.; Chiu, Chui Yu.
Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering. Springer-Verlag London Ltd, 2009. p. 41-52 (Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A new MIP test for S3PGR2

AU - Shih, Yu Ying

AU - Chao, D. Y.

AU - Chiu, Chui Yu

PY - 2009

Y1 - 2009

N2 - For general Petri nets such as S3PGR2 (systems of simple sequential processes with general resources requirement), the mixed integer programming (MIP) test by Chu et al. is no longer valid. Park et al. modified MIP test and claimed that it can determine the net is live if there are no feasible solutions. However, the net can have livelocks even though it is deadlockfree. The set of places with dead input transitions may not form a siphon and cannot be detected by the above modified MIP test which detects siphons and not their subsets. We show one counter example to confirm this and propose a revised MIP test to fix the problem.

AB - For general Petri nets such as S3PGR2 (systems of simple sequential processes with general resources requirement), the mixed integer programming (MIP) test by Chu et al. is no longer valid. Park et al. modified MIP test and claimed that it can determine the net is live if there are no feasible solutions. However, the net can have livelocks even though it is deadlockfree. The set of places with dead input transitions may not form a siphon and cannot be detected by the above modified MIP test which detects siphons and not their subsets. We show one counter example to confirm this and propose a revised MIP test to fix the problem.

KW - Deadlocks

KW - MIP

KW - Petri nets

KW - Siphons

UR - https://www.scopus.com/pages/publications/80051889150

U2 - 10.1007/978-1-84882-762-2_4

DO - 10.1007/978-1-84882-762-2_4

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:80051889150

SN - 9781848827615

T3 - Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering

SP - 41

EP - 52

BT - Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering

PB - Springer-Verlag London Ltd

T2 - 16th ISPE International Conference on Concurrent Engineering, CE 2009

Y2 - 20 July 2009 through 24 July 2009

ER -

Shih YY, Chao DY, Chiu CY. A new MIP test for S³PGR². In Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering. Springer-Verlag London Ltd. 2009. p. 41-52. (Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering). doi: 10.1007/978-1-84882-762-2_4