软件学报

作者：翟治年，卢亚辉，刘关俊，雷景生，向坚，吴茗蔚

单位：翟治年，浙江科技学院 信息与电子工程学院, 浙江 杭州 31002311,卢亚辉，深圳大学计算机与软件学院, 广东 深圳 51806002,刘关俊，同济大学计算机科学系, 上海 20180403,雷景生，浙江科技学院 信息与电子工程学院, 浙江 杭州 31002304,向坚，浙江科技学院 信息与电子工程学院, 浙江 杭州 31002305,吴茗蔚，浙江科技学院 信息与电子工程学院, 浙江 杭州 31002306

关键词：工作流;授权;约束;资源独立;资源分配;可满足

基金：国家自然科学基金(62172299, 61972357); 浙江省教育厅一般科研项目(Y201737476)

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k2)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k2). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.

来源：2023年第4期

《软件学报》期刊编辑部

查看软件学报杂志2023年第4期