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

摘要 针对截止期约束的工作流费用优化问题，逆向分层算法利用同步结束特征优化调度取得了较好的效果.然而，现有此类算法缺乏有效的宽裕时间分配策略容易产生无效时间碎片.通过定义邻服务级差性价比，以及对分配避免活动集的特性分析设计了宽裕时间有效分配启发式算法（slack-time effective allocation，SEA）.SEA使宽裕时间分配给所需的逆向分组以产生最大的费用优化效果，避免无效时间碎片.同时基于对工作流截止期的不同分区属性的分析设计了改进的时序一致性工作流费用优化算法（slack-time effective allocation extended TCDBL，SATCDBL）.实验结果表明了SATCDBL相比典型逆向分层算法DBL和TCDBL，平均费用分别降低了25.9%和12.7%