基于时序一致的工作流费用优化方法

Temporal Consistency Based Heuristics for Cost Optimization in Workflow Scheduling

针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(deadline bottom level,DBL)的基础上,研究工作流的时序特征,并基于任务的一致性状态对费用进行优化,提出了基于时序一致的截止期约束逆向分层算法(temporal consistency based deadline bottom level,TCDBL).TCDBL通过一致性时间点来保证时间约束,解决了DBL的适用性受限问题;同时基于各层并行度分配冗余时间,基于宽松时间约束策略进行费用优化,达到了进一步减少工作流执行费用的目标.实验结果表明TCDBL的费用优化效果比DBL改进了约14%.

Leveling heuristics are used to solve the time-cost trade-off problems in the grid workflow scheduling with temporal constraint by distributing the tasks into groups based on levels and scheduling them level by level. However, due to the absence of an effective method to ensure the temporal constraint, the applicability and performance of these leveling heuristics are damaged. Based on the previous heuristic deadline bottom level （DBL）, an advanced heuristic referred to as temporal consistency based deadline bottom level （TCDBL） is proposed by studying the temporal properties of workflows and by optimizing their execution cost based on the temporal consistency. TCDBL satisfies the workflow temporal constraint by setting a consistent temporal point for each task, distributes the redundancy time based on the parallel degree of each level, and optimizes the workflow cost with a soft temporal constraint strategy. As a result, the workflow execution cost decreases. The experimental results in this study demonstrate that the average execution cost of TCDBL is 14~ less than the cost of DBL.