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

工業工程與管理系

研究成果: 書籍/報告/會議論文中的章節 › 會議投稿 › 同行評審

7 引文斯高帕斯（Scopus）

摘要

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.

原文	English
主出版物標題	Global Perspective for Competitive Enterprise, Economy and Ecology - Proceedings of the 16th ISPE International Conference on Concurrent Engineering
發行者	Springer-Verlag London Ltd
頁面	41-52
頁數	12
ISBN（列印）	9781848827615
DOIs	https://doi.org/10.1007/978-1-84882-762-2_4
出版狀態	Published - 2009
事件	16th ISPE International Conference on Concurrent Engineering, CE 2009 - Taipei, Taiwan 持續時間: 20 7月 2009 → 24 7月 2009

出版系列

名字	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
國家/地區	Taiwan
城市	Taipei
期間	20/07/09 → 24/07/09

存取文件

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

其它文件與鏈接

Link to publication in Scopus

引用此

Shih, Y. Y., Chao, D. Y., & Chiu, C. Y. (2009). 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 (頁 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. 頁 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². 於 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, 頁 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).

研究成果: 書籍/報告/會議論文中的章節 › 會議投稿 › 同行評審

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². 於 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