摘要
我国“以信息化带动工业化、以工业化促进信息化”战略的提出,使得计算机技术越来越广泛的应用于现代的生产制造领域。在传统的制造业中,企业间存在着信息孤岛,制造资源利用不合理,制造成本高昂,制造流程管理混乱等特点。随着网格技术与工作流技术的发展,将网格工作流技术引入制造领域有着非常重要的意义。它使企业,行业间实现信息共享,透明的使用全球分布的制造资源,利用工作流管理技术实现制造流程完全或部分的自动化管理,以减少成本,提高效率。
在经济全球化的大背景下,各种不同服务类型,不同服务质量(QoS)的制造资源遍布各国各个地区以及各个行业,从而形成了巨大的制造网格资源。如何使用计算机网格工作流技术实现制造流程自动化管理,制造任务调度以及网格资源匹配,以生成达到降低生产成本,提高服务质量,合理利用资源等目的的生产方案,是本文的主要研究内容。本文将对制造流程建模,网格工作流任务调度算法以及网格工作流调度系统等方面进行研究。主要的研究内容和创新有:
1)利用有向无环图(DAG)进行制造流程建模。用DAG描述制造流程的任务之间的执行先后顺序,同时为DAG增加截止期限约束。
2)针对现行的网格工作流任务调度算法,提出一种改进的满足截止期限QoS要求的调度算法—基于任务分割的TP资源匹配任务调度算法。TP算法能确保在截止期限内完成工作流的所有任务,并且在执行成本上比现行算法更优。
3)构建网格工作流调度系统的系统原型。该系统原型实现基本的工作流功能,实现制造流程的自动化执行管理,调度模块实现了TP调度算法与D-MDP调度算法。
4)利用网格工作流调度系统与网格模拟平台GridSim对调度算法行实验模拟,实验表明TP算法的执行成本性能较优。
The strategy of "Information Technology Gives an Impetus to Industrialization and Industrialization Promotes Information Technology" proposed in our country enables computer technology more and more widely used in modern manufacturing. Traditional manufacturing has characteristics of information silo between enterprises, irrational use of manufacturing resources, higher manufacturing cost and confusion of the management of manufacturing processes. As the development of grid and workflow technology, the introduction of grid workflow technology in manufacturing is significant. It enables enterprises share information, use the global resources transparently, effectively and automatically manager the manufacturing workflow, in order to reach the goal of cutting cost and improving efficiency.
In the background of economic globalization, different service types, different level of quality of service (QoS) of manufacturing resources distribute in various regions all over the country and all sectors, forming the tremendous manufacturing grid resources. How to realize automatic management of workflow, tasks scheduling and grid resources allocation with the grid workflow technology, and further create a optimal production plan which meets the requirement of cutting cost, improving the level of QoS and rational use of resources, is highly discussed in our paper.
The research of our paper mainly focuses on manufacturing workflow modeling, grid workflow scheduling algorithm and the grid workflow schedule system prototype. The main work and creation are as following:
1) Utilize DAG to model the processes of manufacturing tasks, and add deadline constrain property to DAG.
2) Propose a QoS-constrained workflow scheduling algorithm—TP(Task Partition) algorithm. TP meets the deadline of the workflow while paying less than the current scheduling algorithm.
3) Construct grid workflow schedule system prototype. The system implements basic functions, TP and D-MDP algorithm.
4) Combine the grid workflow schedule system with grid simulation platform GridSim to test our TP algorithm. The experiment results show that the improved TP algorithm costs less than D-MDP, thus, have better performance on cost.
引文
[1] The Globus Alliance. http://www.globus.org
[2] University of Virginia, Legion 1.8 System Administrator Manual, http://legion.virginia.edu, 2001
[3] The DataGrid Project http://eu-datagrid.web.cern.ch
[4] ApGrid Home Page. http://www.apgrid.org/
[5] R. Buyya, D, Abramson, and J. Giddy. Nimrod/G: An Architecture of a Resource Management and Scheduling System in a Global Computational Grid[C], HPC Asia 2000, Beijing, China, IEEE CS Press, Los Alamitos, CA, USA, May 14-17, 2000; 283-289
[6] Li Zha, Wei Li,Haiyan Yu,Xianghui Xie,Nong Xiao,Zhiwei Xu,System Software for China National Grid , proceedings of Network and Parallel Computing ,Springer-verlag,Berlin,2005,14-21
[7] Hai Jin,Grid Computing and ChinaGarid Project,Proceedings,2005 International Conference on Parallel Proceeding Workshops,2005,81-81
[8] NSFC网格,http://www.nscfnet.net
[9] Minglu Li,Hui Liu,Changjun Jinag,Weiqin Tong,Aoying Zhou,Yangdong Gui Hao Zhu,Shui Jinag,Ruonan Rao,Jina Cao,Qinni Deng,Qi Qian,Wei Jin,ShanghaiGrid in Action:The Fisrt Satge Porjects Towards Digital City and City Grid,Grid and Cooperative Computing, Pt 1, M. Li, et al., Editors, Springer-verlag, Berlin, 2004, 616-623.
[10] Information Power Grid,2003 .http://www.nasa.gov/IPG/doc
[11] T. Savolainen, D. Beeckmann,P. Groumpos and H. Jagdev. Positioning of modeling approaches, methods and tools[J]. Computers in Industry ,1995,25(3): 255– 262
[12] Chen D.,Doumeingts G.,Vallespir B..GRAI intergrated methodology and its mapping onto generic enterprise reference architecture and methodology[J].Computer-in-Industry.1997,33(2,3):387-394
[13] Gary Tan,Na Zhao,Simon J E Taylor.Automobile manufacturing supply chain simulation in the grids environment[C].Proceeding of the 2003 Winter Simulation Conference,Dec 7-10,New Orleans,LA,United States,2003:1149-1157
[14]科研成果成果介绍先进制造网格平台.先进制造网格平台AmGrid. http:// vega.ict.ac.cn/amgridproject.jsp?id=dir327,2009
[15]颜波,黄必清,郑力,等.网格研究现状及其在制造业中的应用[J].计算机集成制造系统,2004,10(9):1021-1030
[16]张传顺,莫蓉,石胜友等.基于遗传算法的制造网格资源调度方法研究[J].中国机械工程.2006,18(17):1916~1919
[17]和延立,杨海成,何卫平,等.基于网格原理的跨企业协同制造平台[J].计算机集成制造系统,2005,11(5):636-641
[18]陈庆新;田文生;陈新等.特许连锁模式下的模具制造网格系统架构[J].计算机集成制造系统-CIMS[J].2003,7(9):595~600.
[19]刘丽兰;俞涛;施战备;方明伦.快速制造网格及其服务结点的建设[J].机械设计与研究.2003,5(19):57~59
[20] Buyya R, Abrams on D, Giddy J . Nimrod /G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C]. Beijing: Proceedings of the 4th International Conference on High Performance Computing in Asia-Pacific Reginon, 2000. 283228
[21] Cao J, Jarvis S A , Saini S, et al.GridFlow:Workflow Management for Grid Computing [C]. In 3rd International Symposium on Cluster Computing and the Grid (CC-Grid), Tokyo, Japan, IEEE Computer Society Press, Los Alamitos,2003:12-15
[22] Tannenbaum T, Foster I, Livny M, et al. Condor-G: A Computational Management Agent for Multi-Institutional Grids [J]. Cluster Computing, 2002, 5 (3) : 2372246
[23] Spring N, Wolski R. Application Level Scheduling of Gene Sequence Comparison on Metacomputers [C]. Melbourne: the 12th ACM Int’1 Conf . on Super computing, 1998. 1412 14
[24] Falk Neubauer, Andreas Hoheisel, Joachim Geiler. Workflow-based Grid applications[J].Future Generation Computer Systems,2006,22(1-2):6-15
[25] Han Yu, Xin Bai, Dan C.Marinescu. Workflow management and resource discovery for an intelligent grid[J].Parallel Computing,2005,31(7):797-811
[26] Junwei Cao, Daniel P Spoorner, James D Turner, et al. ARMS: An Agent-based Resource Management for Grid Computing[J].Scientific Programming,2002,10(2):135-148
[27] Yu, J., Buyya, R., Tham, C.K.: A Cost-based Scheduling of Scienti?c Work?ow Applications on Utility Grids. In: The ?rst IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, December 5-8 (2005)
[28] Mohan C. Recent t rends in workflow management products, standards, and research.1997.http://www.almaden.ibm.com/cs/exotica/ wfnato97 .ps
[29] Alonso G, AgrawalD, Abbadi E A et al . Functionality and limitations of current workflow management systems.1997.http:// www. almaden.ibm.com/cs/ exotica/ wfmsys.ps
[30] RusinkiewiczM, Sheth A. Specification and execution of transactional workflows. In Won Kimed. Modern Database Systems: The Object Model, Interoperability, and Beyond Reading, MA: Addison Wesley Publishing Company, 1995
[31] Vander A alstW M P. Three good reasons for using a Petri-net-based workflow management system. In: Navathe S,W kayama Teds . Proceedings of the International Working Conference on Information and Process Integration in Enterprises( IP IC’96). Cambridge, MA: Kluwer Academic Publishers, 1996 . 179～20
[32]罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000.11(7):899-905
[33]王利霞.工作流技术在web平台办公系统中的研究与应用.2008.
[34]范玉顺.工作流管理技术基础.北京:清华大学出版社,2001年4月.
[35]张维明,邓苏,罗雪山等.信息系统建模技术与应用[M].电子工业出版社,1997
[36] B.Scholz-Reiter, E.Stichel. Business process modeling [M]. Berlin: Springer-Verlag , 1996.PaulMessina,Meta Computing and Data-Intensive Applications,Proeeedings of the International Conference on World wide Computing and Its Applications,Mareh1997
[37]王霓虹,滕志霞.网格技术研究与发展趋势综述[J].信息技术.2007,2:117-120
[38]饵雪.基于QoS的网格任务调度模型与算法研究[D].东北大学.2006:1-59
[39]王霜,基于关键路径的网格任务调度算法研究.合肥工业大学.2009
[40]栾翠菊.计算网格环境中任务管理的研究.浙江大学.2006
[41]张绍华.网格工作流关键技术研究.复旦大学.2004
[42] Ullman, J.D.: NP-complete Scheduling Problems. Journal of Computer and System Sciences 10, 384–393 (1975)
[43] Wang Y,Saksena M. Scheduling fixed priority tasks with preemption threshold[J]. In:Proceedings, IEEE International Conference on Real-Time Computing Systems and Applications(December 1999)
[44] YU Jia, BUYYA R. A taxonomy of workflow management systems for grid computing [J]. Journal of Grid Computing, 2006, 3 (324) :1712200
[45]李超,朱巧明,李培峰,等.一个网格服务工作流的动态调度算法[ J ].计算机应用研究, 2008, 25 (11) : 32852328
[46]苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法[ J ].计算机学报, 2008, 31 (2) : 2822290
[47] YUAN Ying-chun, LI Xian-song, SUN Chen-xia . Cost-effective heuristics for workflow scheduling in grid computing economy[C] Proc of the 6th International Conference on Grid and Cooperative Computing . 2007: 322232
[48]张艳,李楠.一个市场驱动的QoS网格工作流任务调度算法[ J ].计算机应用与软件, 2008, 25 (4) : 1622164
[49]倪晚成,刘连臣,吴澄.网格工作流中基于商品市场的服务选择[ J ].计算机应用, 2007, 27 (12) : 297322975
[50] KYRIAZIS D, TSERPES K, MENYCHT AS A, et al. An innovative workflow mapping mechanism for grids in the frame of quality of service [J]. Future Generation Computer Systems, 2008, 24 (6) : 498251
[51]田国忠,于炯,侯勇,等.基于资源状态可靠度的网格工作流调度算法[J].计算机工程与应用, 2008, 44 (18) : 1152118
[52] Wieczorek, M., Prodan, R., Fahringer, T. : Scheduling of Scientific Workflows in the ASKALON Grid Environment. ACM SIGMOD Record 34(3), 56 62 (2005)
[53] He, X., Sun, X., von Laszewski, G.: QoS Guided Min-Min Heuristic for Grid Task Scheduling. Journal of Computer Science and Technology 18(4), 442 451 (2003)
[54] Braun, T.D., Siegel, H.J., Beck, N.: A Comparison of Eleven static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing 61, 801-837 (2001)
[55] Maheswaran, M., et al.: Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems. In: The 8th Heterogeneous Computing Workshop (HCW 1999), San Juan, Puerto Rico, April 12 (1999)
[56] Topcuoglu,H., Hariri,S., Wu,M.Y.: Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems 13(3), 260 274 (2002)
[57] Feo, T.A., Resende, M.G.C.: Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6, 109 133 (1995)
[58] Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
[59] Metropolis, N., et al.: Equations of state calculations by fast computing machines. Journal of Chemistry and Physics 21, 1087 1091 (1953)
[60] Menasc` e, D.A., Casalicchio, E.: A Framework for Resource Allocation in Grid Computing. In: The 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS 2004), Volendam, The Netherlands, October 5-7 (2004)
[61] Tsiakkouri, E., et al.: Scheduling Work?ows with Budget Constraints. In: Gor-latch, S., Danelutto, M. (eds.) The Core GRID Workshop on Integrated research in Grid Computing, Technical Report TR-05-22, University of Pisa, Department of Information, Pisa, Italy, November 28-30, pp. 347–357 (2005)
[62] WIECZOREK M, HOHEISEL A, PRODAN R. Towards a general model of themulti-criteria workflow scheduling on the grid [J]. Future Generation Computer Systems, 2009, 25 (3) : 2372256
[63]李金忠,夏洁武,曾劲涛,朱兵,刘昌鑫.网格工作流调度算法研究综述,计算机应用研究.2009.8
[64] R. Buyya and M. Murshed,―GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing‖, Concurrency and Computation: Practice and Experience, Vol. 14(13-15):1175-1220, Wiley Press, USA, 2002.
[65] Anthony Sulistio,Uros Cibej,Srikumar VenugoPal,Borut Robic and Rajkumar Buyya. A Toolkit for Modeling and Simulating DataGrids: An Extension to Gridsim[ J].Concurrency and Computation: Practice and Experience(CCPE),2008,20,1591-1609