基于串归约的网格工作流费用优化方法

Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial Reduction

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明:BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.

Workflow scheduling which guarantees the anticipated QoS （quality of service） is a fundamental and complexity problem in computational grids. In this paper, the scheduling of workflows represented by directed acyclic graph （DAG） with the objective of cost minimization is considered. In general, the optimization problem is NP-hard. Two new heuristics, FSRD （forward serial reduction with deadline） and BSRD （backward serial, reduction with deadline） are proposed. According to the property of serial activities, a new concept called series reduction （SR） is defined. The time window for each serial reduction group is recalculated based on leveling algorithms. A dynamic programming method is presented for implementing the cost minimization of each serial reduction group. By integrating the local optimization strategy with two leveling algorithms （DBL and DTL）, BSRD and FSRD are investigated. The two heuristics take into account comprehensive serial and parallel properties of DAG, and improve the cost optimization strategies adopted by leveling algorithms. Experimental results show that BSRD and FSRD can considerably improve the average performance of corresponding leveling heuristics. For pipeline workflows, BSRD （FSRD） can achieve the optimal solutions but require a little more computational time. For hybrid workflows, BSRD can save 8.77 % average cost of DBL and FSRD can save 6.00% average cost of DTL. Moreover, BSRD outperforms FSRD. As well, the impact of serial reduction ratio on two heuristics is analyzed.