网格工作流环境下多关键资源的任务调度策略研究
|
摘要
目前,我国大部分地区政府部门的电子政务建设,对外信息化的交流仅处于信息发布基础平台建设阶段。孤立封闭的系统架构,致使信息资源不能共享,数据格式不统一,数据在不同的系统中重复存在,互相不一致,也致使本该协同一致的完整业务过程被人为分割和打碎。这些问题阻碍了政府协同、监管工作效率和公共服务水平的提高,已成为制约中国电子政务发展的瓶颈。
网格技术的出现,为解决这些问题带来了契机,因为网格技术的核心就是信息和资源的共享及协同。但单纯的网格系统还缺乏一种有效地构建和处理具有关联的复杂网格应用的方法,由于工作流技术能够使过程自动化和协同工作,提高工作效率,自然让人联想网格与工作流技术的结合,从而网格工作流这一概念被提出。由于目前已有的网格工作流系统大多是根据高能物理或者生物信息学等专用网格系统中的工作流程复用等需求而设计的,它们更偏重于工作流程建模,而且其用户群体较为单纯,所以很少考虑任务调度方面的问题,相应的调度策略也没有优先性。对于用户群体比较复杂的电子政务网格工作流系统而言,由于资源的有限性,用户提交的任务则需要一定的机制来保证其能在合理的时间内完成。
本文首先从网格开始,着重介绍了网格资源管理与任务调度,并指出任务调度策略是影响网格系统效率的最重要因素,在此基础上结合传统工作流,指出研究网格工作流的必要性,并对网格工作流以及基于网格工作流的电子政务的关键内容进行介绍;接着对比了几种工作流过程建模方法,经过分析后选用Petri网对一个电子政务中常见的行政审批业务的例子建立网格工作流网,并通过对该网格工作流网的分析,得出关键部门误工数最少的次序调度对基于网格工作流的电子政务系统的巨大影响;接着结合排序论中误工数最小问题的算法,抽象出数学模型,并结合实际运用中出现的问题给出算法的改进;接着在单个关键资源的任务调度基础之上,建立一个把整体工期划分到各个阶段工期的动态规划模型,讨论多个关键资源的任务调度算法,并讨论了相关算法的时间复杂度,利用逐次近似法降低复杂度,得到一个在多项式时间内可解的动态规划算法;最后利用JAVA实现一个利用该算法与先进先执行算法比较的仿真系统,通过多次运算得到仿真的结果,证实了本文提出的算法确实可以减少总误工数。
Nowadays, the establishment of e-government and informative contact among most districts in our country are merely at the foundational stage of the release of information. Isolated system enclosure block the share of informative resources, in addition, the disintegrated of date formats and the re-existed date in different systems separate the whole normal business, which should be integrate together, into different parts. These problems, interfering the governmental co-ordination, the work efficiency of supervision and the improvement of public service, restrain the development of the Chinese e-government.
The emergence of grid technology provides an excellent opportunity for solving these problems, as the core of grid is the integration of information and resources. Due to the workflow technology makes the process automatic and integrated, and improves work efficiency, spontaneously let us associate with the integration of grid and workflow technology. Therefore, the concept of grid-workflow comes out.Nevertheless, most of the existing grid-workflow system at present is designed for the demands of workflow multiplexing, based on the peculiar grid system of high-energy physics and bioinformatics. Not only are they heavy on workflow modeling, but also rarely considering task scheduling as the simplified user group, consequently there is no priority on relative scheduling strategy. For e-government grid-workflow system which has more complicated user group, resources limiting, the tasks submitted by the user group need some mechanisms to make sure that they must be finished within a reasonable period of time.
This paper begins with grid, introduces grid-resource management and task scheduling, and indicates that the strategy of task scheduling is the key factor influencing the efficiency of grid system. On this basis, connecting with traditional workflow, it points out the necessity of studying grid-workflow, thus makes a brief introduction of grid-workflow and e-government model based on the grid-workflow. Secondly, after comparing and analyzing several modeling means of workflow, it adopts Petri Net to build grid-workflow net for the average case of administrative procedures for examination and approval in e-government. Through this case, it helps to analyze the function of order scheduling that has the minimum loss of work time in key department, which is based on e-government system of grid-workflow. Thirdly, linking up the algorithm of minimum loss of work time in the theory of scheduling, it abstracts mathematical model, and improves the algorithm under the practical conditions. On a single key-resource task scheduling matters, it establishes a dynamic program dividing the whole due date into several stages, discusses task scheduling algorithm of many key resources and time complexity of relative algorithm, later it utilizes successive approximation to simply the complexity in order to get a dynamic programming algorithm in polynomial time. Last but not the least, it takes advantage of JAVA to realize a emulating system comparing this algorithm and First in First executed algorithm. After many operations, it get a emulated result eventually, which approves that algorithm concerned by this paper helps eliminating the loss of working time.
网格技术的出现,为解决这些问题带来了契机,因为网格技术的核心就是信息和资源的共享及协同。但单纯的网格系统还缺乏一种有效地构建和处理具有关联的复杂网格应用的方法,由于工作流技术能够使过程自动化和协同工作,提高工作效率,自然让人联想网格与工作流技术的结合,从而网格工作流这一概念被提出。由于目前已有的网格工作流系统大多是根据高能物理或者生物信息学等专用网格系统中的工作流程复用等需求而设计的,它们更偏重于工作流程建模,而且其用户群体较为单纯,所以很少考虑任务调度方面的问题,相应的调度策略也没有优先性。对于用户群体比较复杂的电子政务网格工作流系统而言,由于资源的有限性,用户提交的任务则需要一定的机制来保证其能在合理的时间内完成。
本文首先从网格开始,着重介绍了网格资源管理与任务调度,并指出任务调度策略是影响网格系统效率的最重要因素,在此基础上结合传统工作流,指出研究网格工作流的必要性,并对网格工作流以及基于网格工作流的电子政务的关键内容进行介绍;接着对比了几种工作流过程建模方法,经过分析后选用Petri网对一个电子政务中常见的行政审批业务的例子建立网格工作流网,并通过对该网格工作流网的分析,得出关键部门误工数最少的次序调度对基于网格工作流的电子政务系统的巨大影响;接着结合排序论中误工数最小问题的算法,抽象出数学模型,并结合实际运用中出现的问题给出算法的改进;接着在单个关键资源的任务调度基础之上,建立一个把整体工期划分到各个阶段工期的动态规划模型,讨论多个关键资源的任务调度算法,并讨论了相关算法的时间复杂度,利用逐次近似法降低复杂度,得到一个在多项式时间内可解的动态规划算法;最后利用JAVA实现一个利用该算法与先进先执行算法比较的仿真系统,通过多次运算得到仿真的结果,证实了本文提出的算法确实可以减少总误工数。
Nowadays, the establishment of e-government and informative contact among most districts in our country are merely at the foundational stage of the release of information. Isolated system enclosure block the share of informative resources, in addition, the disintegrated of date formats and the re-existed date in different systems separate the whole normal business, which should be integrate together, into different parts. These problems, interfering the governmental co-ordination, the work efficiency of supervision and the improvement of public service, restrain the development of the Chinese e-government.
The emergence of grid technology provides an excellent opportunity for solving these problems, as the core of grid is the integration of information and resources. Due to the workflow technology makes the process automatic and integrated, and improves work efficiency, spontaneously let us associate with the integration of grid and workflow technology. Therefore, the concept of grid-workflow comes out.Nevertheless, most of the existing grid-workflow system at present is designed for the demands of workflow multiplexing, based on the peculiar grid system of high-energy physics and bioinformatics. Not only are they heavy on workflow modeling, but also rarely considering task scheduling as the simplified user group, consequently there is no priority on relative scheduling strategy. For e-government grid-workflow system which has more complicated user group, resources limiting, the tasks submitted by the user group need some mechanisms to make sure that they must be finished within a reasonable period of time.
This paper begins with grid, introduces grid-resource management and task scheduling, and indicates that the strategy of task scheduling is the key factor influencing the efficiency of grid system. On this basis, connecting with traditional workflow, it points out the necessity of studying grid-workflow, thus makes a brief introduction of grid-workflow and e-government model based on the grid-workflow. Secondly, after comparing and analyzing several modeling means of workflow, it adopts Petri Net to build grid-workflow net for the average case of administrative procedures for examination and approval in e-government. Through this case, it helps to analyze the function of order scheduling that has the minimum loss of work time in key department, which is based on e-government system of grid-workflow. Thirdly, linking up the algorithm of minimum loss of work time in the theory of scheduling, it abstracts mathematical model, and improves the algorithm under the practical conditions. On a single key-resource task scheduling matters, it establishes a dynamic program dividing the whole due date into several stages, discusses task scheduling algorithm of many key resources and time complexity of relative algorithm, later it utilizes successive approximation to simply the complexity in order to get a dynamic programming algorithm in polynomial time. Last but not the least, it takes advantage of JAVA to realize a emulating system comparing this algorithm and First in First executed algorithm. After many operations, it get a emulated result eventually, which approves that algorithm concerned by this paper helps eliminating the loss of working time.
引文
[1]武汉市电子政务生产力促进中心.城市电子政务软件平台技术与系统设计[M].湖北:武汉大学出版社.2003 25-32
[2]Quinn Snell Kevin Tew.An enterprise-based grid resource management system [C]Edinburgh Scotland Proceedings of the Tenth IEEE International Symposium on High Performance Distributed Computing(HPDC-11).2002.83-87
[3]Jerry Rolia.Jim Pruyne.Grids for enterprise applications[C].Seattle:Proceedings of the 9 Workshop on Job Scheduling Strategies for Parallel Programs.2003.129-147.
[4]张绍华.网格工作流关键技术研究:(博士论文)复旦大学.2004.6
[5]Globus.http://www.globus.org/
[6]Condor Team.http://www.cs.wisc.edu/condor/
[7]WSRF.http://www.globus.org/wsrf/
[8]Arkin A.et al.Business Process Modeling language(BPMI)2002
[9]Krishnan S.Wagstrom P.von Laszewski G.GSFL;A Workflow Framework for Grid Services.ANL/MGS-P980-0802.Argonne.2002
[10]Graham G E.Evans D.Bertram I.Mc Runjob;A High Energy Physics Workflow Planner for Grid.Computing in High Energy and Nuclear Physics.La Jolla.California.March 2003
[11]Grid Ant.http://www.gridworkflow.org/snips/gridworkflow/space/GridAnt
[12]Cvon Laszewski.M.Hategan.;Java CoGKit Karajan/CridAnt Work-flow Guide.Technical Report.Argonne National Laboratory.Argonne.IL.USA.2005
[13]Kepler.http://kepler-project.org/
[14]DACMan.http://www.gridworkflow.org/snipsrgridworkflow/mace/DACMan/
[15]Loke SW.Towards data-parallel skeletons for grid computing;Anitinerant mobile agent approach[A].IEEE.CCGRID 2003[C].Tokyo.Japan[s.n.].2003
[16]I.Foster.C.Kesselman.The Grid:Blueprint for a New Computing Infrastructure.[M]Morgan Kaufmann Publisher.1999
[17]I.Foster.C.Kesselman.S.Tuecke.The Anatomy of the Grid:Enabling Scalable Virtual Organizations.International J.Supercomputer Applications.15(3).2001.200-222
[18]OGSI.http//www.globus.org/ogsi Sept 20.2006
[19]I.Foster.C.Kesselman.J.Nick.Grid services for distributed system integration.Computer.2003.35(6):37-46
[20]SteveGraham.Davil Hull Bryan Murray Web Services Base Notification 1.3(WS -Base Notification)OASIS standard.1 October 2006
[21]Dave Chappell Lily Liu Web Services Brokered Notification 1.3(WS-Brokered Notification)OASIS standard.1 October 2006
[22]William.Vambenepe.Steve Graham.Peter Niblett WebServices Addressing (WS-Addressing)W3C Member Submission 10 August 2006
[23]DonBox.Erk Christensen.Frameisco Cuberaetal Eeb Services Addressing (WS-Addressing)W3C Member Submission 10 August 2006
[24]I.Foster.C.Kesselman.J.Nick et al.Grid services for distributed system integration.Computer.2003.35(6):37-46
[25]J.Gehring.A.Streit.Robust resource management for metacomputers.In:Proc of 9th IEEE International Symposium on High-Performance DistributedComputing.IEEE CS Press.USA.2004.105-112
[26]L.Silva.R.Buyya.Parallel programming paradigms.2nd ed.Prentice Hall.USA.2001.86-92
[27]李伟.徐志伟.卜冠英等.网格环境下一种有效的资源查找方法[J].计算机学报.2003.26(11 1:1546)1549
[28]周伟生.网格环境下基于Agent技术资源管理的研究.[硕士学位论文].南京理工大学.2004.74.No.5
[29]I.Foster and C.Kessehnan(Eds.).The Grid:Blueprint for a New Computing Infrastructure.Morgan Kaufmann Publishers Inc.San Francisco.1999
[30]H.EI-ReWIni.T.I.ewis.H.Ali.Task Scheduling in Parallel and Distributed systems America.PrenticeHall.1999
[31]R.Sethi.Scheduling Graphs on Two Processors[J].SIAM J Computing.5(1): 73-82.1976.
[32]Workflow Management Coalition.Workflow management coalition terminology and glossary.Technical Report.WfMC-TC-1011.Brussels:Workflow Management Coalition.1996.8-17
[33]Mohan C.Recent trends in workflow management products.standards.and research.1997
[34]Workflow.http://www.almaden.ibm.com/cs/exotica/wfnote97.ps/
[35]罗海滨.范玉顺.吴澄等.工作流技术综述[J].软件学报 2002.11
[36]吴朝晖.潘云鹤.工作流管理技术:机遇和挑战[J].计算机科学.2003.26(10):20-23
[37]UNICORE.http://www.unicore.de
[38]网格工作流执行的基本过程.http://www.extreme.indiana.edu/groc/gridworkflow_infrastructure- dieteycybok/CWL.pdf
[39]R.Yahyapour.P.Wieder.A.Pugliese.D.Talia and J.Hahm.Grid Scheduling Use Cases White Paper.Global Grid Forum.19 July.2004
[40]WFMC:Workflow Management Coalition The Workflow Reference Model David Hollingsworth.19-Jan-95.6-18 20-44
[41]赵卫东.黄丽华.蔡斌.工作流过程模型研究[J].系统工程理论方法应用.2002.11(3):212-217
[42]周建涛.史美林.叶新铭.一种描述工作流的扩展Petri网模型—EWFPN.第三届全国CSCW会议.呼和浩特.2002.31-38
[43]Georgakopoulos D.Hornick M.Shethv A.An Overview of Workflow Management:from Process Modeling to Workflow Automation Infrastructure.Distributed and Parallel Database.1995.3(2):119-152
[44]杨艳.唐胜群.张文涛.一种基于OGSI的网格工作流描述语言[J].计算机工程.2005.31(1):19-21
[45]Paul Grefen.Jochem Vonk.Global Transaction Support for Workflow Management Systems.The VLDB Journal.2001.Vol(10):316-333
[46]Du Weimin.DavisJ.ShanMing Chen.Flexible Specification of Workflow Compensation Scopes.In:Proc ACMSIGGROUP Conference on Supporting Group Work.Phoenix.1997.309-316
[47]Salimifard K.Wright M.Petri Net-based Modeling of Workflow Systems:Anoverview.European Journal of Operational Research.2001.134(3):664-676
[48]潘启澎.姜兵.基于Petri网的工作流建模技术及应用[J].清华大学学报(自然科学版).2000.40(9):86-89
[49]vander Aalst WM P.The Application of Petri Nets to Workflow Management.The Journal of Circuits.Systems and Computers.1998.8(1):21-66
[50]Salimifard K.Wright M.Petri net_based modelling of workflow systems" European Journal of Operational Research.2001.134:664-676
[51]Vander Aalst W M P.Kummar A.A reference model for teamenabled workflow management systems.Data&Knowledge Engineering.2001.38:335-363
[52](荷)阿斯特.工作流管理:模型、方法和系统[M].王建民译.清华大学出版社.2004.23-25
[53]唐国春.现代排序论[M].上海科学普及出版社.2003.12-13
[54]leon cooper and mary w.cooper.动态规划导论[M].张有为译.国防大学出版社.1985.48-49
[55]王莉.李志蜀.殷锋.基于网格工作流的政务协同研究[J].微电子学与计算机.2006.23:77-79
[2]Quinn Snell Kevin Tew.An enterprise-based grid resource management system [C]Edinburgh Scotland Proceedings of the Tenth IEEE International Symposium on High Performance Distributed Computing(HPDC-11).2002.83-87
[3]Jerry Rolia.Jim Pruyne.Grids for enterprise applications[C].Seattle:Proceedings of the 9 Workshop on Job Scheduling Strategies for Parallel Programs.2003.129-147.
[4]张绍华.网格工作流关键技术研究:(博士论文)复旦大学.2004.6
[5]Globus.http://www.globus.org/
[6]Condor Team.http://www.cs.wisc.edu/condor/
[7]WSRF.http://www.globus.org/wsrf/
[8]Arkin A.et al.Business Process Modeling language(BPMI)2002
[9]Krishnan S.Wagstrom P.von Laszewski G.GSFL;A Workflow Framework for Grid Services.ANL/MGS-P980-0802.Argonne.2002
[10]Graham G E.Evans D.Bertram I.Mc Runjob;A High Energy Physics Workflow Planner for Grid.Computing in High Energy and Nuclear Physics.La Jolla.California.March 2003
[11]Grid Ant.http://www.gridworkflow.org/snips/gridworkflow/space/GridAnt
[12]Cvon Laszewski.M.Hategan.;Java CoGKit Karajan/CridAnt Work-flow Guide.Technical Report.Argonne National Laboratory.Argonne.IL.USA.2005
[13]Kepler.http://kepler-project.org/
[14]DACMan.http://www.gridworkflow.org/snipsrgridworkflow/mace/DACMan/
[15]Loke SW.Towards data-parallel skeletons for grid computing;Anitinerant mobile agent approach[A].IEEE.CCGRID 2003[C].Tokyo.Japan[s.n.].2003
[16]I.Foster.C.Kesselman.The Grid:Blueprint for a New Computing Infrastructure.[M]Morgan Kaufmann Publisher.1999
[17]I.Foster.C.Kesselman.S.Tuecke.The Anatomy of the Grid:Enabling Scalable Virtual Organizations.International J.Supercomputer Applications.15(3).2001.200-222
[18]OGSI.http//www.globus.org/ogsi Sept 20.2006
[19]I.Foster.C.Kesselman.J.Nick.Grid services for distributed system integration.Computer.2003.35(6):37-46
[20]SteveGraham.Davil Hull Bryan Murray Web Services Base Notification 1.3(WS -Base Notification)OASIS standard.1 October 2006
[21]Dave Chappell Lily Liu Web Services Brokered Notification 1.3(WS-Brokered Notification)OASIS standard.1 October 2006
[22]William.Vambenepe.Steve Graham.Peter Niblett WebServices Addressing (WS-Addressing)W3C Member Submission 10 August 2006
[23]DonBox.Erk Christensen.Frameisco Cuberaetal Eeb Services Addressing (WS-Addressing)W3C Member Submission 10 August 2006
[24]I.Foster.C.Kesselman.J.Nick et al.Grid services for distributed system integration.Computer.2003.35(6):37-46
[25]J.Gehring.A.Streit.Robust resource management for metacomputers.In:Proc of 9th IEEE International Symposium on High-Performance DistributedComputing.IEEE CS Press.USA.2004.105-112
[26]L.Silva.R.Buyya.Parallel programming paradigms.2nd ed.Prentice Hall.USA.2001.86-92
[27]李伟.徐志伟.卜冠英等.网格环境下一种有效的资源查找方法[J].计算机学报.2003.26(11 1:1546)1549
[28]周伟生.网格环境下基于Agent技术资源管理的研究.[硕士学位论文].南京理工大学.2004.74.No.5
[29]I.Foster and C.Kessehnan(Eds.).The Grid:Blueprint for a New Computing Infrastructure.Morgan Kaufmann Publishers Inc.San Francisco.1999
[30]H.EI-ReWIni.T.I.ewis.H.Ali.Task Scheduling in Parallel and Distributed systems America.PrenticeHall.1999
[31]R.Sethi.Scheduling Graphs on Two Processors[J].SIAM J Computing.5(1): 73-82.1976.
[32]Workflow Management Coalition.Workflow management coalition terminology and glossary.Technical Report.WfMC-TC-1011.Brussels:Workflow Management Coalition.1996.8-17
[33]Mohan C.Recent trends in workflow management products.standards.and research.1997
[34]Workflow.http://www.almaden.ibm.com/cs/exotica/wfnote97.ps/
[35]罗海滨.范玉顺.吴澄等.工作流技术综述[J].软件学报 2002.11
[36]吴朝晖.潘云鹤.工作流管理技术:机遇和挑战[J].计算机科学.2003.26(10):20-23
[37]UNICORE.http://www.unicore.de
[38]网格工作流执行的基本过程.http://www.extreme.indiana.edu/groc/gridworkflow_infrastructure- dieteycybok/CWL.pdf
[39]R.Yahyapour.P.Wieder.A.Pugliese.D.Talia and J.Hahm.Grid Scheduling Use Cases White Paper.Global Grid Forum.19 July.2004
[40]WFMC:Workflow Management Coalition The Workflow Reference Model David Hollingsworth.19-Jan-95.6-18 20-44
[41]赵卫东.黄丽华.蔡斌.工作流过程模型研究[J].系统工程理论方法应用.2002.11(3):212-217
[42]周建涛.史美林.叶新铭.一种描述工作流的扩展Petri网模型—EWFPN.第三届全国CSCW会议.呼和浩特.2002.31-38
[43]Georgakopoulos D.Hornick M.Shethv A.An Overview of Workflow Management:from Process Modeling to Workflow Automation Infrastructure.Distributed and Parallel Database.1995.3(2):119-152
[44]杨艳.唐胜群.张文涛.一种基于OGSI的网格工作流描述语言[J].计算机工程.2005.31(1):19-21
[45]Paul Grefen.Jochem Vonk.Global Transaction Support for Workflow Management Systems.The VLDB Journal.2001.Vol(10):316-333
[46]Du Weimin.DavisJ.ShanMing Chen.Flexible Specification of Workflow Compensation Scopes.In:Proc ACMSIGGROUP Conference on Supporting Group Work.Phoenix.1997.309-316
[47]Salimifard K.Wright M.Petri Net-based Modeling of Workflow Systems:Anoverview.European Journal of Operational Research.2001.134(3):664-676
[48]潘启澎.姜兵.基于Petri网的工作流建模技术及应用[J].清华大学学报(自然科学版).2000.40(9):86-89
[49]vander Aalst WM P.The Application of Petri Nets to Workflow Management.The Journal of Circuits.Systems and Computers.1998.8(1):21-66
[50]Salimifard K.Wright M.Petri net_based modelling of workflow systems" European Journal of Operational Research.2001.134:664-676
[51]Vander Aalst W M P.Kummar A.A reference model for teamenabled workflow management systems.Data&Knowledge Engineering.2001.38:335-363
[52](荷)阿斯特.工作流管理:模型、方法和系统[M].王建民译.清华大学出版社.2004.23-25
[53]唐国春.现代排序论[M].上海科学普及出版社.2003.12-13
[54]leon cooper and mary w.cooper.动态规划导论[M].张有为译.国防大学出版社.1985.48-49
[55]王莉.李志蜀.殷锋.基于网格工作流的政务协同研究[J].微电子学与计算机.2006.23:77-79
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |