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

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

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

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 vectorformed 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.