基于相对效费比的网格工作流调度算法

• 论文 •

基于相对效费比的网格工作流调度算法

龙浩，梁毅，邸瑞华

1.北京工业大学计算机学院，北京100124；2.江西师范大学软件学院，江西南昌330022

出版日期:2010-03-15 发布日期:2010-03-25

Relative time-cost rate based heuristic for workflow scheduling in grids

LONG Hao, LIANG Yi, DI Rui-hua

1.School of Computer Science, Beijing University of Technology, Beijing 100124,China; 2.School of Software,Jiangxi Normal University, Nanchang, 330022,China

Online:2010-03-15 Published:2010-03-25

摘要/Abstract

摘要： 为解决计算网格中有向无环图表示的截止期约束下的工作流时间费用优化问题，提出了一个新的启发式优化算法——相对效费比算法。该算法首先根据调度系数得到初步方案，再逐步调整，当方案完工时间小于截止期时，用时间换成本，选择成本消减最快的节点进行调整，中选服务有最大的正相对效费比值；当方案完工时间超过截止期时，用成本换时间，调整成本增加最慢服务的节点，中选服务有最大的负相对效费比值，该方法在保证截止期约束的同时能有效降低总成本。通过大量模拟实验和与最小关键路径、正向分层费用优化算法、逆向分层费用优化算法的比较，证明了相对效费比的有效性。

关键词: 网格, 工作流, 有向无环图, 启发式算法, 相对效费比

Abstract: In order to solve the workflow time-cost optimization problem under deadline restrictions represented by directed acyclic graph (DAG) in computation grids, a novel heuristics algorithm called relative time-cost rate（RTCR）was proposed. Firstly the preliminary program was obtained by scheduling coefficient, then the scheduling was optimized gradually：when the deadline exceeded, the node with the slowest cost-decreased service was rescheduled, the selected service had the maximum positive RTCR value, otherwise the node with the fastest cost-increased service was rescheduled, the selected service had the maximum negative RTCR value. The proposed method simultaneously guaranteed deadline restrictions and reduced total cost., the RTCR's effectivenss was revealed by comparing with minimum critical path (MCP), deadline top level (DTL) and deadline bottom leve (DBL l).

Key words: grid, workflow, directed acrylic graph, heuristics, relative time-cost rate

中图分类号:

TP393

龙浩，，梁毅，邸瑞华. 基于相对效费比的网格工作流调度算法[J]. .

LONG Hao，, LIANG Yi, DI Rui-hua. Relative time-cost rate based heuristic for workflow scheduling in grids[J]. .

[1]	唐玄昭,余阳,吴荆璞,潘茂林. 基于区块链的业务流程互操作服务框架[J]. 计算机集成制造系统, 2021, 27(9): 2508-2516.
[2]	文一凭,王志斌,刘建勋,许小龙,康国胜. 云际协作环境下能耗与成本感知的工作流调度方法[J]. 计算机集成制造系统, 2021, 27(9): 2583-2591.
[3]	满君丰,赵龙乾,彭成,李倩倩. 云边协同计算架构下大规模工厂接入的任务调度[J]. 计算机集成制造系统, 2021, 27(8): 2282-2294.
[4]	汪逸晖,高亮. 乌鸦搜索算法的改进及其在工程约束优化问题中的应用[J]. 计算机集成制造系统, 2021, 27(7): 1871-1883.
[5]	高勃,张红艳,朱明皓. 面向智能制造的不规则零件排样优化算法[J]. 计算机集成制造系统, 2021, 27(6): 1673-1680.
[6]	袁友伟,黄锡恺,俞东进,李忠金. 移动边缘计算环境下服务工作流容错调度算法[J]. 计算机集成制造系统, 2021, 27(6): 1693-1702.
[7]	王仁伟,张松,葛人杰,栾晓娜,王家昌,鲁韶磊. 改进的球头铣刀加工表面形貌建模方法[J]. 计算机集成制造系统, 2021, 27(4): 973-980.
[8]	顾文斌,李育鑫,钱煜晖,肖紫涵,秦展鹏. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
[9]	冷龙龙,赵燕伟,蒋海青,张春苗,王舜. 求解物流配送同时取送货低碳选址—路径问题的量子超启发式算法[J]. 计算机集成制造系统, 2020, 26(第3): 815-828.
[10]	曹浩,莫蓉,万能. 面向支撑力分布的桁架结构设计方法[J]. 计算机集成制造系统, 2020, 26(7): 1763-1770.
[11]	李万清,刘辉,李忠金,袁友伟. 移动边缘计算环境下面向安全和能耗感知的服务工作流调度方法[J]. 计算机集成制造系统, 2020, 26(7): 1831-1842.
[12]	林煊,陈庆新,毛宁. 板式家具高速自动分拣系统出库及打包调度策略[J]. 计算机集成制造系统, 2020, 26(7): 1843-1854.
[13]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[14]	林国丹,黄钦开,余阳,潘茂林. Activiti引擎的无状态云工作流调度算法[J]. 计算机集成制造系统, 2020, 26(6): 1456-1464.
[15]	文一凭,王志斌,刘建勋,许小龙,陈爱民,曹步清. 混合云环境下成本与隐私感知的工作流调度方法[J]. 计算机集成制造系统, 2020, 26(6): 1582-1588.