法律状态公告日
法律状态信息
法律状态
2017-08-11
未缴年费专利权终止 IPC(主分类):G06Q10/04 授权公告日:20160210 终止日期:20160621 申请日:20120621
专利权的终止
2016-02-10
授权
授权
2013-01-23
实质审查的生效 IPC(主分类):G06Q10/04 申请日:20120621
实质审查的生效
2012-11-28
公开
公开
技术领域
本发明涉及计算机技术、信息技术和系统工程领域,尤其是一种面向业务过 程/工作流执行成本最小化的资源数量配置和任务分配优化方法。
背景技术
在当前面向顾客的日趋激烈的市场竞争环境下,为提高业务过程的执行效 率、获得竞争优势越来越多的企业采用了业务过程管理的方法和技术。合理的资 源配置/分配(包括如何配置资源数量和如何给资源分配任务)可以有效改进业 务过程的执行效率(如:提高资源的利用率,减少业务过程执行时间,降低业务 过程的执行成本等)。因此资源配置优化是业务过程管理的一个重要内容。
“业务过程执行成本”定义为完成一个业务过程实例或业务过程在单位时间 执行所花费的成本。所述“业务过程”是企业为完成某一目标而进行的一系列逻辑 上相关的活动/任务的有序集合,在某些领域也称之为“工作流”。业务过程执行 (即业务过程中活动的执行)通常需要资源的支持,会产生费用或成本。支持过 程执行的资源可以是人员、物理设备、文件、应用系统/程序等任何实体。成本 性能优化(如:满足给定的生产能力或客户需求下,最小化业务过程执行成本) 是资源配置优化的主要目标。
当前面向成本的业务过程/工作流资源配置优化方法中,通常假设一个资源 只能处理某一类活动实例/任务,或不同资源处理同类活动实例/任务服从相同的 随机分布,因此从资源执行活动效率的角度实际上他们研究了资源与活动之间一 对一和一对多的支持关系,而未考虑资源与活动之间多对多的支持关系及在这种 关系中存在的不同资源处理相同活动实例和同一资源处理不同活动实例的效率 可能是不同的问题;此外,通常采用基于资源的成本计算方法,假设业务过程执 行成本仅与配置的资源数量有关(即在业务过程执行成本计算中只考虑了资源的 固定配置成本),这些假设将阻碍对实际复杂业务过程资源配置的更进一步、精 确地描述、分析和优化。
发明内容
为了克服已有的业务过程资源配置优化方面的不足,本发明提供一种资源与 活动多对多支持关系下面向业务过程执行成本最小化的集成资源数量配置和任务 分配优化方法。
本发明解决其技术问题所采用的技术方案是:
一种面向业务过程执行成本最小化的集成资源数量配置和任务分配优化方 法,所述优化方法包括以下步骤:
第一步:建立业务过程模型
将所述业务过程模型定义为一个6元组其中:
(1)是过程实例/服务对象的到达速率;
(2)A是活动节点的集合,其元素a为活动编号,能被进一步描述为 a=(nm,ftm,fct,vct),其中:nm是活动名称,ftm是活动固有执行时间,fct是 活动每执行一次时所需的固定成本,vct是活动的可变成本,即活动执行的单位时 间成本,与活动执行时间成正比;
(3)C是连接点的集合,其元素c为连接点编号,能被进一步描述为 c=(nm,ty,lc),其中:nm是连接点名称,ty连接点类型,lc连接点逻辑; c.ty∈{″Split″,"Join"},c.lc∈{″And","Or"};令N=A∪C为业务过程模型节点(简 称节点)的集合,n∈N,则|·n|表示节点n的前序节点的个数,|n·|表示节点n的 后继节点的个数;若(|·n|=1)∧(|n·|>1),则n∈C∧n.ty="Split";若 (|·n|>1)∧(|n·|=1),则n∈C∧n.ty="Join";存在唯一的逻辑节点ns∈N,|·ns|=0, 称为开始逻辑节点,存在唯一的逻辑节点ne∈N,称为结束逻辑节点;
(4)是连接弧的集合,其元素l是连接弧编 号,能被进一步描述为l=(nm,inid,otid,prb),其中:nm是连接弧名称,inid是 输入节点编号,otid是输出节点编号,prb是执行概率;若n1,n2∈N,则l=<n1,n2> 表示从节点n1到节点n2的连接弧,l.inid=n1,l.otid=n2;若 则l.prb=1;若l∈{<c,n>|c.lc="Or″∧|c·|>1},则
(5)R是资源节点的集合,其元素r为资源编号,能被进一步描述为 r=(nm,qnt,fct,vct1,vct2),其中:nm是资源名称,qnt是资源数量,fct是单位 资源的固定使用成本,与资源的使用与否无关,而与资源的存在/折旧时间有关, vct1是资源的单位资源单位时间可变成本,即单位资源在单位时间内的使用成本, 与使用的时间成正比,vct2是单位资源的单位次数可变成本,即每使用一次的成 本,不依赖于使用时间,而依赖于使用次数;
(6)是资源与活动支持关系的集合,u=<a,r>表示资源r有能力处 理活动a的任务,其元素u是支持关系编号,能被进一步描述为 u=(nm,aid,rid,tap,st),其中:nm是支持关系/调用名称,aid活动编号,rid是 资源编号,tap是活动a的任务产生后分配给资源r去执行的概率,st是资源r处 理活动a的平均服务时间;令u.tap=ξa,r,由于任务只能被执行一次, 故有:
第二步:建立面向业务过程执行成本最小化的资源配置优化的数学模型及其求解
目标函数:
约束条件:
0≤ξa,r≤1,
r.qnt=0,1,…,Mr,
公式(8a)为要优化的目标函数,其中的βp为业务过程单位时间执行成本, βa为业务过程每执行一次活动a需要花费的成本,其计算如下:
(9)
公式(8b)确保任务只能被执行一次;公式(8c)确保资源负载不大于1, 即业务过程能稳定执行,其中的ldr为业务过程每执行一次资源r需要服务的时 间;公式(8d)为任务分配率的取值范围;公式(8e)为资源配置数量的取值范 围,其中Mr为资源配置数量的上限,计算如下:
上述数学模型中的决策变量是资源配置方案,包括资源配置数量r.qnt和分配 给资源的任务分配率ξa,r,该数学模型的最优解即为能保证业务过程稳定执行条 件下,执行成本最小的资源数量配置和任务分配优化方案。
所述数学模型是一个线性的混合整数规划问题,使用Matlab软件的YALMIP 优化工具箱进行求解。当然,也可以采LINGO优化软件或一些智能计算方法(如: 遗传算法、模拟退火算法、粒子群算法、蚁群算法等)来求解。
相对于现有的面向成本的业务过程资源配置优化方法,本发明的有益效果主 要表现在:(1)把资源数量配置和任务分配集成在一起进行优化,同时考虑了资 源与活动之间多对多的支持关系及在这种关系中存在的不同资源处理相同活动实 例和同一资源处理不同活动实例的效率可能是不同的问题;(2)采用基于活动和 资源相结合的业务过程执行成本计算方法,除了考虑资源的固定成本外还考虑了 资源的各种可变成本和活动执行时不依赖于资源的自身成本因素。从而使该方法 更具通用性和柔性,能更好地适应实际复杂业务过程面向成本的资源配置优化需 求。
附图说明
图1是活动与活动之间的逻辑控制关系,其中,(a)为顺序(Sequence),(b) 为循环(Iteration),(c)为与分叉(And-Split),(d)为与汇合(And-Join),(e) 为或分叉(Or-Split)、(f)为或汇合(Or-Join)。
图2是从实际业务过程抽象出来的过程模型逻辑结构示意图。
具体实施方式
下面结合附图对本发明做进一步说明。
参照图1和图2,一种面向业务过程执行成本最小化的集成资源数量配置和 任务分配优化方法,采用集合理论等形式化建模方法建立面向成本和资源配置分 析优化的业务过程模型,采用数值化分析优化技术建立面向业务过程执行成本最 小化的集成资源数量配置和任务分配优化的数学模型,并使用Matlab软件的 YALMIP优化工具箱进行求解。所述测定方法包括以下步骤:
第一步:建立业务过程模型
实际业务过程/工作流由多个逻辑相关的活动组成,活动的执行需要资源的 支持。其中活动与活动之间的逻辑控制关系包括顺序(Sequence)、循环(Iteration)、 与分叉(AND-Split)、与汇合(AND-Join)、或分叉(OR-Split)、或汇合(OR-Join)、 等逻辑控制关系,如图1所示。资源与活动之间的支持关系是多对多的,即一种 活动的任务可以由不同的资源来完成,一种资源也可以承担执行不同活动的任务。
将所述业务过程模型定义为一个6元组其中:
(1)是过程实例/服务对象的到达速率;
(2)A是业务过程中活动节点(简称活动)的集合,其元素a为活动编号, 能被进一步描述为a=(nm,ftm,fct,vct),其中:nm是活动名称,ftm是活动固有 执行时间,fct是活动每执行一次时所需的固定成本,vct是活动的可变成本,即 活动执行的单位时间成本,与活动执行时间成正比;
(3)C是业务过程中连接点的集合。其元素c为连接点编号,能被进一步描 述为c=(nm,ty,lc),其中:nm是连接点名称,ty连接点类型,lc连接点逻辑。 c.ty∈{″Split″,"Join"},c.lc∈{″And","Or"}。令N=A∪C为业务过程模型节点(简 称节点)的集合,n∈N,则|·n|表示节点n的前序节点的个数,|n·|表示节点n的 后继节点的个数;若(|·n|=1)∧(|n·|>1),则n∈C∧n.ty="Split";若 (|·n|>1)∧(|n·|=1),则n∈C∧n.ty="Join";存在唯一的逻辑节点ns∈N,|·ns|=0, 称为开始逻辑节点,存在唯一的逻辑节点ne∈N,称为结束逻辑节点。
(4)是业务过程中连接弧的集合。其元素l为 连接弧编号,能被进一步描述为l=(nm,inid,otid,prb),其中:nm是连接弧名称, inid是输入节点编号,otid是输出节点编号,prb是执行概率。若n1,n2∈N,则 l=<n1,n2>表示从节点n1到节点n2的连接弧,l.inid=n1,l.otid=n2。若 则l.prb=1;若l∈{<c,n>|c.lc="Or″∧|c·|>1},则
(5)R是业务过程中资源节点(简称资源)的集合,其元素r为资源编号, 能被进一步描述为r=(nm,qnt,fct,vct1,vct2),其中:nm是资源名称,qnt是资源 数量,fct是单位资源单位时间的固定成本,与资源的使用与否无关,而与资源 的存在/折旧时间有关,vct1是资源的单位资源单位时间可变成本,即单位资源在 单位时间的使用成本,与使用的时间成正比,vct2是单位资源的单位次数可变成 本,即每使用一次的成本,不依赖于使用时间,而依赖于使用次数。
(6)是业务过程中资源与活动支持关系(资源调用)的集合。 u=<a,r>表示资源r有能力处理活动a的任务。其元素u是支持关系(资源调用) 编号,能被进一步描述为u=(nm,aid,rid,tap,st),其中:nm是支持关系/调用名 称,aid活动编号,rid是资源编号,tap是活动a的任务产生后分配给资源r去执 行的概率,st是资源r处理活动a的平均服务时间。令u.tap=ξa,r,由于任务只能被执行一次,故有:
在业务过程模型中定义节点的期望执行率为业务过程执行一次时节点期望执 行的次数。顺序(Sequence)、循环(Iteration)、与分叉(And-Split)、与汇合 (And-Join)、或分叉(Or-Split)、或汇合(Or-Join)逻辑控制关系中各节点的期 望执行率有如下计算关系:
在图1(a)所示的顺序逻辑控制关系中,有:
fa1=…=fan (1)
其中:fa1,…,fan分别为活动a1,…,an的期望执行率。
在图1(b)所示的循环逻辑控制关系中,有:
for=fa1 (2)
fa2=fa1(1-p) (3)
其中:p为退出循环的概率,fa1,fa2分别为活动a1,a2的期望执行率,fOr为 连接点“Or”的期望执行率。
在图1(c)所示的与分叉(And-Split)逻辑控制关系中,有:
fAnd=fa1=…=fan (4)
其中:fa1,…,fan分别为活动a1,…,an的期望执行率,fAnd为连接点“And”的期 望执行率。
在图1(d)所示的与汇合(And-Join)逻辑控制关系中,有:
fAnd=fa1=…=fan (5)
其中:fa1,…,fan分别为活动a1,…,an的期望执行率,fAnd为连接点“And”的期 望执行率。
在图1(e)所示的或分叉(Or-Split)逻辑控制关系中,有:
fai=fOr·pi,i=1,2,…,n (6)
其中:pi=<Or,ai>.prb是各分支的执行概率,fa1,…,fan分别为活动a1,…,an 的期望执行率,fOr为连接点“Or”的期望执行率。
在图1(f)所示的或汇合(Or-Join)逻辑控制关系中,有:
其中:fa1,…,fan分别为活动a1,…,an的期望执行率,fOr为连接点“Or”的期 望执行率。
然后,根据以上计算关系从开始节点计算业务过程模型中所有活动节点的期 望执行率,开始节点的期望执行率为1。
第二步:建立面向业务过程执行成本最小化的资源配置优化的数学模型及其求解
目标函数:
约束条件:
0≤ξa,r≤1,
r.qnt=0,1,…,Mr,
公式(8a)为要优化的目标函数,其中的βp为业务过程单位时间执行成本, βa为业务过程每执行一次(完成一个过程实例)活动a需要花费的成本,其计算 如下:
(9)
公式(8b)确保任务只能被执行一次。公式(8c)确保资源负载不大于1, 即业务过程能稳定执行,其中的ldr为业务过程每执行一次(完成一个过程实例) 资源r需要服务的时间。公式(8d)为任务分配率的取值范围。公式(8e)为资 源配置数量的取值范围,其中Mr为资源配置数量的上限,计算如下:
上述数学模型中的决策变量是资源配置方案,包括资源配置数量r.qnt和分配 给资源的任务分配率ξa,r(任务分配方案)。该数学模型的最优解即为能保证业务 过程稳定执行条件下,执行成本最小的资源数量配置和任务分配优化方案。该数 学模型是一个线性的混合整数规划问题,可使用Matlab软件的YALMIP优化工 具箱进行求解。当然,也可以采LINGO优化软件或一些智能计算方法(如:遗 传算法、模拟退火算法、粒子群算法、蚁群算法等)来求解。
图2是从实际业务过程抽象出来的过程模型逻辑结构示意图,其形式化的过 程模型可定义为一个6元组其中:
(1)过程实例的到达速率为:
(2)活动集合:
A={a1,a2,a3,a4,a5,a6,a7,a8};其中:a1=(a1,8,1,1),a2=(a2,0,0,0), a3=(a3,0,0,0),a4=(a4,0,0,0),a5=(a5,0,2,0),a6=(a6,0,0,1), a7=(a7,0,0,0),a8=(a8,6,4,2)。
(3)连接点集合:
C={c1,c2,c3,c4,c5,c6};其中:c1=(c1,"Split″,"And"), c2=(c2,"Split","Or"),c3=(c3,"Join","Or"),c4=(c4,"Join","Or"), c5=(c5,"Split″,"Or"),c6=(c6,"Join","And")。
(4)连接弧集合:
L={l1,l2,l3,l4,l5,l6,l7,l8,l9,l10,l11,l12,l13,l14,l15,l16},其中: l1=(l1,a1,c1,1),l2=(l2,c1,a2,1),l3=(l3,a2,c2,1),l4=(l4,c2,a3,0.4), l5=(l5,c2,a4,0.6),l6=(l6,a3,c3,1),l7=(l7,a4,c3,1),l8=(l8,c3,a6,1), l9=(l9,a6,c6,1),l10=(l10,c1,a5,1),l11=(l11,a5,c4,1),l12=(l12,c4,a7,1), l13=(l13,a7,c5,1),l14=(l14,c5,c4,0.2),l15=(l15,c5,c6,0.8),l16=(l16,c6,a8,1)。
(5)资源集合:
R={r1,r2,r3,r4};其中:r1=(r1,?,20,5,0),r2=(r2,?,30,7,0), r3=(r3,?,25,6,0),r4=(r4,?,22,6,0)。“?”为要求的资源配置数量r.qnt。
(6)资源与活动支持关系(资源调用)的集合:
U={u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11,u12,u13,u14,u15,u16,u17,u18,u19}, 其中:u1=(u1,a1,r1,?,14),u2=(u2,a1,r2,?,8),u3=(u3,a1,r4,?,8), u4=(u4,a2,r3,?,6),u5=(u5,a2,r4,?,14),u6=(u6,a3,r1,?,8), u7=(u7,a3,r3,?,5),u8=(u8,a4,r2,?,12),u9=(u9,a4,r4,?,6), u10=(u10,a5,r2,?,8),u11=(u11,a5,r3,?,12),u12=(u12,a6,r1,?,10), u13=(u13,a6,r4,?,18),u14=(u14,a7,r1,?,12),u15=(u15,a7,r2,?,4), u16=(u16,a7,r3,?,8),u17=(u17,a8,r2,?,2),u18=(u18,a8,r3,?,4), u19=(u19,a8,r4,?,3)。“?”为要求的任务分配率ξa,r。
根据业务过程模型逻辑控制关系,由公式(1)-(7)从开始节点a1(开始 节点的期望执行率为1)可计算出业务过程中所有活动节点的期望执行率,计算 结果如下:fa1=1,fa2=1,fa3=0.4,fa4=0.6,fa5=1,fa7=1.25,fa8=1。
根据业务过程模型提供的以上信息,由公式(8)-(10)可建立如下面向业 务过程执行成本最小化的资源配置优化数学模型:
目标函数:
minβp=0.5×(27+84ξa1,r1+64ξa1,r2+56ξa1,r4+36ξa2,r3+84ξa2,r4+16ξa1,r1+12ξa1,r3+50.4ξa4,r2+21.6ξa4,r4+56ξa5,r2+72ξa5,r3+60ξa6,r1+126ξa6,r4+75ξa7,r1+35ξa7,r2+60ξa7,r3+18ξa8,r2+32ξa8,r3+24ξa8,r4) +20r1.qnt+30r2.qnt+25r3.qnt+22r4.qnt
约束条件:
ξa1,r1+ξa1,r2+ξa1,r4=1
ξa2,r3+ξa2,r4=1
ξa3,r1+ξa3,r3=1
ξa4,r2+ξa4,r4=1
ξa5,r2+ξa5,r3=1
ξa6,r1+ξa6,r4=1
ξa7,r1+ξa7,r2+ξa7,r3=1
ξa8,r2+ξa8,r3+ξa8,r4=1
ldr1=(14ξa1,r1+3.2ξa3,r1+10ξa6,r1+15ξa7,r1)/r1.qnt≤2
ldr2=(8ξa1,r2+7.2ξa4,r2+8ξa5,r2+5ξa7,r2+2ξa8,r2)/r2.qnt≤2
ldr3=(6ξa2,r3+2ξa3,r3+12ξa5,r3+10ξa7,r3+4ξa8,r3)/r3.qnt≤2
ldr4=(8ξa1,r4+14ξa2,r4+3.6ξa4,r4+18ξa6,r4+3ξa8,r4)/r4.qnt≤2
0≤ξa1,r1≤1,0≤ξa3,r1≤1,0≤ξa6,r1≤1,0≤ξa7,r1≤1
0≤ξa1,r2≤1,0≤ξa4,r2≤1,0≤ξa5,r2≤1,0≤ξa7,r2≤1,0≤ξa8,r2≤1
0≤ξa2,r3≤1,0≤ξa3,r3≤1,0≤ξa5,r3≤1,0≤ξa7,r3≤1,0≤ξa8,r3≤1
0≤ξa1,r4≤1,0≤ξa2,r4≤1,0≤ξa4,r4≤1,0≤ξa6,r4≤1,0≤ξa8,r4≤1
r1.qnt=0,1,…,22
r2.qnt=0,1,…,16
r3.qnt=0,1,…,17
r4.qnt=0,1,…,24
使用Matlab软件中的YALMIP优化工具箱进行求解的程序如下:
x=sdpvar(1,11);%定义决策变量:任务分配率
y=intvar(1,4);%定义决策变量:资源配置数量
%以下的F为约束条件
F=set(0<=x<=1);
F=F+set(0<=1-x(1)-x(5)<=1);
F=F+set(0<=1-x(4)-x(8)<=1);
F=F+set(0<=1-x(9)-x(11)<=1);
F=F+set(0<=y(1)<=22);
F=F+set(0<=y(2)<=16);
F=F+set(0<=y(3)<=17);
F=F+set(0<=y(4)<=24);
F=F+set(14*x(1)+3.2*x(2)+10*x(3)+15*x(4)-2*y(1)<=0);
F=F+set(8*x(5)+7.2*x(6)+8*x(7)+5*x(8)+2*x(9)-2*y(2)<=0);
F=F+set(6*x(10)+2*(1-x(2))+12*(1-x(7))+10*(1-x(4)-x(8))+4*x(11)-2*y(3) <=0);
F=F+set(8*(1-x(1)-x(5))+14*(1-x(10))+3.6*(1-x(6))+18*(1-x(3))+3*(1-x(9)- x(11))-2*y(4)<=0);
f=0.5*(27+84*x(1)+64*x(5)+56*(1-x(1)-x(5))+36*x(10)+84*(1-x(10))+16*x (2)+12*(1-x(2))+50.4*x(6)+21.6*(1-x(6))+56*x(7)+72*(1-x(7))+60*x(3)+1 26*(1-x(3))+75*x(4)+35*x(8)+60*(1-x(4)-x(8))+18*x(9)+32*x(11)+ 24*(1-x(9)-x(11)))+20*y(1)+30*y(2)+25*y(3)+22*y(4);%f为目标函数
solvesdp(F,f) %调用solvesdp()函数求最优解及最优的目标函数值
double(f) %显示最优的目标函数值
double(x) %显示最优的任务分配率
double(y) %显示最优的资源配置数量
以上程序运行求解的结果如下:
f=725.0333;x(1)=0,x(2)=0.5500,x(3)=1,x(4)=0,x(5)=0,x(6)=0, x(7)=0.9083,x(8)=1,x(9)=0.8667,x(10)=1,x(11)=0;y(1)=6,y(2)=7, y(3)=4,y(4)=6。
即资源数量配置优化方案为:
r1.qnt=y(1)=6,r2.qnt=y(2)=7,r3.qnt=y(3)=4,r4.qnt=y(4)=6;
对应的任务分配优化方案为:
ξa1,r1=x(1)=0,ξa1,r2=x(5)=0,ξa1,r4=1-x(1)-x(5)=1,ξa2,r3=x(10)=1, ξa2,r4=1-x(10)=0,ξa3,r1=x(2)=0.5500,ξa3,r3=1-x(2)=0.4500, ξa4,r2=x(6)=0,ξa4,r4=1-x(6)=1,ξa5,r2=x(7)=0.9083,ξa5,r3=1-x(7)=0.0917, ξa6,r1=x(3)=1,ξa6,r4=1-x(3)=0,ξa7,r1=x(4)=0,ξa7,r2=x(8)=1, ξa7,r3=1-x(4)-x(8)=0,ξa8,r2=x(9)=0.8667,ξa8,r3=x(11)=0, ξa8,r4=1-x(9)-x(11)=0.1333。
在此资源优化配置(资源数量优化配置和任务分配优化方案)下,业务过程 能稳定执行,且单位时间内的执行成本最小,其值为:
minβp=f=725.0333。
机译: 任务分配优化系统,任务分配优化方法和任务分配优化程序
机译: 任务分配优化系统,任务分配优化方法以及存储任务分配优化程序的非暂时性计算机可读介质
机译: 任务分配优化系统,任务分配优化方法和任务分配优化程序