向量目标整数线性规划问题及其在工作流网分析中的应用

doi:10.13196/j.cims.2017.05.004

计算机集成制造系统 ›› 2017, Vol. 23 ›› Issue (第5期): 947-954.DOI: 10.13196/j.cims.2017.05.004

向量目标整数线性规划问题及其在工作流网分析中的应用

包云霞^1,2,鲁法明^1,3+,王艳晓¹,段华²,林泽东¹

1.山东科技大学计算机科学与工程学院
2.山东科技大学数学与系统科学学院
3.同济大学嵌入式系统与服务计算教育部重点实验室

出版日期:2017-05-31 发布日期:2017-05-31
基金资助:
国家自然科学基金资助项目(61602279,61472229);山东省科技发展计划资助项目(2014GGX101035,2016ZDJS02A11);山东省自然科学基金资助项目(BS2014DX013,ZR2015FM013);同济大学嵌入式系统与服务计算教育部重点实验室开放课题资助项目 (ESSCKF201403);山东省博士后创新专项资金资助项目(201603056);山东科技大学领军人才与优秀科研团队计划资助项目(2015TDJH102)。

Integer linear programming problems with vector-formed objectives and its application in workflow net analysis

Online:2017-05-31 Published:2017-05-31
Supported by:
Project supported by the National Natural Science Foundation,China(No.61602279,61472229),the Science & Technology Development Fund of Shandong Province,China(No.2014GGX101035,2016ZDJS02A11),the Shandong Provincial Natural Science Fondation,China (No.BS2014DX013,ZR2015FM013),the Open Project Foundation of the Key Laboratory of Embedded System and Service Computing of Ministry of Education in Tongji University,China(No.ESSCKF201403),the Shandong Provincial Postdoctoral Innovation Project,China(No.201603056),and the SDUST Research Fund,China(No.2015TDJH102).

摘要/Abstract

摘要： 为了求解一类特殊的整数规划问题以对工作流网进行可达性分析和不变量计算,将该类问题进行归纳和抽象,提出向量目标整数线性规划问题的概念和标准模型;在传统整数规划问题求解方法的基础上,针对一类正定的向量目标整数线性规划问题设计了一种新的分支定界算法,以求取全部最优解;将工作流网不变量分解与恰当终结性验证等问题转换为前述向量目标整数规划问题,结合实例说明了该方法在工作流网性质分析中的应用。

关键词: 整数规划, Petri网, 工作流网, 分支定界法

Abstract: To solve a special kind of integer programming problems for reachability analysis and invariant computation of workflow nets,the definition and the standard model of Integer Linear Programming (ILP) problems with vector-formed objectives were presented by summarizing and abstracting these special problems.On the basis of the traditional ILP solving methods,a new type of branch and bound method was introduced to compute all the optimization solutions of positive-definite ILP problems.Both the decomposition approach with invariants and the properly end property of workflow nets were attributed to the solution of ILP problems with vector-formed objectives.The application of the proposed method in workflow net analysis was illustrated with two specific examples.

Key words: integer programming, Petri nets, workflow net, branch and bound method

中图分类号:

TP301

包云霞,鲁法明,王艳晓,段华,林泽东. 向量目标整数线性规划问题及其在工作流网分析中的应用[J]. 计算机集成制造系统, 2017, 23(第5期): 947-954.

[1]	鲁法明,崔明浩,包云霞,曾庆田,段华. 基于程序运行轨迹Petri网模型挖掘的死锁检测方法[J]. 计算机集成制造系统, 2021, 27(9): 2611-2624.
[2]	王丽丽,方贤文. 基于行为距离的带隐变迁过程模型挖掘方法[J]. 计算机集成制造系统, 2021, 27(9): 2670-2679.
[3]	王沙沙,张则强,刘俊琦,陈凤. 多路径交互环形过道布置问题建模及改进蚁狮算法优化[J]. 计算机集成制造系统, 2021, 27(8): 2237-2247.
[4]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[5]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[6]	张海军,闫琼,张国辉,李庆宇,余杰. 基于数字孪生的制造资源动态优选决策[J]. 计算机集成制造系统, 2021, 27(2): 521-535.
[7]	王沙沙,张则强,刘俊琦,陈凤. 双向环形过道布置问题建模及混合鲸鱼算法求解[J]. 计算机集成制造系统, 2021, 27(10): 2908-2920.
[8]	李文川,高思源,章鑫,冯良清. 基于随机Petri网的企业RFID技术采纳内化建模与仿真[J]. 计算机集成制造系统, 2020, 26(第2): 470-480.
[9]	何彦,陈文奇,王禹林,岳冠楠,李育锋,田小成. 集成设计参数和制造参数的车削工件机加工能耗预测方法[J]. 计算机集成制造系统, 2020, 26(9): 2355-2366.
[10]	张立彬,吕焕培,胥芳,谭大鹏,陈教料,林琼. 面向低压电器的CPN协同装配任务建模与优化[J]. 计算机集成制造系统, 2020, 26(7): 1737-1748.
[11]	刘聪,程龙,曾庆田,闻立杰,欧阳春. 基于Petri网的分层业务过程挖掘方法[J]. 计算机集成制造系统, 2020, 26(6): 1525-1537.
[12]	黄苾,代飞,王亚博,莫启,曹涌,王雷光. 基于Petri网分析编排的可实现性[J]. 计算机集成制造系统, 2020, 26(6): 1548-1556.
[13]	韩咚,田银花,杜玉越,张琴. 基于Petri网可达图的业务对齐方法[J]. 计算机集成制造系统, 2020, 26(6): 1589-1606.
[14]	郝惠晶,方贤文,方娜,许健. 基于Petri网的业务流程低频行为挖掘与优化分析[J]. 计算机集成制造系统, 2020, 26(6): 1660-1667.
[15]	毛永年,唐秋华,张利平,李梓响. 具有并行制造特征的自动化混流生产线调度模型[J]. 计算机集成制造系统, 2019, 25(第7): 1717-1728.

向量目标整数线性规划问题及其在工作流网分析中的应用

Integer linear programming problems with vector-formed objectives and its application in workflow net analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics