使用宽裕时间有效分配优化工作流逆向分层算法  

Using Slack-time Effective Allocation to Facilitate Bottom-level Based Workflow Cost Optimization

作　　者：郑美光[1] 胡志刚[1] 杨柳[1] 赵锦元[1] 

机构地区：[1]中南大学软件学院,长沙410075

出　　处：《小型微型计算机系统》2016年第8期1639-1644,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61272148;60970038)资助;国家自然科学基金青年项目(61301136)资助;中南大学博士后基金项目资助

摘　　要：针对截止期约束的工作流费用优化问题,逆向分层算法利用同步结束特征优化调度取得了较好的效果.然而,现有此类算法缺乏有效的宽裕时间分配策略容易产生无效时间碎片.通过定义邻服务级差性价比,以及对分配避免活动集的特性分析设计了宽裕时间有效分配启发式算法(slack-time effective allocation,SEA).SEA使宽裕时间分配给所需的逆向分组以产生最大的费用优化效果,避免无效时间碎片.同时基于对工作流截止期的不同分区属性的分析设计了改进的时序一致性工作流费用优化算法(slack-time effective allocation extended TCDBL,SATCDBL).实验结果表明了SATCDBL相比典型逆向分层算法DBL和TCDBL,平均费用分别降低了25.9%和12.7%.Analyzing the synchronization properties that all activities in the same bottom level （ BL ） have the identical sub-deadline, BL heuristics are relatively efficient to solve the workflow optimization problem. However, with the lack of effective strategy to allo- cate slack-time, this kind of algorithm is prone to invalid time fragment. Based on the definition of performance cost ratio of adjacent service level differential （ PCRASLD ） and the property analysis of allocation avoided activity sets （ AAAS ）, a slack-time effective allocation heuristic called SEA is proposed. Allocating slack-time to the fight BL group, SEA tries to avoid invalid time fragment and optimize the workflow cost. By adopting SEA and analyzing the different property with deadline in different domain, an extended tem- poral consistency based algorithm called SATCDBL for cost optimization in workflow scheduling is presented. Compared with two typical BL heuristics namely DBL and TCDBL, the experimental results show that SATCDBL can decrease the average cost by 25.9% and 12. 7% respectively.

关 键 词：无效时间碎片 邻服务级差性价比 工作流费用优化 逆向分层 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]