基于协作相容性的工作流任务分配优化方法

胡海洋1,2,3姬朝配1胡 华1,2葛季栋3

1(杭州电子科技大学计算机学院 杭州 310018)

2(复杂系统建模与仿真教育部重点实验室(杭州电子科技大学) 杭州 310018)

3(计算机软件新技术国家重点实验室(南京大学) 南京 210046)

(huhaiyang@hdu.edu.cn)

工作流系统中任务分配策略将对其系统运行性能有很大的影响,在分配任务时不仅需要考虑执行者对相应任务的熟悉度,还需分析执行者之间配合协作的默契程度.传统研究工作在进行工作流任务分配时缺乏对执行者工作负载、执行者之间协作相容性的综合考虑.为了实现有效的任务分配,首先通过分析历史日志的信息,对执行者间的协作相容性进行分析计算,在此基础上综合考虑执行者当前的任务负载,提出了基于协作相容性的、负载均衡式任务分配模型,并给出了多目标联合优化的任务分配方法,可提高整个流程实例的执行效率,并保持执行者间的负载均衡.提出4种相应的算法,并分析了算法的时间复杂度,进行了系统性的对比实验,评估了所提出方法的正确性和有效性.

关键词工作流;任务分配;协作相容性;负载均衡;任务交互

在工作流调度中,各任务由工作流引擎调度系统中的资源来操作完成.由于不同的任务分配策略将对工作流管理系统的性能有很大的影响[1],因此需要制定良好的任务分配优化策略,将各任务分配给合适的资源.根据应用领域的不同,工作流系统中的资源可以是人力资源、设备仪器资源、应用程序或网络资源等.其中人力资源在工作流系统中起着重要的作用,他们一般是指具有特定技能的任务执行者,通过相应的角色(role)彼此配合与协作,在工作流系统中调度各类计算资源完成任务.在现代企业中,任务执行者常可承担多类角色用于完成多种任务[2],其对完成不同类型任务常可具有不同的熟悉程度,并且不同人员之间配合协作的默契程度也存在着差异.

任务执行者完成任务的技能熟悉度、彼此间协作的默契度对整个业务过程顺利、高效执行起着重要作用.然而,现有的任务分配算法仅考虑候选执行者的专业能力、兴趣、经验、负载等,忽略了工作流中任务交互时执行者之间的协作相容性.这样的协作相容性可以定义为:“和其他人的凝聚力、熟悉度,和谐、配合度等[2]”.例如一个典型的医疗索赔流程(如第2节中的图1所示),几个任务以确定的顺序分配给几个角色执行.当一个角色完成分配的任务并提交给下一个任务的执行者执行时,2个执行者之间可能会存在一些交互以询问和验证一些信息.在这样的任务交互过程中,执行者之间的协作相容性影响着工作的高效性.例如有2个员工甲、乙均可完成某个任务,并且甲的个人能力强于乙,然而甲对公司里其他员工的配合并不默契,当工作流中的任务需要员工之间进行交互时,甲的整体工作效率可能反而低于乙的整体效率.

此外,在工作流系统实际过程中,由于存在着多个流程实例,并且各实例到达时间有一定的随机性,候选执行者的工作列表中常存在多个等待处理的任务.在此情形下,一个满负载的执行者很难及时完成所分配的工作流任务.由于执行者当前所有的任务负载情况将对分配任务的最后完成时间有着很大的影响,因此工作流系统在分配任务过程中需考虑到各个任务执行者当前的工作负载情况,即尽可能将任务分配给轻负载(light-loaded)的执行者,从而提高整个工作流系统的性能.

现有的一部分研究工作通过将任务执行者的专业能力、任务成功率、兴趣度、经验等因素转化为模糊数[3-5],并对各影响因素分配一个权重因子,在任务分配时选择综合分数最高的候选者进行分配,但没有认识到任务间存在交互的情形下执行者之间协作的配合度影响.而有些研究尽管考虑了任务分配时上下文环境中任务执行者的一些社会关系、配合度等对任务执行时间的影响[6-9],然而却仅局限于连续的2个任务之间的配合度,同时也没有考虑到多实例同时到达的情况下任务执行者工作负载方面的影响.

为了解决以上问题,本文引入了执行者间协作相容性对任务分配影响的内容,通过结合历史日志的信息,对执行者间的协作相容性及任务负载进行了分析计算.在此基础上,给出了任务分配问题的优化建模,提出了基于协作相容性与负载均衡的任务分配算法,提高了整个流程实例的执行效率.

1相关工作

在工作流调度中基本上任务分配策略是基于角色或组织模型[1].它仅仅考虑了资源的角色而没有区分自动型任务和用户型任务.研究者们通过人的属性扩展了这一概念,例如文献[2]基于流程任务间可能存在的交互,通过一个启发式算法,在任务分配时选择整个实例中合作协作相容性之和最大的执行者执行任务.文献[3]提出了一种多准则评估模型算法,根据候选者的能力、社会关系和任务属性进行任务分配,但对社会关系如何影响候选者的能力问题没有说明.文献[4]中提出了一种自主工作流任务分配策略,为任务分配带来了更多的自主权.

Fig. 1 A process flow of medical insurance claim
图1 一个医疗保险索赔流程

文献[5]在研究任务分配时考虑了更多因素(如任务重要性、任务类型、能力、负载、经验),并用模糊理论讨论了关于每一因素权重的大小表示该因素的影响程度;文献[6-7]证明了基于优化社会关系的任务团队组建,如团队的凝聚力等,将使工作流中的任务更加高效地执行;文献[8]提出了一种基于社会关系矩阵处理多实例的任务分配问题;文献[9]采用隐Markov建模,通过基于候选者任务执行能力和日志中挖掘的连续任务的交互关系,并通过Viterbi算法解决任务分配问题;文献[10]提出了一种基于Q学习的任务分配算法,且在任务分配时考虑了社会关系的影响,缩短了实例的平均执行时间.然而,以上5种方法考虑的社会关系仅仅局限于连续任务的前置执行者,忽略了工作流中非连续任务之间存在交互时社会关系的影响,也未能充分考虑到执行者间的负载均衡.

此外文献[11]在任务分配时不仅考虑到当前待分配任务的候选者,也考虑整个实例执行中合作候选者间的依赖关系,优先选择历史合作次数最多的执行者.然而,他们都没有考虑到候选者的负载情况.文献[12]在任务分配时不仅考虑了任务候选者的个体属性,而且考虑了工作流中前一任务执行者对当前候选者的影响,改进了传统的最短处理时间、最短完成时间、平均工作负载和最短工作列表这4种任务分配算法,但同样没有充分考虑到工作流任务分配中的执行者工作负载均衡问题.文献[13-15]提出的动态任务分配策略,主要考虑了众包(crowdsourcing)执行环境中任务执行候选者在任务分配时的当前状况,具有一定的现实意义.文献[16]将机器学习算法用于工作流事件日志,在任务执行时根据算法生成的分类器推荐一个合适的执行者,以半自动的方法减少手动员工分配.文献[17-19]提供了解决任务分配问题的一个基本框架,但忽略了任务候选者之间社会关系的影响,也没有考虑到同时到达多实例时的情形.

综上所述,在任务分配时大多数的任务分配算法仅考虑候选执行者的个体能力属性,没有认识到工作流中不同任务交互时执行者之间的协作相容性对流程性能的影响.本文提出的基于协作相容性的任务均衡分配算法,不仅考虑了执行者当前的工作负载,而且考虑了流程实例运行中任务交互时候选者之间的协作相容性,更好地体现了工作流系统的实际运行情况.

2基于协作相容性的任务均衡分配模型

2.1问题描述和基本框架

本文通过一个具体实例来阐释相关问题.如图1所示的一个医疗保险索赔流程[2],该工作流程涉及索赔的受理(receiving)、材料的验证(validating)、理算(settlement)、审批签字(approving)和付款(payment)等任务处理过程,每个任务由不同角色执行的同时又有不同的交互.

该流程运行时,1)客服代表(customer staff)对医疗保险索赔进行记录并将由审查人员(reviewer)进行理赔调查或体检;2)评估人员(evaluator)根据审查人员所提供的信息进行索赔理算(settlement);3)经理(manager)对收到的赔偿款项进行签字确认;4)财务人员(accountant)将相应款项转入客户账户.

由于每一任务的角色可能处于不同的物理位置,使得任务执行过程中协作相容性的需求较大.在图1中,各任务上面的圆弧状虚线,表示执行不同任务的角色可能需要进行信息的交互.例如,收到索赔后,审查员可能需要客户服务代表澄清关于某些缺失的索赔信息(如发生事故的确切位置或事件的时间丢失).同样,评估员可能需要咨询审查员关于事故信息的更多细节.最后,财务会计人员可能会在付款之前咨询审查员说明一些支付选项不明的信息(如签字无效等).

因此,这里我们考虑的任务分配问题的场景如下:1)我们要考虑候选任务执行者的任务负载情况,即在分配时优选相对轻载的执行者;2)由于整个实例中不同任务可能存在交互的情况,不同执行者合作时所需的时间开销不同,因此任务分配时还需考虑执行者之间的协作相容性.任务执行者之间的协作相容性越高,交互时所需的时间越少.由于执行者可具备多种角色,即具有执行多种任务的能力,若任务分配时仅考虑优化协作相容性(我们假设一个执行者与自身的协作相容度最大),会导致多个任务分配给同一个执行者,这样大大增加该执行者的工作负载,因此,这2个优化目标之间存在一定的冲突.为了解决这个问题,我们提出了一个基于协作相容性的任务均衡分配基本框架(如图2所示).

Fig. 2 Framework for tasks allocation based on cooperation capability
图2 基于协作相容性的任务均衡分配基本框架

基于该框架,任务分配的确定过程如下:

1) 根据任务候选执行者之间相对预测负载大小(相关定义在2.2节中给出),将候选执行者划分为轻负载、中负载和重负载3个区间.同一区间内的候选者具有相似的负载.而在具体应用中,对候选者的相对预测负载区间数量和参数的设置,可根据工作环境的实际状况进行灵活调整;

2) 选择轻载区间内的候选者作为待分配任务的新候选者集合;

3) 根据具体任务之间的交互情形,从每一个任务的新候选者集合中,选择一个具有能力执行该任务且同时能最大化交互任务中执行者之间的协作相容性.

在工作流任务分配过程中,本文所做4点假设:

1) 工作流中所有任务候选者之间的协作相容性独立于具体的任务,且执行者之间的协作相容性具有对称性.

2) 执行者间的协作相容性与交互时所需时间成正比,即2个任务执行者间的协作相容性越好,任务执行时交流信息花费的时间越小.

3) 工作流运行过程中执行者总负载包括2部分:任务执行负载、与其他执行者交互所需的负载.其中,任务执行负载是当前预分配任务及执行者的工作列表中所有等待执行任务的负载.

4) 执行者对其工作列表中的任务进行处理时采用“先进先出”方式.

2.2最优任务分配模型

根据图2中的基本框架,本节将给出具体的计算模型;为了方便描述和分析,表1给出了本文所使用的一些基本符号与定义.

我们用执行者完成其工作队列中所有任务所需的时间来表示他的工作负载.

定义1. 执行者uk当前工作列表中等待处理的任务集为TAk,且执行任务TiTAk所需要时间为若工作列表中等待处理的任务Tini个,则uk的当前负载为

定义2. 设执行者uk当前负载为wcur(uk),若任务Ti即将分配给他,则uk的预测负载为

定义3. 设待分配的任务Ti的候选执行者集合为CEi={uk},且执行uk的预测负载为wpred(uk),则将候选执行者的负载进行归一化处理后可得到uk的相对预测负载为

为各执行者的平均工作负载,则执行者间的负载均衡情况可通过标准差来表示:

(1)

Aik标识任务Ti是否被分配给执行者ukcpij标识任务TiTj需要交互,则工作流任务分配时执行者间发生交互时的总协作相容度可表示为

(2)

我们的目标是在分析执行者任务负载均衡的基础上,进一步通过使待分配任务的执行者与流程中各交互任务的执行者之间总体协作相容性最大,从而提高系统运行的效率.该任务分配问题可以描述成一个多目标整数线性规划问题:

max(CW,WL-1),

AikXik,1≤in,1≤km,

Xik∈0,1,1≤in,1≤km

(3)

其中,对WL-1值的最大化即相当于对WL值的最小化.约束条件表明工作流实例中每个任务Ti都应该分配唯一的执行者uk.约束条件AikXik(Xik的定义如表1所示)表明每个任务必须被分配给有能力完成它的候选执行者.

尽管式(3)是一个整数的线性规划问题,可以使用数学优化工具(如CPLEX)计算得出最优的分配方法,然而由于问题的规模,这是非常耗时的.因此,在后面我们首先给出计算执行者间协作相容性的方法,然后提出贪心算法,求解任务分配过程的局部最优解.

Table1DefinitionsofNotations
表1相关符号与定义

NotationDefinitionTask={Ti}The set of tasks in workflow systemU={ui}The set of executors in workflow system MCP={cpij}The set of interaction tasks with cpij∈{0,1}:if Ti has interaction with Tj,cpij=1;otherwise cpij=0MX={Xik}The set of roles that an executor can take on,where Xik∈{0,1}:if executor uk can take on the role of performing task Ti,Xik=1;otherwise Xik=0MCW={cwij}The set of cooperation capability among executors where cwij∈[0,1] denotes the amount of cooperation capability be-tween executor ui and uj.tikThe time needed by executor uk for completing task Tim=|U|The number of executorsn=|Task|The number of tasksMA={Aik}The set of task assignments in which if task Ti is assigned to executor ui,Aik=1;otherwise Aik=0 WL,WM,WHWL,WM and WH represents the set of executors that currently have light,medium and heavy amount of workload,respec-tively.

2.3执行者间协作相容性

当工作流中的任务之间需要交互时,任务执行者间的高协作相容性可以加快他们信息的交流,提高任务执行的速度.一些电子商务网站如Epinions.com,Slashdot.org等通过询问用户记录成员之间的协作相容性来建立员工之间的信任网络或黑名单.然而,由于员工之间的协作相容性属于个人隐私,从而使得这种通过访问的方式来记录彼此间的协作相容性是非常不合适的.

根据任务执行者合作的多样性,本文主要通过工作流日志里执行者间协作完成流程的时间来度量他们的协作相容性,主要思想如下:对于发生交互的任意2个任务,计算进行协作的2个执行者之间平均吞吐时间与最小执行时间的差值,相对于2个任务中最多与最少的执行时间的差值比值,则该比值越小,协作相容性越大.协作相容性计算为

(4)

其中,cwkv表示uk,uv的协作相容性;tavg表示ukuv配合时执行流程的平均吞吐时间;tmin表示流程的最小完成时间;tmax表示流程的最大完成时间;0<ω<1.显然,由式(4)所得的任务执行者之间的协作相容性取值范围为cwkv∈[0,1].例如,假设基于图1的一个流程日志解析得到的部分执行信息如表2所示:

Table2PartsofLogInformation
表2部分日志信息

CaseIDReceivingValidatingSettlementTime Needed∕min1MaryJackJohn102MaryCarlJohn123MaryJackJohn11

由表2可得,流程的平均吞吐时间为tavg=(10+12+11)3=11 min,Mary和Jack配合时的流程平均完成时间为(10+11)2=10.5 min;流程的最大完成时间为12 min,最小完成时间为10 min;取ω=0.8,根据式(4)得:Mary和和Jack的协作相容性为0.8.同理可得,Mary和Carl的协作相容性为0.2.

3任务分配策略

为了阐述本文所给算法的适用场合和相关特点,我们首先给出3种单目标的贪心算法,分别针对候选执行者的期望任务负载(expected workload)最小化、流程中所有任务完成的期望完成时间(expected completed time)最短以及基于预测负载的协作相容性最大化;然后在此基础上提出了联合优化执行者负载均衡及执行者间协作相容性的相关算法.在后面的实验中,我们将从不同的角度分析对比这4种算法.

3.1期望任务负载最小化策略

执行者的期望任务负载最小化算法ESWL的主要思想是:每次在进行任务分配时,遍历所有具有执行该任务能力的候选执行者,从中选择期望任务负载最小的候选者执行相应任务.设在单位时间内系统分配给uk的平均任务数为mk(mk值可通过日志分析的方法近似获取[20]),令执行者uk当前待完成的任务集为TAk,则在uk完成任务集TAk的过程中,系统新分配给uk的新任务数近似为uk的期望任务负载为

下面给出期望工作负载最小化算法ESWL的执行过程:

算法1. ESWL算法.

输入: 执行者角色集合MX={Xik};

输出: 任务分配策略集MA={Aik}.

MA=∅;

② FOR each taskTiTaskDO

exp_workload=MAX_INT;k=0;

④ FOR eachujUDO

⑤ IF(Xij=1)

⑥ 计算uj的期望任务数λj

⑦ IF(λj<exp_workload)

exp_workloadλj

kj

⑩ END IF

END IF

END FOR

Aik=1;

END FOR

ESWL算法对流程中的每一个待分配任务,需要遍历所有的候选者,因此,其时间复杂度为O(mn),其中n是流程中任务的个数,m是所有执行者数.

3.2期望完成时间最短化策略

对于流程的期望完成时间最短算法ESCT,其主要思想是:在任务分配时,遍历所有具有执行该任务能力的候选者,考察当前的执行者完成及其所携带的工作列表,计算新任务完成的期望时间,期望时间最短的执行者将被挑选出,并将该任务分配给它.由于执行者uk可承担的任务集为Taskk={Ti|Xik=1,i=1,2,…,n},则uk完成任务的平均时间为

uk当前待完成的任务集为TAk,考虑到当uk完成TAk中任务时系统还会分配新任务,则uk完成任务的期望时间为

下面给出期望完成时间最短化算法ESCT的执行过程:

算法2. ESCT算法.

输入: 执行者角色集合MX={Xik};

输出:任务分配策略集MA={Aik}.

MA=∅;

② FOR each taskTiTaskDO

③ FOR eachujUDO

exp_time=MAX_INT;k=0;

⑤ IF(Xij=1)

⑥ 计算uj完成任务的期望时间γj

⑦ IF(γj<exp_time)

exp_timeγj;kj

⑨ END IF

⑩ END IF

END FOR

Aik=1;

END FOR

同样地,该算法对流程中的每一个任务,也需遍历所有的候选者.因此,时间复杂度为O(nm),其中n是流程中任务的个数,m是所有候选者的个数.

3.3协作相容性最大化策略

我们首先根据式(4)计算出执行者之间的协作相容性;然后在文献[2]的基础上,给出协作相容性最大化算法MCW的主要步骤如下:在任务分配时,遍历所有具有执行该任务能力的候选者,考察当前的执行者与所有交互任务的执行者协作相容性,从中选择协作相容性最大的执行者分配该任务.

下面给出协作相容性最大化算法MCW的算法伪码:

算法3. MCW算法.

输入: 执行者角色集合MX={Xik}、任务交互集合MCP={cpij}、执行者协作相容集合MCW={cwkv};

输出: 任务分配策略集MA={Aik}.

① FOR eachukUDO

② FOR eachuvUDO

③ 由式(4)计算ukuv间协作相容性cwkv的值;

④ END FOR

⑤ END FOR

⑥ FOR eachTiTaskDO

max_coop0;v0;

⑧ FOR eachukDO

⑨ IF(Xik=1)

max_coop[k]0;

FOR eachTjTaskTjTiDO

IF(cpi=1且Tj未分配)

*循环所有交互且未分配任务*

在集合中找出与任务Ti的执行者uk之间cwkv值最大的候选者uv

max_coop[k]max_coop[k]+cwkv

END IF

END FOR

END IF

END FOR

k*

Aik*1;

FOR eachTiTaskTjTiDO

IF(cpi=1且Tj尚未分配)

找出与uk*之间cwk*v最大的执行者uv,Ajv1;

END IF

END FOR

END FOR

如上所述,该算法对流程中的每一待分配任务,需要遍历所有的候选者及任务集合,用以找到与所有交互任务执行者之间的协作相容性.因此,时间复杂度是O(mn2).

3.4联合优化策略

我们将考虑在执行者负载相对均衡的基础上,且使得执行者间整体协作相容性最优的任务分配算法.在设计这样的分配算法MCLB时,需要考虑到流程中存在任务交互的情形,因此,算法需要3个输入集合:任务交互集合MCP={cpij}、执行者协作相容集合MCW={cwkv}及执行者角色集合MX={Xik}.在任务分配过程中,我们目标是在保持执行者间工作负载相对均衡的基础上,最大化整个流程中交互任务间的执行者协作相容性.为了实现这个目标,我们首先通过一个映射函数,将执行者之间的协作相容性值映射为任务交互时花费的时间,即对2个执行者而言,若他们的协作相容性越高,则彼此交互所需的时间越少.设2个执行者ukuv分别执行任务TiTj,他们之间协作相容性为cwkv,则他们交互时间开销可表示为

β

(5)

其中,β是协作相容性对时间映射的比例因子.对于任一执行者uk,若考虑将任务Ti分配给他,则任务Ti完成的预测时间为

wpred(uk)=wpred(uk)+

(6)

由于在任务分配过程中,当分配Ti时,可能存在着其他任务尚未被分配给任何执行者,因此,利用式(6)计算Ti分配策略时,我们仅考虑Ti与那些已分配好执行者的任务间的交互情形.

下面简述MCLB算法的执行流程:1)当分配流程实例中一个新任务Ti时,统计所有具备承担该任务角色的那些后续执行者,通过定义2、定义3计算他们当前的负载及相对预测负载值,依据相对预测负载值的大小依次将其放到对应的轻负载执行者集合中负载集合和重负载集合中(其中分别为系统设置的工作负载区间阈值,且判断新任务与流程其他任务间是否有交互,若无,则将该任务分配给相对预测负载值较小的候选者;否则,对流程中待分配的每个任务,依次遍历WLWM集合,找到可以执行Ti的候选者并且遍历所有与Ti需要交互任务,考察它们所有可能处于WLWM中的候选执行者,计算Ti的候选执行者与这些候选执行者间的协作相容性总和.3)找出可最大化全局协作相容性的任务候选者,并分配任务Ti,并将实例中与Ti有交互的其他尚未分配的任务分配给对应的执行者.重复以上步骤,直到所有任务已全部分配.

下面给出面向负载均衡的、最大化整体协作相容性的任务分配算法MCLB伪码:

算法4. MCLB算法.

输入: 执行者角色集合MX={Xik}、任务交互集合MCP={cpij}、执行者协作相容集合MCW={cwkv};

输出: 任务分配策略集MA={Aik}.

① FOR eachujUDO

② 由定义3计算

③ END FOR

④ 根据分别生成WL,WMWH

⑤ IF(!IsExistCoop(MCP))*判断是工作流程是否需要任务交互*

⑥ FORTiTaskDO

⑦ 利用ESWL算法找出当前期望负载最小的后续执行者uk

Aik1;

⑨ END FOR;

⑩ ELSE

FOR eachTiTaskDO

max_coop0;v0;

FOR eachukWLWMDO

IF(Xik=1)

max_coop[k]0;

FOR eachTiTaskTjTiDO

IF(cpi=1且Tj尚未分配)

*循环所有交互且未分配任务*

在集合WLWM中考察所有Tj的候选执行者{uv},找出cwkv值最大的候选者uv

max_coop[k]max_coop[k]+cwkv

END IF

END FOR

END IF

END FOR

k*

Aik*1;

FOR eachTiTaskTjTiDO

IF(cpi=1且Tj尚未分配)

考察集合WLWM中所有Tj的候选执行者{uv},找出cwk*v值最大的候选者uv

Ajv1;

END IF

END FOR

END FOR

END IF

函数IsExistCoop(MCP)判断输入的流程中是否存在任务交互.若流程中不存在任务交互时,时间复杂度为O(nm);当任务间存在交互时,该算法在任务分配时,对每一待分配任务,在遍历相对轻载的候选者集合时,还需在该可能候选者的基础上遍历其他所有可能交互的任务.因此,算法的时间复杂度是O(m2n2),其中n是任务的个数,m是所有候选者的个数.

3.5基于最优模型分配的一个例子

为了便于阐述上述方法,现给出了基于图1场景的一个简单例子.假设图1中每一任务的角色、执行者如表3所示:

Table3TaskRolesandCandidates
表3任务角色及候选者信息

TaskRoleCandidateReceivingCustomer StaffMary,SusanValidatingReviewerJack,CarlSettlementEvaluatorJohn,BethApprovingManagerTony,SamPaymentAccountantClare,Lin

其中,基于图1的任务交互矩阵如表4所示:

Table4MatrixofTaskInteraction
表4任务交互矩阵

TaskReceivingValidatingSettlementApprovingPaymentReceiving01100Validating10110Settlement11010Approving01101Payment00010

设执行者之间计算所得的协作相容性矩阵为表5所示:

Table5MatrixofCooperationCapability
表5协作相容性矩阵

Role(Task)Customer Staff(Receiving)Reviewer(Validating)Evaluator(Settlement)Manager(Approving)Accountant(Payment)MarySusanJackCarlJohnBethTonySamClareLinMary1.00.90.80.20.80.40.90.30.50.3Susan0.91.00.40.70.30.80.90.20.20.7Jack0.80.41.00.80.20.90.80.30.20.9Carl0.20.70.81.00.80.50.40.60.80.4John0.80.30.20.81.00.90.30.90.70.2Beth0.40.80.90.50.91.00.80.20.30.8Tony0.90.90.80.40.30.81.00.80.70.4Sam0.30.20.30.60.90.20.81.00.10.8Clare0.50.20.20.80.70.30.70.11.00.9Lin0.30.70.90.40.20.80.40.80.91.0

基于上面前提条件,则在运行时有如下情形:

1) 初始时所有候选者的工作列表为空,即任务候选者的待执行任务的负载为0;当到达第1个流程实例时,流程中所有任务的待候选者均为空闲(即都在轻载集合中).这时,通过最优分配模型,得到总体最大化协作相容性的任务分配情况如下:{receiving:Mary,validating:Jack,settlement:Beth,approving:Tony,payment:Clare}.总体协作相容性为:4.4.

2) 假设在某一时刻新的流程实例到达时,所有任务的候选者工作列表中都有等待完成的任务,即一定的工作负载,且通过估算执行者的预测负载及相对预测负载值,划分的新候选集合如下:WL={Mary,Susan,Carl,Clare,Lin};WM={John,Beth,Tony};WH={Jack,Sam}.

在任务分配时,首选我们考虑的是负载,将对应的轻载集合作为新任务的候选执行者集合.因此,首先从WL集合中搜索具备执行该任务角色的候选者,直到对应轻载集合搜索完为止,若未发现具备承担该任务角色的执行者,再依次搜索WMWH.例如在分配任务receiving时,由于该任务的2个候选执行者均在WL集合中,因此,候选执行者集合就为WL中的Mary,Susan.而在搜索任务validating的候选者集合时,WL中有一个可能的候选者Carl,则任务validating的候选执行者集{Carl}.通过以上候选执行者集合的确定,然后针对分配的可能情况,选择任务交互时执行者间协作相容性最大的进行相应分配,结果如下:{receiving;Susan,validating:Carl,settlement:Beth,approving:Tony,payment:Clare},总体协作相容性为3.9.

4

本节对ESWL,ESCT,MCW,MCLB这4种算法进行实验比较来分析各个方法的特点与性能.仿真采用的工作流顺序模型如图3所示:

Fig. 3 Workflow model
图3 工作流模型

在实验中,我们根据相对预测负载值设置轻负载、中负载、重负载区间,即WL=[0,0.34),WM=[0.34,0.67),WH=[0.67,1).首先使用ESWL算法,产生相应的工作流日志.根据所产生的工作流日志信息,计算任务执行者之间的协作相容性和执行者任务平均完成时间,将协作相容性值存入协作相容性矩阵;在工作流实例不同到达概率的情况下,使用不同的任务分配算法和相应能力配置进行仿真实验.对每一实例到达的概率,使用每种算法进行100次的仿真,并使用相同的实例队列和迭代次数在其他算法进行仿真,采取平均100次的仿真结果作为最终的结果进行分析.实验中工作流实例到达的概率服从二项分布.

各任务的处理时间设置如表6所示.在实验中,执行者可承担的角色设置为2种情况:任务执行者仅具备单一角色、任务执行者可具备多个角色的情况(如表7、表8所示);流程中任务间的交互情形又分为2种情况:任务间存在交互、任务间不存在任何交互(如表9、表10所示).通过结合执行者能力、负载以及任务交互的特点,仿真实验了所有4种可能情况下的结果.

Table6ProcessingTimeofTasks

表6任务处理时间min

TaskProcessing TimeT19T212T317T410T56

Table7EachExecutorHasaSingleRole
表7任务执行者仅具备单一角色

ExecutorT1T2T3T4T5u11u21u31u41u51u61u71u81u91u101

Table8EachExecutorCanHaveSeveralRoles
表8任务执行者可具备多个角色

ExecutorT1T2T3T4T5u11u211u311u411u51u61u71u811u91u101

Table9TasksHaveNoInteractions
表9任务间无交互情形

TaskT1T2T3T4T5T100000T200000T300000T400000T500000

Table10TasksHaveInteractions
表10任务间存在交互情形

TaskT1T2T3T4T5T101100T210110T311010T401101T500010

任务无交互情况下是在表7和表8配置下,结合表9进行仿真实验.实验结果如图4所示.通过观察图4(a)可以看出,4种算法下工作流实例完成时间几乎相同.这是由于在一个任务执行者仅具备单一角色且无任务交互时,其他3种算法的本质上是一样的,都是基于最小负载进行任务分配的,能够达到任务的均衡分配.MCW算法的任务执行者是随机分配的,没有考虑候选执行者实际的负载情形.通过观察图4(b),MCLB算法和ESCT算法完成时间几乎相同,ESWL和MCW算法略差且具有交叉性.这是由于在一个任务执行者可具备多个角色下,ESWL算法仅以期望任务负载作为任务分配的立足点,并不能正确地反映候选者的实际任务负载.仿真的结果表明,在没有任务交互的情况下,MCLB算法仍然取得了较好的性能.

Fig. 4 Completed time of workflow instances with no task interactions
图4 无任务交互情况下工作流实例的完成时间

我们现在考虑在工作流实例中任务有交互情况下,实验结果如图5所示.通过观察图5可以看出,在2种场景下,MCLB算法的结果都是最好的,MCW算法最差.这是由于存在任务交互时,MCLB算法不仅考虑了任务的负载,还考虑了交互任务执行者的协作相容性,一定程度上缩短了任务交互时的花费时间.而ESCT算法仅考虑了期望完成时间,ESWL算法仅仅考虑期望任务负载.尽管MCW算法考虑了任务候选者与前置所有任务候选者的协作相容性,但却忽略了多实例同时到达的场景,也即忽略了任务负载的影响.同时,从图5(a)和图5(b)的结果对比中可以发现,MCLB算法在后一种场景下的效果,要比前一种场景下的优势更大,这是由于实验中任务候选者增多时任务选择性变得更多.

Fig. 5 Completed time of workflow instances having task interactions
图5 存在任务交互情况下工作流实例的完成时间

下面我们考察任务执行者之间的协作相容性对工作流实例处理时间的影响.当工作流实例中的各任务间无交互情形时,4种任务分配算法中工作流实例的平均处理时间总是大小相等,即约为54 min;而当工作流任务存在交互情形时(如图6所示),4种任务分配算法的执行时间是不同的.使用MCW算法和MCLB算法时,工作流实例的平均处理时间总是优于其他2种算法.其中,图6(a)中,MCLB算法下工作流实例的平均处理时间比ESCT算法约少2 min,比ESWL算法约少3 min.图6(b)中,MCLB算法比ESCT算法约少2.5 min,比ESWL算法约少1.3 min.相比之下,MCW算法比ESCT算法约少5 min,比ESWL算法约少6 min.MCW算法下的平均处理时间最小的原因在于,它总是能够使当前任务执行者的协作相容性最大,尤其在任务执行者具备多个角色时,会将连续的多个交互任务分配给同一执行者.同时,通过将图6(a)和图6(b)的结果对比可以发现,在任务执行者可具备多个角色的情况下,使用ESCT算法得到的效率比ESWL算法要差.这是由于ESCT算法不能根据一个任务执行者可具备多个角色这一特点进行灵活地分配,造成前面任务候选者的选择严重影响后面其他任务的候选者选择情况.

我们现在分析在4种任务分配算法下任务执行者的负载均衡,其中执行者的总负载为所分配任务的总执行时间加上实际运行中交互时的花费时间.图7中给出了相关的实验结果.从图7(a)结果可以看出,当任务执行者仅具备单一角色时,MCLB算法能够使任务所有候选者的总负载相对均衡,而其他3种算法下任务候选者的负载情况相差较大.例如任务T3的候选者u5,u6,MCLB算法下u5u6多3.15%,ESWL算法下多13.26%,ESCT算法下多23.74%,而MCW算法下u5u6少68.04%.从图7(b)结果可以看出,一个任务执行者可具备多个角色时,MCLB算法同样能够均衡全局任务执行者的负载,而其他3种算法下任务的执行者负载不能保持相对均衡.例如T4的所有候选者有u7u8T5的所有候选者有u8u9u10.尽管u8可以同时执行2个任务,但MCLB算法下2个任务所有候选执行者的负载相对于其他算法,仍然具有较好的均衡效果.

Fig. 6 Average processing time of a workflow instance having task interactions
图6 存在任务交互情形时工作流实例的平均处理时间

Fig. 7 Workload for each executor when 20 instances having task interactions arrived per hour
图7 每小时到达20个实例时任务交互情况下执行者的工作负载

5

本文研究了基于协作相容性的工作流任务分配问题及算法.通过对工作流中任务之间的交互与否以及执行者之间的协作相容性对工作流性能的影响进行建模,并在考虑负载均衡的基础上,通过将交互任务的执行者协作相容性整体最大化以实现最终的任务分配,减少了流程实例的平均吞吐时间,提高了工作流的整体性能.通过实验得出,基于协作相容性的任务均衡分配方法对工作流中是否存在交互任务的情况均有良好的执行效率.

由于执行者之间协作相容性大小涉及的因素可能有很多,因此本文计算协作相容性的方法有待进一步细化.同时,由于具体的工作流流程有顺序、选择、并行结构,而本文只关注了顺序结构.因此,未来的研究包括3个方面:1)通过考虑更多的因素,进一步完善协作相容性的计算方法;2)考虑工作流中具有选择、并行结构时任务执行者间协作相容性的影响;3)考虑任务间存在转换概率时的协作相容性概率期望值.

参考文献

[1]Aalst W M P, Van Hee K M. Workflow Management: Models, Methods, and Systems[M]. Cambridge, MA: MIT Press, 2004

[2]Kumar A, Dijkman R, Song M. Optimal resource assignment in workflows for maximizing cooperation[G]LNCS 8094: Proc of the 11th Int Conf on Business Process Management. Berlin: Springer, 2013: 235-250

[3]Shen M, Tzeng G H, Liu D R. Multi-criteria task assignment in workflow management systems[C]Proc of the 36th Annual Hawaii Int Conf on System Sciences. Piscataway, NJ: IEEE, 2003: 1-9

[4]Chen Chuanbo, Zhao Weiwei. Strategy for a task assignment of workflow system[J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2005, 33(6): 20-22 (in Chinese) (陈传波, 赵伟伟. 一种自主工作流任务分配策略[J]. 华中科技大学学报: 自然科学版, 2005, 33(6): 20-22)

[5]Xiao Zhengjin, He Qinming, Chen Qi. A multilevel model of task assignment in fuzzy situations of workflow[J]. Journal of Computer Research and Development, 2007, 44(2): 302-309 (in Chinese)(肖郑进, 何钦铭, 陈奇. 模糊环境中工作流任务分配的多级模型[J]. 计算机研究与发展, 2007, 44(2): 302-309)

[6]Jordan M H, Feild H S, Armenakis A A. The relationship of group process variables and team performance a team-level analysis in a field setting[J]. Small Group Research, 2002, 33(1): 121-150

[7]Sanders K, Nauta A. Social cohesiveness and absenteeism the relationship between characteristics of employees and short-term absenteeism within an organization[J]. Small Group Research, 2004, 35(6): 724-741

[8]Bajaj A, Russell R. AWSM: Allocation of workflows utilizing social network metrics[J]. Decision Support Systems, 2010, 50(1): 191-202

[9]Lin S, Luo Z, Yu Y, et al. Effective team formation in workflow process context[C]Proc of the 2013 Int Conf on Cloud and Green Computing. Piscataway, NJ: IEEE, 2013: 508-513

[10]Yu Yang, Wang Ying, Liu Xingmei, et al. Workflow task assignment strategy based on social context[J]. Journal of Software, 2015, 26(3): 562-573 (in Chinese)(余阳, 王颍, 刘醒梅, 等. 基于社会关系的工作流任务分派策略研究[J]. 软件学报, 2015, 26(3): 562-573)

[11]Yang H, Wang C, Liu Y, et al. An optimal approach for workflow staff assignment based on hidden Markov models[G]LNCS 5333: Proc of OTM 2008 Workshops. Berlin: Springer, 2008: 24-26

[12]Xu J, Huang Z, Yu Y, et al. A performance analysis on task allocation using social context[C]Proc of the 2nd Int Conf on Cloud and Green Computing. Piscataway, NJ: IEEE, 2012: 637-644

[13]Ho C J, Vaughan J W. Online task assignment in crowdsourcing markets[C]Proc of the 26th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2012: 45-51

[14]Ho C J, Jabbari S, Vaughan J W. Adaptive task assignment for crowdsourced classification[C]Proc of the 30th Int Conf on Machine Learning. New York: ACM, 2013: 534-542

[15]Björnson E, Jorswieck E. Optimal resource allocation in coordinated multi-cell systems[J]. Foundations and Trends in Communications and Information Theory, 2013, 9(2): 113-128

[16]Liu Y, Wang J, Yang Y, et al. A semi-automatic approach for workflow staff assignment[J]. Computers in Industry, 2008, 59(5): 463-476

[17]Huang Z, Lu X, Duan H. A task operation model for resource allocation optimization in business process management[J]. IEEE Trans on Systems, Man and Cybernetics, Part A: Systems and Humans, 2012, 42(5): 1256-1270

[18]Menon A, Tamuz O, Gulwani S, et al. A machine learning framework for programming by example[C]Proc of the 30th Int Conf on Machine Learning. New York: ACM, 2013: 187-195

[19]Huang Z, Aalst W M P, Lu X, et al. Reinforcement learning based resource allocation in business process management[J]. Data and Knowledge Engineering, 2011, 70(1): 127-145

[20]Han Rui, Liu Yingbo, Wen Lijie, et al. A probabilistic approach to analyze and adjust time constraints in workflow management System[J]. Journal of Computer Research and Development, 2010, 47(1): 157-163 (in Chinese)(韩锐, 刘英博, 闻立杰, 等. 工作流管理系统中一种概率性分析和调整时间约束的方法[J]. 计算机研究与发展, 2010, 47(1): 157-163)

MethodforOptimizingTaskAllocationinWorkflowSystemBasedonCooperativeCompatibility

Hu Haiyang1,2,3, Ji Chaopei1, Hu Hua1,2, and Ge Jidong3

1(CollegeofComputerScience,HangzhouDianziUniversity,Hangzhou310018 )

2(KeyLaboratoryofComplexSystemsModelingandSimulation(HangzhouDianziUniversity),MinistryofEducation,Hangzhou310018)

3(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210046)

AbstractTask allocation strategy has an important influence on the performance efficiency of workflow system. When allocating tasks among executors, it needs to consider both the capability of each executor and the cooperative compatibility between the executors. Traditional methods for assigning tasks usually only consider the technical skills of executors and ignore the social cooperation compatibility among the executors. Although a few of research works have considered the social cooperation compatibility, they fail to consider how to maintain load balancing among executors when allocating the tasks. Based on the workflow log, cooperative compatibilities among executors are modeled and computed. The relations of interaction tasks are also taken into account. By analyzing the current workload of each executor, a multi-objective joint optimization framework for maintaining load balancing and maximizing the cooperative compatibility among executors is proposed. In this framework, when a new task is assigned, the current workload of each executor that can perform this task will be analyzed and its cooperation capability to other executors that have been assigned those tasks having interactions with this new task will be computed. Several corresponding algorithms are designed for optimizing different objectives and their time complexity is analyzed. Extensive experiments are conducted for comparing the proposed methods which demonstrate the correctness and effectiveness of our approaches.

Keywordsworkflow; task assignment; cooperation compatibility; load balancing; task interaction

This work was supported by the National Natural Science Foundation of China (61572162, 61272188, 61572251), the Foundation of Key Research Base for Philosophy and Social Sciences of Zhejiang Province (14JDXX04YB), the Natural Science Foundation of Jiangsu Province of China (BK20131277), the Fundamental Research Funds for the Central Universities (021714380004), the Foundation of State Key Laboratory for Novel Software Technology of Nanjing University (KFKT2014B15), and the Innovation Project of State Key Laboratory for Novel Software Technology of Nanjing University (ZZKT2013B14).

基金项目国家自然科学基金项目(61572162,61272188,61572251);浙江省哲学社会科学重点研究基地项目(14JDXX04YB);江苏省自科学基金项目(BK20131277);中央高校基本科研业务费专项资金项目(021714380004);南京大学计算机软件新技术国家重点实验室开放基金项目(KFKT2014B15);南京大学计算机软件新技术国家重点实验室创新项目(ZZKT2013B14)

修回日期:20160428

收稿日期20151222;

中图法分类号TP311

HuHaiyang, born in 1977. PhD and Professor. His main research interests include workflow system and parallel computing.

JiChaopei, born in 1987. Master. His main research interests include workflow system and business process management.

HuHua, born in 1964. Professor and PhD supervisor. His main research interests include workflow system and database theory.

GeJidong, born in 1978. PhD and associate professor. His main research interests include workflow system and business process management.