A Petri Net Model with Time Window Constraints

時間視窗派翠網路模式

10.29977/JCIIE.200703.0002

陳彥良(Yen-Liang Chen)；張元斌(Yuan-Bin Chang)；許秉瑜(Ping-Yu Hsu)

派翠網路 ； 時間視窗 ； 資源 ； Petri net ； time-window ； resource

工業工程學刊

24卷2期（2007 / 03 / 01）

110 - 119

英文

時間視窗已成為真實系統中常被考量的時間限制條件。為了表達此種語意需求，許多既有的派翠網路研究於transition中賦予單一的時間區間，做為enabled transition（被致能的transition）可以觸發(fire)的時間條件。本論則就時間視窗的意涵，進一步分兩方面延伸傳統時間視窗派翠網路。首先，本論文使用多個無重疊的時間區間取代單一時間區間，來表達資源或工作可運作的實際時間範圍。其次，本論文於transition（工作）及place（如資源）中均可設定各自的時間區間，因此可同時考量到工作(transition)及資源(place)的可用時間限制。尤其，我們定義一種新的place 稱為resource place，此類place上的時間視窗乃用以表達資源可被使用在執行特定工作的時間範圍。基此，本論文提供了一個名為TWPN（時間視窗派翠網路，Time Window Petri Net）的正規模式，經由本模式，可以清楚描述出多個不同的作業案例(case)搶用相同資源，且各個作業及被搶用的資源又有個自的可用時間視窗限制的複雜狀況，並可計算出各個作業案例在使用共同資源下，實際完成的真實時間。最後，本論文亦証明本模式計算所得的作業案例真正執行時間是正確的。

Time window has been a common form of time constraint considered in real world systems. Viewing this requirement, some previous researches on Petri nets included time window constraint into their models by attaching a single time interval to a transition, denoting the time period when the transition may fire after it is enabled. This paper further extends the traditional time-window Petri net model in two respects. First, we extend the time window from a single interval to multiple intervals, that is, a sequence of non-overlapped time intervals is used to denote the periods when the task can be executed. Second, we add the time window constraints into both transitions and places. Specifically, we define a new kind of places, called resource places, and the time window associated with a resource place denotes the time periods when the resource can support task execution. Accordingly, we develop a formal model, named as TWPN (Time Window Petri Net), through which we can model the scenario that multiple cases which share common resources are performed concurrently subject to time windows constraints. Finally, we also show that the model can correctly compute the execution time of each case.

1. Aalst, W.(1998).The application of Petri nets to workflow management.Journal of Circuits, Systems and Computers,8,21-66.
2. Alpan, G.,M. A. Jafari(1997).Dynamic analysis of timed Petri nets: a case of two processes and a shared resource.IEEE Transactions on Robotics and Automation,13,338-346.
3. Chen, Y. L.,L. J. Hsiao(2003).Shipping problems with body clock constraints.Computers and Operations Research,30,1037-1049.
4. Gaujal, B.,M. Jafari,M. B. Gursoy,G. Alpan,(1995).Allocation Sequences of two-processes sharing a resource.IEEE Transactions on Robotics and Automation,11,748-753.
5. Hasegawa, K.,P. E. Miyagi,D. J. Santos Filho,K.Takahashi,L. Ma,M. Sugisawa(1999).On resource arc for Petri net modeling of complex resource sharing system.Journal of International Robotic Systems Theory and Applications,26,423-437.
6. Kim, J.,A. A. Desrochers,A. C. Sanderson(1995).Proceedings of 1995 IEEE International Symposium on Assembly and Task Planning.
7. Kumar, A.,L. S. Ganesh(1998).Use of Petri nets for resource allocation in projects.IEEE Transactions on Engineering Management,45,49-56.
8. Li, J.,Y. S. Fan,M. C. Zhou(2003).Timing constraint workflow nets for workflow analysis.IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans,33,179-193.
9. Ling, S.,H. Schmidt(2000).Proceedings of IEEE Int. Conference on Systems, Man, and Cybernetics.
10. Murata, T.(1989).Proceedings of the IEEE.
11. Peterson, J. L.(1981).Petri Net Theory and the Modeling of Systems.Englewood Cliffs, NJ:Prentice-Hall.
12. Simon, C.D.,Y. Pascal(2003).Proceedings of IEEE Conference on Emerging Technologies and Factory Automation.
13. Tsai, J. J. P.,S. J. Yang,Y. H. Chang(1995).Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications.IEEE Transactions on Software Engineering,21,32-49.
14. Xu, D.,X. He,Y. Deng(2002).Compositional schedulability analysis of real-time systems using time Petri nets.IEEE Transactions on Software Engineering,28,984-996.
15. Zuberek, W. M.(2001).Timed Petri nets in modeling and analysis of cluster tools.IEEE Transactions on Robotics and Automation,17,562-575.
16. Zuberek, W.M.,W. Kubiak(1999).Timed Petri nets in modeling and analysis of simple schedules for manufacturing cells.Computers and Mathematics with Applications,37,191-206.