Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/111457
|
| Title: | 建構派翠網路封閉形式解決方案的序曲：從變型K-階S3PR系統開始
The overture of constructing the closed-form solution for Petri Nets: begin from the variant k-th order S3PR system |
| Authors: | 游宗憲 |
| Contributors: | 趙玉
陳春龍
游宗憲 |
| Keywords: | 控制系統
離散事件系統
彈性製造系統
派翠網路
Control systems
Discrete event systems
Flexible manufacturing systems
Petri nets |
| Date: | 2017 |
| Issue Date: | 2017-07-31 10:59:38 (UTC+8) |
| Abstract: | 因應物聯網、機器人和雲端計算等系統快速的科技創新，我們需要更有效之方法來模型化由上述系統所架構出來愈趨複雜的動態資源配置系統，以解決類似瓶頸、死結等潛藏的系統控制相關問題。為了解決以派翠網路模型化大型系統一直存在的指數倍數成長之複雜性問題，一個即使運用MIP（混合整數規劃）方法於可達性分析也是完全NP（非確定性多項式時間）的問題，趙玉教授率先以開發k階和k網系統的控制相關狀態(CRSs)數量之封閉形式解決方案(簡稱封閉解)，來突破此一指數倍數成長複雜性的障礙。然而，對稱網路結構的屬性，限縮了此兩系統在模型化系統中可應用的範圍;同時由於不可避免的死結的狀況，也阻礙了兩個系統的並行處理能力。為了延伸派翠網路封閉解的研究領域至非對稱系統，及強化對大型即時動態資源分配非對稱系統的模型化能力，本論文擴展派翠網路封閉解的研究領域至所謂的「左邊一般化k階系統」、「左邊一般化k網系統」和「A網系統」等三種不同類型的基本非對稱系統。「左邊一般化k階（相對於k網）系統」是在k階（相對於k網）之控製行程的任意位置，使用一非共享資源的網路模型，為模型化具有客製化製程系統之基本網路架構; 「A網系統」是在一k階系統中，連接一頂層非共享圈子網（TNCS）的網路模型，在實際應用中，為模型化具共享相同製程系統的基本網路架構。本論文透過非共用資源在等價網路(k階（相對於k網）)的影響性分析，及其等價網路之封閉解為基礎，建構「左邊一般化k階（相對於k網）系統」之封閉解;在「A網系統」中，由於TNCS和連接的缺陷 k階系統兩個子系統的獨立性，首先我們可以從其相關之k階系統的封閉解中，排除不可能狀態的數量，推導出缺陷k階系統的封閉解，然後以累計加總缺陷k階系統及TNCS兩個子系統在各種TNCS中存在不同權杖個數狀況下的封閉解乘積，構建出「A網系統」的封閉解。在實際應用中，我們可透過由封閉解所產生之即時CRS信息，強化對大型動態即時資源分配系統的模型化能力。例如，採用本論文所提出的避免死結演算法，可以在不用附加控制器之狀況下，實現k階和k網系統之並行處理的功能;並且可以在k-網系統中，在不用暫停所有系統的工作流程狀況下，實現動態行程配置的功能。除了應用虹吸計算方法構建非對稱系統的基礎封閉解外，本論文還提出了依據其反向網路被驗證的有效信息為基準，新的由模型驗證之以知識基礎的理論分析方法，加速派翠網路封閉解的建構。在此，本論文開啟了以變型k階系統為啟端，建構派翠網路封閉解新的研究時代。
In the light of the rapid innovation of the Internet of Things (IoT), robot systems, and cloud computing systems, we need an efficient methodology to model gradually more and more complicated, real-time resource allocation systems (RAS), constructed using the systems mentioned above, for solving issues such as bottlenecks, deadlocks, and other embedded system-control-related problems. To solve the exponentially increasing complexity in the persistent problem of modeling large systems using Petri nets, which is an NP (nondeterministic polynomial time)-complete problem even when MIP (mixed integer programming) is employed for reachability analysis, Chao broke this barrier by developing the first closed-form solution (CFS) for the number of Control Related States (CRSs) for k-th order and k-net systems. However, the properties of symmetric net structures limit their application range in modeling systems; the inevitable deadlock obstructs the capability of concurrent processing in both systems. To enhance the capability of modeling large dynamic, real-time resource allocation in asymmetric systems, this dissertation extends the research on the CFS of PNs to the so-called Gen-Left k-th order system, the Gen-Left k-net system, and the A-net system, which comprise the three different types of fundamental asymmetric systems. A Gen-Left k-th order (resp. k-net) system is a k-th order (resp. k-net) system containing a non-sharing resource (NSR) at arbitrary locations in the control process, which is the fundamental net structure for modeling contained customized manufacturing processes inside a system. An A-net system is a k-th order system connected to a Top Non-sharing Circle Subnet (TNCS), which is the fundamental net structure to model a shared common manufacturing processing system in real applications. Based upon analyzing the effects of one NSR in the equivalent, the corresponding k-th order (resp. k-net) system, and an equivalent CFS, this dissertation derives the CFS for the Gen-Left k-th order (resp. k-net) system. Due to the independence of the TNCS and the connected Deficient k-th order system, we can first derive the CFS for a Deficient k-th order system just by excluding the number of impossible states from the CFS for its corresponding k-th order system. Then, the CFS of an A-net is constructed by summing the products of the CFS for the two sub-systems in each different case under the condition of the number of tokens inside TNCS. Based on real-time CRS information derived, we can enhance the capability for modeling a large dynamic, real-time resource allocation system in real applications. Employing the proposed deadlock-avoidance algorithm, for instance, we can realize concurrent processing in both k-th order and k-net systems without additional controllers being implemented; and the function of dynamic process allocation in a k-net system without suspending the system’s working flows. In addition to applying siphon computation to construct the fundamental CFS for asymmetric systems, this dissertation pioneers and proposes a new knowledge-based, analysis methodology, called proof by model, to accelerate the construction of the CFS for a PN based upon the validation information from its reverse net. This dissertation opens a new research era for constructing the CFS for PNs beginning from the Variant k-th order system. |
| Reference: | References
[1] Chao, D. Y. (2005). Reachability of Nonsynchronized Choice Petri nets and its applications. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), 35(6), 1203–1213. doi:10.1109/tsmcb.2005.850171.
[2] Chao, D. Y. (2006). Computation of elementary siphons in Petri nets for deadlock control. The Computer Journal, 49(4), 470-479.
[3] Chao, D. Y. (2011a). Improvement of suboptimal siphon- and FBM-Based control model of a well-known S3PR. IEEE Transactions on Automation Science and Engineering, 8(2), 404-411.
[4] Chao, D. Y. (2011b). Enumeration of lost states of a suboptimal control model of a well-known S3PR. IET Control Theory & Applications, 5(11), 1277-1286.
[5] Chao, D. Y. (2011c). A simple modification of deadlock prevention policy of S3PR based on elementary siphons. Transactions of the Institute of Measurement and Control, 33(1), 93-115.
[6] Chao, D. Y. (2012). Recursive solution of number of reachable states of a simple subclass of FMS. International Journal of Systems Science, 45(3), 702-710.
[7] Chao, D. Y. (2014). Enumeration of reachable (forbidden, live, and deadlock) States of k-th order system of Petri nets. IMA Journal of Mathematical Control and Information, 32 (4), 823-837.
[8] Chao, D. Y. (2016). Closed-form solution of controller synthesis for infinitely large systems of resource sharing systems of a subclass of Petri nets. Transactions of the Institute of Measurement and Control, 38(1), 83-92.
[9] Chao, D. Y., Chen, J.-T., & Yu, F. (2012). Enumeration of reachable and other states of simple version of systems of simple sequential processes with resources (S3PR). In Industrial Electronics Society, 2012 ISIE 2012. 21st IEEE International Symposium on Industrial Electronics, Hangzhou, China, 28–31 May 2012. IEEE: pp. 1369-1374.
[10] Chao, D. Y., Chen, J.-T., & Yu, F. (2013). A novel liveness condition for S3PGR2. Transactions of the Institute of Measurement and Control, 35(2), 131-137.
[11] Chao, D. Y., Chi, Y. P., Yu, T. H., Yu, L. C., & Lee, M. Y. (2016). Proof by model: a new knowledge-based reachability analysis methodology for Petri net. IMA Journal of Mathematical Control and Information, dnw025.
[12] Chao, D. Y., & Wu, K.-C. (2013). An integrated approach for supervisory control of a subclass of Petri nets. Transactions of the Institute of Measurement and Control, 35(2), 117-130.
[13] Chao, D. Y., & Yu, T. H. (2013) Enumeration of reachable (forbidden, live, and deadlock) states of top k-th order system (with a non-sharing resource place) of Petri nets. Paper presented at the meeting of IECON 2013 - 39th Annual Conference on IEEE Industrial Electronics Society, pp. 3515-3521, Vienna, Austria.
[14] Chao, D. Y., & Yu, T. H. (2015). Computation of control related states of bottom k-th order system (with a non-sharing resource place) of Petri nets. Transactions of the Institute of Measurement and Control, 37(3), 382–395.
[15] Chao, D. Y., Yu, T. H., & Liou, C. C. (2014, April). Enumeration of reachable, forbidden, live, and deadlock states of bottom k-th order system (with a left side non-sharing resource place) of Petri nets. Paper presented at the meeting of Networking, Sensing and Control (ICNSC), 2014 IEEE 11th International Conference (pp. 572-577), Miami, FL.
[16] Chao, D. Y., Yu, T. H., & Wu, S. C. (2014, April). Closed form formula construction to enumerate control related states of k-th order S3PR system (with a top left side non-sharing resource place) of Petri nets. Paper presented at the meeting of Networking, Sensing and Control (ICNSC), 2014 IEEE 11th International Conference on (pp. 132-137), Miami, FL.
[17] Chao, D. Y., & Yu, T. H. (2014, December). Enumeration of reachable, forbidden, live states of gen-left k-net system (with a non-sharing resource place) of Petri nets. Paper presented at the meeting of Computational Intelligence in Control and Automation (CICA), 2014 IEEE Symposium (pp. 1-7), Orlando, FL.
[18] Chao, D. Y., & Yu, T. H. (2015, November). MLR: A new concept to launch a partial deadlock avoidance policy for k-th order system of Petri Nets. Paper presented at the meeting of Industrial Electronics Society, IECON 2015-41st Annual Conference of the IEEE (pp. 003148-003152), Yokohama, Japan .
[19] Chao, D. Y., & Yu, T. H. (2016). The fundamental closed-form solution of control-related states of kth order S3PR system with left-side non-sharing resource places of Petri nets. International Journal of Control, 89(1), 169-178.
[20] Chao, D. Y., & Yu, T. H. (2017). Construct the closed-form solution of A-net of Petri nets by case study. Advances in Mechanical Engineering (AIME), 9(2).
[21] Ezpeleta, J. J., Colom, M., & Martinez, J. (1995). A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation, 11(2), 173-184.
[22] Ferrarini, L. (1994). On the reachability and reversibility problems in a class of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics,24(10), 1474-1482.
[23] Hiraishi, K., & Ichikawa, A. (1988). A class of Petri nets that a necessary and sufficient condition for reachability is obtainable. Transactions of the Society of Instrument and Control Engineers, 24(6), 635-640.
[24] Ichikawa, A., Yokoyama, K., & Kurogi, S. (1985). Control of event-driven systems - reachability and control of conflict-free Petri nets. Transactions of the Society of Instrument and Control Engineers, 21(4), 324-330.
[25] Kostin, A. E. (2003). Reachability analysis in T-invariant-less Petri nets. IEEE Transactions on Automatic Control, 48(6), 1019-1024.
[26] Lee, D. I., Kumagai, S., & Kodama, S. (1990). Reachability of LSFC nets. IEEE International Symposium on Circuits and Systems, 4(5), 2666-2669.
[27] Lee, J. S., Zhou, M. C., & Hsu, P. L. (2005). An application of Petri nets to supervisory control for human-computer interactive systems. IEEE Transactions on Industrial Electronics, 52(5/ Oct), 1220-1226.
[28] Liang, H., & Chao, D. Y. (2012). Enumeration of reachable states for arbitrary marked graphs. IET Control Theory and Applications, 6(10), 1536-1543.
[29] Liu, M., Wang, S., & Li, Z. W. (2013). Supervisor reconfiguration for deadlock prevention by resources reallocation. Journal of Applied Mathematics, Article ID 315894, http://dx.doi.org/10.1155/2013/315894.
[30] Miyamoto, T., & Horiguchi, K. (2011). Modular reachability analysis in fundamental class of multi-agent nets. Paper presented at the meeting of IECON 2011 - 37th Annual Conference on IEEE Industrial Electronics Society. Melbourne, Australia, 7–10 Nov. 2011. IEEE: pp. 3782-3787.
[31] Mizuno, N., Ohta, A., & Tsuji, K. (2007). Reachability problem of marked graphs with batch processing arcs. Paper presented at the meeting of IECON 2007. 33rd Annual Conference of IEEE Industrial Electronics. Taipei, Taiwan, 5–8 Nov. 2007. IEEE: pp. 70-75.
[32] Nazeem, A., Reveliotis, S.A., Wang, Y., & Lafortune, S. (2011). Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case. IEEE Transactions on Automatic Control, 57(7), 1670-1684.
[33] Schrijver A. (1998). Theory of linear and integer programming. John Wiley & Sons.
[34] Shih, Y. Y., & Chao, D. Y. (2010). Sequence of control in S3PMR. Computer Journal, doi:10.1093/comjnl/bxp081.
[35] Starke, P. H. (1992). INA: Integrated Net Analyzer: Handbook. Germany, Humboldt University.
[36] Sun, P., Jiang, C. J., & Zhou, M. C. (2009). Interactive Web service composition based on Petri net. Transactions of the Institute of Measurement and Control, 33(1), 116-132.
[37] Uzam, M., & Zhou, M. C. (2006). An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems. International Journal of Production Research, 44(10), 1987-2030.
[38] Wang, J. C., Zhou, X. Z., & Ding, J. H. (2010). Software architectural modelling and verification: a Petri net and temporal logic approach. Transactions of the Institute of Measurement and Control, 33(1), 168-181.
[39] Yu, T. H. (2016 a). Parameterized of control related states of gen-right k-th order system of Petri nets based on proof by model of gen-left. Paper presented at the meeting of Industrial Electronics Society, IECON 2016-43st Annual Conference of the IEEE (pp. 276-281). Florence, Italy.
[40] Yu, T. H. (2016 b). The closed-form solution of the control related states of deficient gen-left k-th order system (the essential element of non-sharing subnet) of Petri Nets. Paper presented at the meeting of 2016 IEEE Symposium on Computational Intelligence in Control and Automation. Athens, Greece.
[41] Zimmermann, A. (2012). http://www.tu-ilmenau.de/ TimeNeT, Technische Universität Ilmenau, System and Software Engineering, D-98684 Ilmenau, Germany. |
| Description: | 博士
國立政治大學
資訊管理學系
100356506 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G1003565061 |
| Data Type: | thesis |
| Appears in Collections: | [資訊管理學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 254 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
