互斥约束工作流可满足性决策的匹配剪枝模式回溯法

摘要：

针对用于工作流可满足决策的模式回溯技术如何平衡性能与代价的问题,提出了一种对部分模式解及时进行授权匹配验证的优化方法,牺牲一定验证效率以增强剪枝能力.就仅受互斥约束的问题情形,利用实例难易程度的两极分化现象对总体时间性能进行了分析.随机生成数据集上的实验表明,这一优化极大地降低了模式回溯在难实例上的时间代价,而对易实例执行时间的影响很小,且相对于其他基于动态规划的代表性算法,优化后的算法在时间和空间性能上均有显著优势.

关键词：工作流、授权、约束、资源分配、可满足性

所属期刊栏目：29

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61572163,61502429;浙江省自然科学基金资助项目LY17F050005;浙江省教育厅科研项目Y201737476;教育部人文社会科学研究项目17YJC630109,17YJA880004

在线出版日期：2019-04-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：2988-2998