臺灣博碩士論文加值系統

工作流程管理已經被認為是一個企業成功的重要因素。基於合作夥伴
所提議的工作流程方案，公司是否能夠在截止日期或訂單時程內完成交付
而做出正確的決策，這對公司而言是很重要問題。本研究的目的是建立一
個有效的計算方法來分析時間的工作流程。許多研究指出派翠網路（Petri
Nets）能夠充分表達工作流程的問題和解決複雜的時序分析問題。我們提出
一個時間性工作流程網路問題，而這個網路模型屬於工作流程網路中的特
殊問題。我們提出一個演算法來計算最早完成的時間，以及開發一個支援
已標準化派翠網路標記語言（Petri Net Markup Language, PNML）格式的工
具，來幫助工作流程管理中的決策工作。

Workflow management has been recognized as a significant issue to the
success of an enterprise. How to estimate whether the workflow solution
proposed by the partners can meet the due date or schedule of an order is critical
for a company to make the right decision. The objective of this paper is to
develop a computationally efficient algorithm to analyze the timing of
workflows. As pointed out by many studies, the Petri net is able to fully express
the configuration of workflows and solve the complicated timing analysis
problems. We propose an algorithm to compute the earliest completion time for
a class of timed workflow nets and develop a tool based on the standardized
Petri net Markup Language (PNML) to support the decision-making in
workflow management.

摘 要........................III
Abstract................... IV
誌 謝........................V
目 錄....................... VI
圖 目 錄.....................VIII
表 目 錄.....................X
第1 章 緒論...................................1
1.1 工作流程概述...............................1
1.2 工作流程管理系統............................3
1.3 基於派翠網路的工作流程管理系統................6
1.4 研究動機..................................7
1.5 研究目的..................................10
1.6 論文架構..................................10
第2 章 文獻探討................................12
2.1 派翠網路定義...............................12
2.2 基於派翠網路的工作流程模型...................15
2.3 時間派翠程網路定義（Timed Petri Net）........18
2.4 派翠網路標記語言............................19
第3 章 問題模型定義.............................21
第4 章 演算法設計與分析..........................23
4.1 最短完成時間演算法..........................23
4.2 複雜度分析.................................28
第5 章 實作與驗證...............................29
5.1 案例驗證...................................41
第6 章 結論與未來發展............................45
參考文獻.......................................47
附錄..........................................52
圖 目 錄
圖 1 工作流程管理系統發展史...........................................................2
圖 2 工作流程聯盟的參考模型...........................................................6
圖 3 派翠網路架構圖..........................................................................13
圖 4 派翠網路之集合表示法.............................................................13
圖 5 透過轉換觸發後的標記.............................................................14
圖 6. 工作流程網路.............................................................................16
圖 7 工作流程結構..............................................................................17
圖 8. 包含時間參數的派翠網路........................................................19
圖 9 簡單的時間性工作流程網路.....................................................22
圖 10 一般性工作流程網路.................................................................28
圖 11 工作流程派翠網路設計師儲存格式........................................30
圖 12 工作流程派翠網路設計師的操作介面...................................31
圖 13 時間資訊設定............................................................................32
圖 14 使用DOM4J 進行PNML 檔案解析的Java 程式...................38
圖 15 最短完成時間分析軟體............................................................39
圖 16 最短完成時間子網路................................................................40
圖 17 複雜的網路分析結果................................................................41
圖 18 較複雜的時間性工作流程網路...............................................43
IX
圖 19 最短完成時間的子網路............................................................44
圖 20 包含迴路的時間性工作流程網路...........................................58
圖 21 包含迴路的工作流程的最佳解...............................................59
X
表 目 錄
表 1 PNML 標籤...................................................................................20
表 2 最短完成演算法..........................................................................25
表 3 案例分析過程..............................................................................26
表 4 使用WoPeD 儲存的PNML 格式...............................................32
表 5 所有子網路清單..........................................................................42
表 6 迴路問題的最短完成時間演算法.............................................53
表 7 案例分析過程..............................................................................55

[1] Atsushi Inamoto. Object-oriented model driven workflow process analysis.
Proc Of Japan/USA Symposium on Flexible Automation’96, 1996, pp.
1317-1324.
[2] A. Rozinat, M.T. Wynn, W.M.P. van der Aalst, A.H.M. ter Hofstede, C.J.
Fidge, "Workflow simulation for operational decision support", Data &
Knowledge Engineering 68 (2009) 834–850
[3] C. A. Ellis, G. J. Nutt. Modeling and enactment of workflow systems.
Application and Theory of Petri Nets, Springer-Verlag, Chicago, III, 1994.
[4] C. A. Petri, “Kommunikation mit automaten,” Ph.D. dissertation, Inst.
Instrumentelle Math., Bonn, Germany, 1962.
[5] David Hollingsworth, “Workflow Management Coalition The Workflow
Reference Model”, 1995
[6] Ekkart Kindler,” High-level Petri Nets – Transfer Format”, Working Draft
of the International Standard ISO/IEC 15909,2004, Part 2 Version 0.5.0.
[7] Goell, Ric Scott, “Workflow: what is it?”, International Journal of
Micrographics & Optical Technology, Vol.13, Issue: 1, March, 1995, pp.
9-12
[8] G. K. Janssens, B.W. Jan Verelst, and B.Weyn, “Techniques for modeling
workflows and their support for reuse,” in Business Process Management:
Models, Techniques, and Empirical Studies, W. van der Aalst, Ed. Berlin,
Germany: Springer-Verlag, 2000, pp. 1–15.
[9] HAYES, K. AND K. LAVERY, Workflow management software: the
business opportunity, Ovum, 1991
[10] Hua Duan, Qingtian Zeng, Huaiqing Wangc, Sherry X. Sun, Dongming Xu,
“Classification and evaluation of timed running schemas for workflow
based on process mining”, The Journal of Systems and Software 82 (2009)
400–410
[11] Huaiqingd Wang, Qingtian Zeng, Modeling and Analysis for Workflow
Constrained by Resources and Nondetermined Time: An Approach Based
on Petri Nets, IEEE Transactions on Systems, Man and Cybernetics, Part A,
Volume 38, Issue 4, July 2008 Page(s):802 – 817
[12] http://www.google.com.tw/
[13] http://www.w3schools.com/xml/default.asp
[14] http://www.w3.org/TR/xpath
[15] http://www.w3.org/XML/Schema
[16] http://www.w3.org/TR/xslt
[17] http://www.saxproject.org/
[18] http://www.w3.org/DOM/
[19] http://www.jdom.org/
[20] http://www.dom4j.org/
[21] JianQiang Li, YuShun Fan, MengChu Zhou, "Timing constraint workflow
nets for workflow analysis", IEEE Transactions on Systems, Man and
Cybernetics, Part A, Volume 33, Issue 2, March 2003 Page(s):179 – 193
[22] KOULOPOULOS, T.M. , The Workflow Imperative, Van NostrandReinhold,
New York, 1995.
[23] Murata, T, “Petri nets: Properties, analysis and applications,” Proceedings of
the IEEE, Vol. 77, Issue 4, April ,1989, pp. 541- 580.
[24] M.T. Wynn, H.M.W. Verbeek, W.M.P. van der Aalst, A.H.M. ter Hofstede, D.
Edmond, "Soundness-preserving reduction rules for reset workflow nets",
Information Sciences 179 (2009) 769–790
[25] N. R. Adam, V. Atluri, and W. K. Huang, “Modeling and analysis of
workflows using Petri nets,” J. Intell. Inf. Syst., vol. 10, no. 2, pp. 131– 158,
Mar. 1998.
[26] Natalie S. Glance, Daniele S. Pagani, and Remo Pareschi. Generalized
process structure grammars(GPSG) for flexible representations of work.
Proc of CSCW’96, 1996, pp. 180-189.
[27] Paul Dourish, Jim Holmes, Allan MacLean, and etc. Freeflow: mediating
between representation and action in workflow systems. Proc of CSCW’96,
1996, pp. 190-198.
[28] PNML, http://www2.informatik.hu-berlin.de/top/pnml/about.html
[29] PNML, “Software and Systems Engineering – High-level Petri Nets, Part 2:
Transfer Format”, International Standard ISO/IEC 15909-2. Working Draft
Version 0.9.0, June 2005
[30] Ping Sun, Changjun Jiang, “Analysis of workflow dynamic changes based
on Petri net”, Information and Software Technology 51 (2009) 284–292
[31] Qingtian Zeng, Huaiqing Wang, Dongming Xu, Hua Duan and Yanbo Han,
"Conflict Detection and Resolution for Workflow Constrained by Resources
and Non-determined Duration", Journal of System Software
[32] Raul Medina-Mora, Terry Winograd, Rodrigo Flores, and etc. The Action
workflow approach to workflow management technology. Proc of
CSCW’92, 1992, pp. 281- 288
[33] Seungchul Ha, Hyo-Won Suh, "A timed colored Petri nets modeling for
dynamic workflow in product development process", Computers in Industry
59 (2008) 193–209
[34] Ste’phane Julia, Fernanda Francielle de Oliveira, Robert Valette, "Real time
scheduling of Workflow Management Systems based on a p-time Petri net
model with hybrid resources", Simulation Modelling Practice and Theory 16
(2008) 462–482
[35] SCH ‥AL, T. (1996), Workflow Management for Process Organisations,
Lecture Notes in Computer Science 1096, Springer-Verlag, Berlin.
[36] SHI Meilin, YANG Guangxin, XIANG Yong, WU Shangguang, “Workflow
Management Systems: A Survey”, Proceedings of IEEE Intl Conf on
Communication Technology, Beijing:, Oct, 1998
[37] W.M.P. van der Aalst, Three good reasons for using a petri-net-based
workflow management system. In: Navathe, S.,Wakayama, T., (Eds.),
Proceedings of the International Working Conference on Information and
Process Integration in Enterprises (IPIC’96), Camebridge, Massachusetts,
1996, pp.179–201.
[38] W.M.P. van der Aalst. Petri-net-based Workflow Management Software. In
A. Sheth, editor, Proceedings of the NFS Workshop on Workflow and Proc.
Automation in Information Systems, pages 114–118, Athens, Georgia, May
1996
[39] W.M.P. van der Aalst. A class of Petri net for modeling and analyzing
business processes. Computing Science Reports 95/26, Eindhoven
University of Technology, Eindhoven, 1995.
[40] WFMC. Workflow Management Coalition Terminology and Glossary
(WFMC-TC-1011). Technical report, Workflow Management Coalition,
Brussels, 1996.
[41] WFMC, Workflow reference model, Technical report, Workflow
Management Coalition, Brussels, 1994
[42] WfMC. Workflow management coalition audit data specification. 1996
[43] WfMC. Workflow Management Coalition Workflow Client Application
(Interface 2) Application Programming Interface (WAPI) Specification.
1996
[44] WfMC. Workflow Management Coalition Workflow Client Application
(Interface 2) Application Programming Interface (WAPI) Naming
Conventions. 1996
[45] WfMC. Workflow management coalition workflow standard -
interoperability abstract specification. 1996
[46] WfMC. Workflow process definition read/write interface: request for
comments. 1995
[47] W. Reisig, “Petri nets: An introduction,” in Monographs in Theoretical
Computer Science: An EATCS Series, vol. 4. Berlin, Germany: Springer-
Verlag, 1985.
[48] “WoPeD”, http://www.woped.org/
[49] Yang Guangxin, Shi Meilin, Xiang Yong, etc. Wowww!: managing
workflow on the world wide web. Proc of ICCT''98, Beijing, 1998