基于逆向分层的工作流时间-费用优化方法  

Time and cost trade-off heuristics for workflow scheduling based on bottom level

作　　者：刘灿灿 张卫民[2] 骆志刚[2] 

机构地区：[1]空军军训器材研究所,北京100195 [2]国防科技大学计算机学院,湖南长沙410073

出　　处：《国防科技大学学报》2013年第3期61-66,共6页Journal of National University of Defense Technology

基　　金：国家863计划资助项目(2006AA01A123);国家自然科学基金资助项目(60903042)

摘　　要：针对效用网格下基于优先级因子的工作流时间-费用优化问题,基于工作流的同步完成特征对任务进行分层并提出三种实时调度算法:基于逆向分层的sufferage(BLSuff)、基于逆向分层的min-min(BLMin)及基于逆向分层的min-max(BLMax)。算法设计基于优先级因子的衡量标准对时间与费用同时进行优化,并为任务设置期望完成时间以达到充分利用费用优化空间进行费用优化的目标。实验结果表明这三种算法在各种优先级因子下都能对工作流的执行时间与执行费用进行较好的优化。In order to manage the trade-off between the workflow execution time and the workflow execution cost on utility grids,the task was divided into several groups by using the workflow synchronization properties,and three real-time heuristics were proposed： the bottom level based sufferage（BLSuff）,the bottom level based min-min（BLMin） and the bottom level based min-max（BLMax）.A metric was designed in these heuristics to optimize the execution time and the execution cost simultaneously based on the trade-off factor,and the expected finish time was set for the task trying to make most of the cost optimization space to save the workflow execution cost.The experimental results demonstrate that these heuristics can optimize the execution time and execution cost simultaneously with various trade-off factors.

关 键 词：工作流调度 时间-费用优化 优先级因子 逆向分层 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]