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

中国机械工程

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

翟治年1;卢亚辉2;万健1,3;王中鹏1;吴茗蔚1

1.浙江科技学院信息与电子工程学院，杭州，310023
2.深圳大学计算机与软件学院，深圳，518060
3.复杂系统建模与仿真教育部重点实验室，杭州，310018

出版日期:2018-12-25 发布日期:2018-12-24
基金资助:
国家自然科学基金资助项目(61572163,61502429);
浙江省自然科学基金资助项目(LY17F050005);
浙江省教育厅科研项目 (Y201737476);
教育部人文社会科学研究项目(17YJC630109，17YJA880004)
National Natural Science Foundation of China （No. 61572163,61502429）
Zhejiang Provincial Natural Science Foundation of China （No. LY17F050005）

Match-pruning Pattern Backtracking Algorithm for Exclusion Constrained Workflow Satisfiability Decision

ZHAI Zhinian1;LU Yahui2;WAN Jian1,3;WANG Zhongpeng1;WU Mingwei1

1.School of Information and Electronic Engineering，Zhejiang University of Science and Technology，Hangzhou， 310023
2.School of Computer and Software，Shenzhen University，Shenzhen，Guangdong,518060
3.Key Laboratory of Complex Systems Modeling and Simulation,Ministry of Education，Hangzhou，310018

Online:2018-12-25 Published:2018-12-24
Supported by:
National Natural Science Foundation of China （No. 61572163,61502429）
Zhejiang Provincial Natural Science Foundation of China （No. LY17F050005）

摘要/Abstract

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

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

Abstract: To address the issue of balancing the performance and cost in pattern backtracking (PB) technique for workflow satisfiability decision，an optimizing method was proposed where the authorization matching was enforced in time on partial pattern solutions to strengthen pruning by giving up some validating efficiencies. The overall performance was analysed by utilizing the polarizing phenomenon of ease or the complexity of instances on exclusion-constrained problems. Experiments on randomly generated data sets show that the optimization reduces the solving time of PB on hard instances greatly with little influence on the run-time of easy instances. Besides，the optimized algorithm has notably better time and space performances than other representative algorithms based on dynamic planning.

Key words: workflow；authorization；constraint, resource allocation, satisfiability

中图分类号:

TP309

翟治年1;卢亚辉2;万健1,3;王中鹏1;吴茗蔚1. 互斥约束工作流可满足性决策的匹配剪枝模式回溯法[J]. 中国机械工程.

ZHAI Zhinian1;LU Yahui2;WAN Jian1,3;WANG Zhongpeng1;WU Mingwei1. Match-pruning Pattern Backtracking Algorithm for Exclusion Constrained Workflow Satisfiability Decision[J]. China Mechanical Engineering.

参考文献

[1]陶飞，张霖，郭华,等. 云制造特征及云服务组合关键问题研究[J]. 计算机集成制造系统，2011，17(3):477-486.
TAO Fei，ZHANG Lin，GUO Hua，et al. Typical Characteristics of Cloud Manufacturing and Several Key Issues of Cloud Service Composition [J]. Computer Integrated Manufacturing Systems，2011，17(3):477-486.
[2]鲁建厦，胡庆辉，董巧英，等. 面向云制造的混流混合车间调度问题[J]. 中国机械工程，2017，28(2):191-198.
LU Jiansha，HU Qinghui，DONG Qiaoying，et al. Cloud Manufacturing-oriented Mixed-model Hybrid Shop-scheduling Problem[J]. China Mechanical Engineering，2017，28(2):191-198.
[3]周龙飞，张霖，刘永奎. 云制造调度问题研究综述[J]. 计算机集成制造系统，2017，23(6):1147-1166.
ZHOU Longfei，ZHANG Lin，LIU Yongkui. Survey on Scheduling Problem in Cloud Manufacturing[J]. Computer Integrated Manufacturing Systems，2017，23(6):1147-1166.
[4]马文龙，赵燕伟，王万良. 制造云服务组合异常自适应调整方法[J]. 中国机械工程，2016，27(6):778-784.
MA Wenlong，ZHAO Yanwei，WANG Wanliang. An Adaptive Adjustment Method of Composition Exception for Manufacturing Cloud Service[J]. China Mechanical Engineering，2016，27(6):778-784.
[5]WANG Q，LI N. Satisfiability and Resiliency in Workflow Authorization Systems[J]. ACM Transactions on Information and System Security，2010，13(4):1-35.
[6]CRAMPTON J，GUTIN G，YEO A, et al. On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem[J]. ACM Transactions on Information & System Security，2013，16(1):1-31.
[7]COHEN D，CRAMPTON J，GAGARIN A，et al. Iterative Plan Construction for the Workflow Satisfiability Problem[J]. Journal of Artificial Intelligence Research，2014,51(11):555-577.
[8]COHEN D，CRAMPTON J，GAGARIN A，et al. Algorithms for the Workflow Satisfiability Problem Engineered for Counting Constraints[J]. Journal of Combinatorial Optimization，2016，32(1):3-24.
[9]KARAPETYAN D，GAGARIN A，GUTIN G. Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-independent Constraints[C]// Proceedings of International Workshop on Frontiers in Algorithmics.Guilin，2015:138-149.
[10]CRAMPTON J，GAGARIN A，GUTIN G，et al. On the Workflow Satisfiability Problem with Class-independent Constraints for Hierarchical Organizations[J]. ACM Transactions on Privacy & Security，2016，19(3):8.
[11]HENTENRYCK P V，FLENER P，PEARSON J，et al. Tractable Symmetry Breaking for CSPs with Interchangeable Values[C]// Proceedings of the 18th International Joint Conference on Artificial Intelligence. Acapulco，2003:277-282.
[12]RONEY-DOUGAL C M，GENT I P，KELSEY T，et al. Tractable Symmetry Breaking Using Restricted Search Trees[C]// Proceedings of the 16th European Conference on Artificial Intelligence. Valencia，2004:211-215.
[13]FLENER P，PEARSON J，SELLMANN M，et al. Dynamic Structural Symmetry Breaking for Constraint Satisfaction Problems[J]. Constraints，2009，14(4):506-538.
[14]COHEN D，JEAVONS P，JEFFERSON C，et al. Symmetry Definitions for Constraint Satisfaction Problems[J]. Constraints，2006，11(2/3):115-137.
[15]EDMONDS J. Paths，Trees and Flowers[J]. Canadian Journal of Mathematics，1965，17(2):449-467.
[16]FREUDER E C. A Sufficient Condition for Backtrack-free Search[J]. Journal of the ACM，1982，29(1):24-32.
[17]PURDOM，P W. Backtracking and Random Constraint Satisfaction[J]. Annals of Mathematics & Artificial Intelligence. 1997，20(7):393-410.
[18]DYER M E，FRIEZE A M，MOLLOY M. A Probabilistic Analysis of Randomly Generated Binary Constraint Satisfaction Problems[J]. Theoretical Computer Science，2003，290(1):1815-1828.