基于路径平衡的工作流费用优化方法

针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(pathbalance,简称pb)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(pathbalancebasedcostoptimization,简称pbco)算法.pbco基于pb的计算结果设置初始约束时间,充分利用了工作流的费用优化空间.同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果.实验结果表明,pbco比另外几种著名算法(如det,dbl等)改进了约35%.