隨著人事流動與人事成本比例的提高，工作流程自動化能夠有效的降低成本和提高產能，這也是企業組織和政府單位所期望達成的目標。在工廠的製造流程中通常會經由一些工作流程和操作來生產一件產品，而這些工作流程和操作都會需要利用製造資源(包括人力和機器)來支援完成這項工作。因此在工作流程排程中，一項關鍵的問題是當工廠管理者接收到一份訂單時，必須要能夠確定這份訂單能夠在期限下利用可用的資源完成，並且滿足訂單需求。本篇論文的目標在於提出一個有效和有系統的方法，來解決在製造業中工作流程的排程問題。為了解決這個問題，我們的方法是基於時間派翠網路(Time Petri Net)建立工作流程與資源活動的模型，以及利用契約網協定(Contract Net Protocol)和多代理人系統(Multi-agent Systems, MAS)來達成工作流程與資源之間的協商。此外我們的工作流程排程演算法是結合最小成本流演算法(Minimum Cost Flow)、次梯度演算法(Subgradient algorithm)、啟發式演算法(Heuristic algorithm)和負載平衡(Load Balance)的概念來計算工作流程中每個操作所需要的資源，以及執行的時間區間和生產的數量。最後我們是運用Java代理人開發框架(Java Agent DEvelopment Framework, JADE)軟體平台來實現整個排程系統，並且利用流程圖和甘特圖的方式驗證排程結果。

Workflow automation can effectively reduce costs, increase productivity and achieve the goal of business organizations and government agencies. Usually it requires workflows and operations to manufacture a product in a factory. These workflows and operations will need to make use of manpower and machines to complete the production processes. The manpower and machines are resources in the manufacturing systems. In workflow scheduling, an important issue for order managers is to determine whether the requirements of an order can be met by the deadline using the available resources. The objectives of this paper are to propose an effective and systematic approach to solving workflow scheduling problems in manufacturing sector. To solve this problem, our approach is based on Timed Petri Net (TPN) to construct models of workflows and resource activities, and uses the Contract Net Protocol (CNP) as well as multi-agent systems (MAS) to achieve the negotiation between the workflow and resources. In addition, our workflow scheduling algorithm combines the minimum cost flow algorithm, subgradient algorithm, heuristic algorithm and the concept of load balance for the calculation of resources and time interval and the production quantity of each operation in workflow. Finally, we develop a multi-agent scheduling simulation software based on the Java Agent DEvelopment Framework (JADE) and use flow charts and Gantt charts to verify that the scheduling results.

中文摘要 I
Abstract II
致謝 III
目錄 V
表目錄 VIII
圖目錄 IX
第一章 簡介 1
1.1 研究背景與動機 1
1.2 研究目標與方法 7
1.3 論文架構 11
第二章 文獻回顧 13
2.1 製造規劃系統的演進 13
2.2 先進規劃排程系統 14
2.2.1 先進規劃排程系統簡介 14
2.2.2 先進規劃排程系統相關文獻探討 19
2.3 多代理人系統 21
2.3.1 代理人介紹 21
2.3.2 多代理人系統定義 24
2.3.3 多代理人系統在製造系統的應用 26
第三章 代理人協商機制 30
3.1 場景設計 30
3.2 契約網協定介紹 33
3.2 協商過程 35
3.2.1 工作流程代理人與資源代理人協商 38
3.2.2 上下游工作流程代理人協商 42
第四章 代理人工作流程與資源活動建模 48
4.1 時間派翠網路 48
4.1.1 時間派翠網路概述 48
4.1.2 時間派翠網路特性 49
4.1.3 派翠網路標記語言 52
4.2 工作流程建模 57
4.3 資源活動建模 60
第五章 排程演算法設計 63
5.1 最小成本流演算法 63
5.1.1 最小成本流問題 63
5.1.2 最小成本流排程演算法 66
5.1.3 最小成本流排程演算法遇到的問題 71
5.2 Lagrangian relaxation演算法 73
5.2.1 Lagrangian relaxation介紹 73
5.2.2 Lagrangian relaxation之理論推導 74
5.2.3 利用次梯度演算法修正Lagrangian乘數 77
5.2.4 收斂的判斷 78
5.3 啟發式演算法 78
5.4 負載平衡 81
5.5 總排程演算法流程 82
第六章 模擬與結果 84
6.1 JADE介紹 84
6.2 系統架構 88
6.3 模擬參數設定 89
6.4 模擬過程 93
6.5 模擬結果分析 100
第七章 結論 111
參考文獻 116
附錄 A 模擬參數 125

表目錄
表2.1 先進規劃排程系統各模式比較表[38] .............................................. 19
表3.1 代理人代表 ......................................................................................... 36
表3.2 上下游工作流程代理人協商範例 ..................................................... 43
表4.1 時間派翠網路數學定義表 ................................................................. 50
表4.2 時間派翠網路圖形定義表 ................................................................. 50
表4.3 PNML標籤屬性表[64] ....................................................................... 53
表4.4 時間派翠網路範例模型PNML文件 .................................................. 54
表5.1 成本網路流符號表 ............................................................................. 67
表6.1 訂單編號1排程結果 ....................................................................... 101
表6.2 訂單編號2排程結果 ....................................................................... 103
表6.3 訂單編號3排程結果 ....................................................................... 104
表A.1 訂單要求 ........................................................................................... 125
表A.2 工作流程代理人屬性 ....................................................................... 125
表A.3 Input和Output工作流程位置屬性 ................................................... 126
表A.4 資源代理人屬性 ............................................................................... 127
表A.5 手動投標的資源代理人空閒時間 ................................................... 127


圖目錄
圖2.1 管理資訊系統的演進[37] .................................................................. 13
圖2.2 同步規劃的先進規劃排程系統[38] .................................................. 16
圖2.3 先進規劃排程系統功能模組[43] ...................................................... 17
圖2.4 代理人與環境互動關係[50] .............................................................. 22
圖2.5 多代理人系統平台開發架構流程[57] .............................................. 25
圖2.6 代理人框架[1] .................................................................................... 27
圖3.1 工廠製造場景 ..................................................................................... 32
圖3.2 契約網協定-Call For Proposal ........................................................... 33
圖3.3 契約網協定-PROPOSE ...................................................................... 34
圖3.4 契約網協定-ACCEPT_PROPOSAL .................................................. 35
圖3.5 契約網協定-INFORM ........................................................................ 35
圖3.6 代理人協商架構圖 ............................................................................. 37
圖3.7 工作流程與資源協商順序圖-CFP .................................................... 38
圖3.8 工作流程與資源協商順序圖-PROPOSE .......................................... 39
圖3.9 工作流程與資源協商順序圖-最佳解要求與回應 ........................... 39
圖3.10 工作流程與資源協商順序圖-ACCEPT_PROPOSAL ..................... 40
圖3.11 工作流程與資源協商順序圖-INFORM ............................................ 41
圖3.12 工作流程樹範例 ................................................................................. 43
圖3.13 工作流程之間協商順序圖-提出訂單 ............................................... 43
圖3.14 工作流程之間協商順序圖-工作流程協商 ....................................... 46
圖3.15 工作流程之間協商順序圖-完成訂單 ............................................... 47
圖4.1 原始時間派翠網路圖 ......................................................................... 51
圖4.2 觸發後時間派翠網路圖 ..................................................................... 52
圖4.3 時間派翠網路範例模型圖 ................................................................. 54
圖4.4 工作流程模型範例圖 ......................................................................... 58
圖4.5 加入位置的工作流程模型範例圖 ..................................................... 59
圖4.6 資源活動模型範例圖-空閒狀態 ....................................................... 60
圖4.7 資源活動模型範例圖-忙碌狀態 ....................................................... 61
圖4.8 資源多個活動模型範例圖 ................................................................. 61
圖5.1 最小成本流範例 ................................................................................. 64
圖5.2 最小成本流範例最佳解 ..................................................................... 65
圖5.3 進貨流程範例原始網路圖 ................................................................. 68
圖5.4 進貨流程範例最佳解網路圖 ............................................................. 69
圖5.5 製造流程範例原始網路圖 ................................................................. 70
圖5.6 製造流程範例最佳解網路圖 ............................................................. 71
圖5.7 具有衝突問題的網路圖 ..................................................................... 72
圖5.8 未具有衝突問題的網路圖 ................................................................. 72
圖5.9 Lagrangian relaxation演算法結構...................................................... 76
圖5.10 啟發式演算法流程圖 ......................................................................... 80
圖5.11 總排程演算法流程圖 ......................................................................... 83
圖6.1 代理人管理參考模型[75] .................................................................. 85
圖6.2 JADE平台與容器架構圖[25] ............................................................ 86
圖6.3 JADE GUI視窗 ................................................................................... 87
圖6.4 排程系統架構圖 ................................................................................. 89
圖6.5 模擬範例工作流程關係 ..................................................................... 91
圖6.6 W1加入位置的工作流程模型 .......................................................... 91
圖6.7 R1加入位置的資源活動模型 ........................................................... 93
圖6.8 各類型代理人視窗 ............................................................................. 94
圖6.9 設定工作流程屬性視窗 ..................................................................... 95
圖6.10 設定資源屬性視窗 ............................................................................. 96
圖6.11 資源定位視窗 ..................................................................................... 96
圖6.12 資源代理人手動提出計畫視窗 ......................................................... 97
圖6.13 資源代理人手動建立契約視窗 ......................................................... 98
圖6.14 設定訂單要求視窗 ............................................................................. 98
圖6.15 訂單編號3處理流程 ......................................................................... 99
圖6.16 訂單編號1排程結果流程圖 ........................................................... 100
圖6.17 訂單編號2排程結果流程圖 ........................................................... 102
圖6.18 訂單編號3排程結果流程圖 ........................................................... 103
圖6.19 資源R1~R3甘特圖 .......................................................................... 105
圖6.20 資源R4~R8甘特圖 .......................................................................... 106
圖6.21 資源R9~R13甘特圖 ........................................................................ 107
圖6.23 訂單編號2生產流程模型 ............................................................... 109
圖6.24 訂單編號3生產流程模型 ............................................................... 110
圖A.1 模擬範例工作流程模型 ................................................................... 128
圖A.2 模擬範例資源活動模型 ................................................................... 129

[1]Kai-Ying Chen and Chun-Jay Chen, “Applying multi-agent technique in multi-section flexible manufacturing system,” Expert Systems with Applications, Nov. 2010, Vol. 37, Issue 11, pp. 7310-7318.
[2]Agility Forum, “Next generation manufacturing project: A framework for action,” Views of the future, 1997, Vol. 4.
[3]Y. Koren, U. Heisel, F. Jovane, T. Moriwaki, G. Pritschow, G. Ulsoy, H. Van Brussel, “Reconfigurable Manufacturing Systems,” CIRP Annals-Manufacturing Technology, 1999, Vol. 48, Issue 2, pp. 527-540.
[4]Wencai Wang and Yoram Koren, “Scalability planning for reconfigurable manufacturing systems,” Journal of Manufacturing Systems, April. 2012, Vol. 31, Issue 2, pp. 83-91.
[5]Young Hae Lee, Chan Seok Jeong, Chiung Moon, “Advanced planning and scheduling with outsourcing in manufacturing supply chain,” Computers & Industrial Engineering, July. 2002, Vol. 43, Issues 1-2, pp. 351-374.
[6]K.J. Chen, P. Ji, “A genetic algorithm for dynamic advanced planning and scheduling (DAPS) with a frozen interval,” Expert Systems with Applications, November. 2007, Vol. 33, Issue 4, pp. 1004-1010.
[7]Kejia Chen, Ping Ji, “A mixed integer programming model for advanced planning and scheduling (APS),” European Journal of Operational Research, August. 2007, Vol. 181, Issue 1, pp. 515-522.
[8]Giordano Lanzola, Luca Gatti, Sabina Falasconi, Mario Stefanelli, “A framework for building cooperative software agents in medical applications,” Artificial Intelligence in Medicine, July. 1999, Vol. 16, Issue 3, pp. 223-249.
[9]Jacques Ferber, Multi-agent systems: An introduction to distributed artificial intelligence, 1999.
[10]C. Y. Huang and S. Y. Nof, “Formation of autonomous agent networks for manufacturing systems,” International Journal of Production Research, 2000, Vol. 38, No. 3, pp. 607-624.
[11]Fu-Shiung Hsieh, “Design of reconfiguration mechanism for holonic manufacturing systems based on formal models,” Engineering Applications of Artificial Intelligence, October. 2010, Vol. 23, Issue 7, pp. 1187-1199.
[12]Fu-Shiung Hsieh, “Developing cooperation mechanism for multi-agent systems with Petri nets,” Engineering Applications of Artificial Intelligence, June. 2009, Vol. 22, Issues 4-5, pp.616-627.
[13]Fu-Shiung Hsieh, “Dynamic composition of holonic processes to satisfy timing constraints with minimal costs,” Engineering Applications of Artificial Intelligence, October. 2009, Vol. 22, Issue 7, pp.1117-1126.
[14]T. N. Wong, C. W. Leung, K. L. Mak, R. Y. K. Fung, “Dynamic shopfloor scheduling in multi-agent manufacturing systems,” Expert Systems with Applications, October. 2006, Vol. 31, Issue 3, pp. 486-494.
[15]Rizvan Erol, Cenk Sahin, Adil Baykasoglu and Vahit Kapiznoglu, “A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems,” Applied Soft Computing, June. 2012, Vol. 13, Issue 6, pp. 1720-1732.
[16]Qing-lin Guo, Ming Zhang, “An-agent-oriented approach to resolve scheduling optimization in intelligent manufacturing,” Robotics and Computer-Integrated Manufacturing, February. 2010, Vol. 26, Issue 1, pp. 39-45.
[17]R. G. Smith, “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver,” IEEE Transactions On Computers, December. 1980, Vol. 29, No. 12, pp. 1104-1113.
[18]Fu-Shiung Hsieh and Chih Yi Chiang, “Collaborative composition of processes in holonic manufacturing systems,” Computers in Industry, January. 2011, Vol. 62, Issue 1, pp. 51-64.
[19]Workflow Management Coalition, “XPDL support and resources,” 2009, http://www.wfmc.org/xpdl.html.
[20]Object Management Group, “Business process modeling notation,” 2009, http://www.bpmn.org.
[21]OASIS, “Web services business process execution language version 2.0,” 2009, http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html.
[22]Dongsheng Liu, Jianmin Wang, Stephen C. F. Chan, Jiaguang Sun, Li Zhang, “Modeling Workflow processes with colored Petri nets,” Computers in Industry, December. 2002, Vol. 49, Issue 3, pp. 267-281.
[23]Fu-Shiung Hsieh, “Robustness analysis of Petri nets for complex processes,” Proceedings of the Thirty-Seventh Southeastern Symposium on System Theory, March. 2005, No.20-22, pp.2049-2054.
[24]Fu-Shiung Hsieh, “Robustness Analysis of a Class of Non-ordinary Controlled Petri Nets,” Proceedings of the 2006 IEEE International Conference on System, 2006, No. 8-11, pp. 2068-3073.
[25]Telecom Italia Lab, “Java Agent DEvelopment Framework,” 2011, http://jade.tilab.com.
[26]陳善鈺，以Petri net模型為基礎之協同合作分散式問題解決方法，碩士論文，朝陽科技大學資訊工程系，臺中，2008。
[27]江致宜，多代理人系統之工作程序動態合成，碩士論文，朝陽科技大學資訊工程系，臺中，2009。
[28]M.K. Lim and Z. Zhang, “A multi-agent system using iterative bidding mechanism to enhance manufacturing agility,” Expert Systems with Applications, July. 2012, Vol. 39, Issue 9, pp. 8259-8273.
[29]Fu-Shiung Hsieh, “Holarchy formation and optimization in holonic manufacturing systems with contract net,” Automatica, April. 2008, Vol. 44, Issue 4, pp. 959-970.
[30]Fu-Shiung Hsieh, “Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets,” Automatica, January. 2004, Vol. 40, Issue 1, pp. 51-57.
[31]Fu-Shiung Hsieh, “Analysis of contract net in multi-agent systems,” Automatica, May. 2006, Vol. 42, Issue 5, pp. 733-740.
[32]楊毓興，多代理人系統之工作流程合成、執行與監督，碩士論文，朝陽科技大學，資訊工程系，臺中，2011。
[33]Xinyu Li, Chaoyong Zhang, Liang Gao, Weidong Li, Xinyu Shao, “An agent-based approach for integrated process planning and scheduling,” Expert Systems with Applications, March. 2010, Vol. 37, Issue 2, pp. 1256-1264.
[34]C. W. Leung, T. N. Wong, K. L. Mak, R. Y. K. Fung, “Integrated process planning and scheduling by an agent-based ant colony optimization,” Computers & Industrial Engineering, August. 2010, Vol. 59, Issue 1, pp. 166-180.

[35]IEEE Foundation for Intelligent Physical Agents, “The Foundation for Intelligent Physical Agents”, 2012, http://www.fipa.org/.
[36]鄧雅元，先進生產規劃與排程系統分析，碩士論文，國立台灣大學，工業工程學研究所，臺北，1999。
[37]張嘉盈、賈維褣、秦志榮、周立笙、曾華瑩，「建構先進規劃排程系統(APS)強化企業資源規劃(ERP)」，輔仁大學企業管理學系第三十五屆生管專題報告，2001。
[38]王立志，系統化運籌與供應鏈管理-企業營運新典範，滄海書局，2006。
[39]盧舜年、鄒坤霖，供應鏈管理的第一本書，商周出版，2002。
[40]Hans-Henrik Hvolby, Kenn Steger-Jensen, “Technical and industrial issues of Advanced Planning and Scheduling (APS) systems,” Computers in Industry, December. 2010, Vol. 61, Issue 9, pp. 845-851.
[41]鼎新電腦，淺談運籌/供應鏈管理核心-先進規劃與排程系統(APS)觀念篇，http://www.dsc.com.tw/newspaper/47/47-1.htm.
[42]鼎新電腦，製造業管理新紀元-應用先進生產規劃與排程系統提升企業競爭優勢，http://www.dsc.com.tw/newspaper/43/43-1.htm.
[43]蘇雄義、陳培光、黃明顯，供應鏈經營管理，智勝文化事業有限公司，2005。
[44]朱思頻，從訂單差異性觀點建立供應鏈管理之先進規劃流程管理，碩士論文，國立屏東科技大學，工業管理系所，屏東，2002。
[45]陳明達，與先進規劃流程系統整合之作業基礎制成本分析，碩士論文，國立雲林科技大學，工業工程與管理研究所，雲林，2003。
[46]Junyu Yang, Wencheng Tang, “Hybrid Genetic Algorithm for Advanced Planning and Scheduling,” International Conference on Electrical and Control Engineering, June. 2010, pp. 1138-1141.
[47]Chiung Moon, Yoonho Seo, “Evolutionary algorithm for advanced process planning and scheduling in multi-plant,” Computers & Industrial Engineering, March. 2005, Vol. 48, Issue 2, pp. 311-325.
[48]S. H. Chung, H.C. Lau, K. L. Choy, G. T. S. Ho, Y. K. Tse, “Application of genetic approach for advanced planning in multi-factory environment,” International Journal of Production Economics, October. 2010, Vol. 127, Issue 2, pp. 300-308.
[49]郭哲良，自動化產業先進規劃排程系統之製造成本分析與管理-以TFT-LCD產業為例，碩士論文，國立雲林科技大學，工業工程與管理研究所，雲林，2005。
[50]Gerhard Weiss, Multiagent Systems A Modern Approach to Distributed Modern Approach to Artificial Intelligence, Massachusetts Institute of Technology, 1999.
[51]A. Moreno, C. Garbay, “Software agents in health care,” Artificial Intelligence in Medicine, March. 2003, Vol. 27, Issue 3, pp. 229-232.



[52]Zakaria Maamar, Quan Z. Sheng, Boualem Benatallah, Ghazi AI-Khatib, “A three-level specification approach for an environment of software agents and Web services, ” Electronic Commerce Research and Applications, Autumn. 2004, Vol. 3, Issue 3, pp. 214-231.
[53]Zakaria Maamar, “Association of users with software agents in e-commerce,” Electronic Commerce Research and Applications, Spring. 2002, Vol. 1, Issue 1, pp. 104-112.
[54]李乘帆，以多代理人為基礎建立非相關平行機台之流程生產控制系統，碩士論文，國立屏東科技大學，工業管理系，屏東，2007。
[55]Deyuan Meng, Yingmin Jia, Junping Du, Fashan Yu, “Tracking control over a finite interval for multi-agent systems with a time-varying reference trajectory,” Systems & Control Letters, July. 2012, Vol. 61, Issue 7, pp. 807-818.
[56]T. Vengattaraman, S. Abiramy, P. Dhavacheelvan, R. Baskaran, “An application perspective evaluation of multi-agent system in versatile environments,” Expert Systems with Application, March. 2011, Vol. 38, Issue 3, pp. 1405-1416.
[57]Sooyong Park, Vijayan Sugumaran, “Designing multi-agent systems: a framework and application,” Expert System with Applications, February. 2005, Vol. 25, Issue 2, pp. 259-271.
[58]林坤正，智慧型多重代理人建構電子市集中之自動協商機制，碩士論文，朝陽科技大學，工業工程與管理系，臺中，2003。
[59]C. A. Petri, “Communication mitt Automation” PhD thesis instituted for instrumentally Mathematics, 1962.
[60]T. Murata, “Petri Nets: Properties, Analysis and Applications,” Proceedings of the IEEE, 1989, Vol. 77, No. 4, pp. 541-580.
[61]Hehua Zhang and Ming Gu, “Modeling job shop scheduling with batches and setup times by timed Petri nets,” Mathematical and Computer Modelling, January. 2009, Vol. 49, Issues 1-2, pp. 286-294.
[62]Yin-Hsuan Lee, Chuei-Tin Chang, David Shan-Hill Wong, Shi-Shang Jang, “Petri-net based scheduling strategy for semiconductor manufacturing processes,” Chemical Engineering Research and Design, March. 2011, Vol. 89, Issue 3, pp. 291-300.
[63]M. Jüngel, E. Kindler, M. Weber, “The Petri Net Markup Language,” Petri Net Newsletter, 2000, No. 59, pp. 24-29.
[64]M. Weber, E. Kindler, “The Petri Net Markup Language,” 2002, http://www2.informatik.hu-berlin.de/top/pnml/download/about/PNML_LNCS.pdf.
[65]WinPeSim, “HPSim”, http://www.winpesim.de/index.html.
[66]P. Bonet, C. M. Llado, R. Puijaner, W. J. Knottenbelt, “PIPE V2.5: A Petri Net Tool for Performance Modeling,” Proc. 23rd Latin American Conference on Informatics (CLEI 2007), October. 2007.
[67]Workflow Petri Net Designer, “WoPeD”, 2011, http://www.woped.org/.
[68]IBM ILOG CPLEX Optimization Studio, http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studio/.
[69]Marshall L. Fisher, Kurt O. Jörnsten, Oli B. G. Madsen, “Vehicle Routing with Time Windows: Two Optimization Algorithms,” Operations Research, May-Jun. 1997, Vol. 45, No. 3, pp. 488-492.
[70]Fu-Shiung Hsieh, “Combinatorial reverse auction based on revelation of Lagrangian multipliers,” Decision Support Systems, January. 2010, Vol. 48, Issue 2, pp. 323-330.
[71]Lixin Tang, Hua Xuan, Jiuin Liu, “A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time,” Computers & Operations Research, November. 2006, Vol. 33, Issue 11, pp.3344-3359.
[72]Shi-Chung Chang, Da-Yin Liao, “Scheduling Flexible Flow Shops with No Setup Effects,” IEEE TRANSATIONS ON ROBOTICS AND AUTOMATION, April. 1994, Vol. 10, No. 2, pp. 112-122.
[73]Zhongzhi Shi, Haijun Zhang, Yong Cheng, Yuncheng Jiang, Qiujian Sheng, Zhikung Zhao, “MAGE: an agent-oriented software engineering environment,” Cognitive Informatics, 2004. Proceedings of the Third IEEE International Conference, Aug. 2004, pp. 250-257.
[74]Kenichi Yoshimura, “FIPA JACK A Plugin for JACK Intelligent Agents,” September. 2003.
[75]F. Bellifemine, A. Poggi, G. Rimassa, “Developing multi-agent systems with JADE,” Intelligent agents, Springer-Verlag, 2001.