带时间惩罚的有向串并联图任务分配问题_胡淑珂.pdf

1引言任务分配问题是组合领域中重点课题，受到广泛关注和研究。许多经济决策涉及如何将特定的任务有效地分配给厂商或处理器加工，使得其最终能够获得最大的利益。Stone于1977年首次讨论了无向图结构的任务分配问题，对于给定的图G=(T,E,dj)，其中顶点集合T表示n个任务，边集合E表示任务之间的通信关系，向量函数e:TR+m表示任务的加工成本函数，分量eip(i)表示任务iT在处理器p(i)P上的加工成本，向量函数:ER+表示任务之间的通信成本函数，任一边ijE的通信成本为(dj)，这里的任务之间通信成本仅与任务有关而与处理器无关，但当分配给同一个处理器时任务通信成本为0，目标是寻找使所有任务得到加工后加工成本和通信成本之和达到最小的分配方案，即miniTeip(i)+jE(dj)，p:TP为所有任务分配给对应处理器的分配函数。当处理器数量|p|=2时，Stone构造了一个赋权网络，利用Ford-Fulkerson算法寻找网络中的最大流从而得到该问题的最优分配方案1。Lo基于Stone得到的前缀属性提出了求解无向图结构通信的任务分配问题的启发式算法2。1981年，Bokhari证明了当|p|3时，无向图结构通信的任务分配问题是NP困难的3。随后，Baca得到了一些该问题复杂性方面的结果：除非P=NP，否则不可能存在1+e近似的多项式时间算法4。但是在一些具有特殊结构通信任务分配问题中，我们能够找到最优的分配方案。Bokhari首次提出树形图结构的任务分配问题，结合动态规划算法和最短路算法，弧集合E表示任务之间的通信关系，p:TP为所有任务分配给对应处理器的分配函数，为使得所有任务得到加工后加工成本和通信成本之和达到最小，即miniTeip(i)+(i,j)E(dj,p(i),p(j)5。Bokhari设计了求解该问题最小成本最优解的一个时间复杂性为O(nm2)多项式时间算法。在树结构的一致通信中，任务的通信与处理器无关时，即miniTeip(i)+(i,j)E(dj)，Billionnet将其时间复杂性减少到O(nm)6。基于静态分配和任务执行的可重复性的特性（如程序等类型任务），Towsley考虑了任务分配图是串并联图时，如何将n个任务分配给m个异构处理器，找到一个最优分配方案使得总成本达到最小，并得到了一个时间复杂性为O(nm3)的静态多项式精确算法7。传统的任务调度分配算法大多是针对同构或异构系统设计的，而异构多核并行系统的发展对任务调度分配算法也提出了新的挑战8-11。带时间惩罚的有向串并联图任务分配问题胡淑珂，庞留勇，周向前（黄淮学院数学与统计学院，河南驻马店463000）收稿日期：2022-09-15基金项目：国家自然科学基金项目（12171193）；河南省高等学校重点科研项目（23B110012；23B110009；22B110006；21A110015；20B110008）；河南省科技攻关项目（212102310464）摘要：随着经济的快速增长，很多产品的运作生产，往往需要不同的工艺流程。文章考虑了带有时间惩罚的有向串并联图最小任务分配问题和带有时间惩罚的有向串并联图最小跨度任务分配问题，根据有向串并联任务优先图结构构建有向串并联分配图。在此基础上，文章应用时间复杂性更小的特殊结构最短路算法以及收缩方法，分别设计了两个时间复杂性为O(nm2k2)的多项式算法来解决带时间惩罚的有向串并联图任务分配问题，其中n为任务数量，m为处理器数量，k是时间段限制数量。关键词：有向串并联图；任务分配；多项式算法；时间限制惩罚；最小成本；最小跨度中图分类号：O224文献标识码：A文章编号：1673-260X（2023）02-0014-06Vol.39 No.2Feb.2023赤 峰 学 院 学 报（自 然 科 学 版）Journal of Chifeng University(Natural Science Edition)第39卷第2期2023年2月14-DOI:10.13398/ki.issn1673-260 x.2023.02.019有向串并联图结构任务分配问题生活中常见的例子如程序模块化运行、电流方向一定的集成电路、大型建筑工程流程、医疗器械等产品工艺制造流程、产品加工流程等等，其在生产工艺上的应用颇为广泛，具有重要的研究意义和价值。本文将基于前人对串并联图研究的基础上9-12创新探讨带有惩罚的有向串并联图任务分配问题，并进行模型的构建和算法的设计。2有向串并联图相关概念有向串并联图是指能够转化为只有一个源点、一个收点、一条弧的图，其转换规则如下：(1)如果两个顶点之间有两条并行的弧，则替换为一条弧，如图1中二重弧(c,d)可合并用一条弧替换。(2)如果一个顶点b出入度均为1，只与顶点a和顶点c相邻，如图1(a)，则合并用一条弧(a,c)替代弧(a,b),(b,c)。(3)通过构造虚拟的顶点和弧来使其间接转化为有向串并联图。如图1(b)所示树形图，构造了虚拟的顶点z，将树形图叶子节点通过虚拟的弧与虚拟顶点z相连，并将虚拟的弧权重赋值为0。如图1(a)和1(b)通过上述三种规则的转化都可以转化为有向串并联图，对于能够通过上述3种规则能够转化为只有一个源点和只有一个收点的一条有向弧的有向图，我们统称为有向串并联图9。3带有时间惩罚的串并联图任务分配问题3.1问题定义本文所考虑的分布式处理系统的前提条件：(1)有向串并联结构的任务优先图；(2)可考虑任务迁移的通信代价惩罚；(3)处理器为异构(多核)处理器；(4)任务是不可分的，每个任务都要分配给一个处理器处理；(5)任务在各个节点上的执行成本、通信成本和惩罚代价都是可计算的。假定分布式处理系统是由n个任务，m个异构处理器组成，k个时间段限制，不同任务、不同处理器在不同时间段之间的通信成本不尽相同。如图2为一个带有时间惩罚的有向串并联图可行任务分配情况。任务i在处理器px在时间段v上的执行成本记为ei,px,v，当处理器在某个时间段不可用时，其执行成本记为无穷大；当任务i分配给处理器p时间段v上并且任务j分配给处理器q时间段w上时，任务i和j的通信成本记为(dj,px,py,v,w)，任务在同一处理器上的成本是恒定的；同时，每项任务的完成又有一定的时间段限制，如果任务j没有在第w-1时间段结束时完成，则任务j有一个惩罚费用记为Fj,w-1，如果任务j要求必须在w-1时间段结束前完成，那么任务j在w-1时间段结束后未完成的惩罚费用记为无穷大。有向串并联任务优先图G(T,E,dj)中，如图3所示，一条弧(i,j)E表示处理任务j之前需要把任务i完成，dj表示任务i到任务j之间的传送量。若有向串并联任务优先图有多重弧，则将多重弧合并为一条弧，该弧传送量为两条弧之和dj1+dj2，需注意对于重弧做此合并不会影响到任务的执行分配情况。3.2模型构建为解决带有时间惩罚的串并联图任务分配问题，我们首先将带有时间惩罚的有向串并联任务优先图转化为带有时间惩罚的有向串并联分配图D图1有向串并联图图2带有时间惩罚的可行有向串并联任务分配图图3有向串并联任务优先图数理研究15-(V,A)，定义如下：(1)顶点集合。包括一个源点s和一个终点z，以及nmk个层顶点。这里n表示任务优先图中的任务数量，m表示处理器数量，k表示限制时间段数量。层顶点ip代表任务i在处理器p在时间段上执行。如图4有向串并联分配图是对应图3任务优先图在2个处理器和2段时间限制惩罚下转化而成。(2)如果顶点ipxv到顶点ipyw在构建的分配图上有弧，则仅当任务i到任务j在任务优先图上有弧并且wv，如图4所示。(3)从源点s到入度为0的起始层顶点分别构造一条有向弧，如图4所示，从s到111,121,112等。(4)从出度为0的顶点到终端点z分别构造一条弧。如图4所示，511,521,611,621,到终点z构造的有向弧。Bokhari提出的最短路算法思想5将有助于我们解决带有时间惩罚的有向串并联图任务分配问题，这里结构特殊，直接应用Dijkstra最短路算法会增加时间复杂性，故本文基于特殊结构的最短路SHORT算法来设计求带有时间惩罚的有向串并联图分配问题最优解的多项式算法。SHORT算法具体如下：图5SHORT算法示例图Input：一个如图5结构的有向图D=(V,A,w);Output:起始层所有点到z的最短路。BeginStep1Step2Step3Step4End置d(z)=0,d(vip)=+,i=1,2,n；其中p=1,2,m,=1,2k；令d(z)=0,d(vnp)=w(vnp,z),P(vnp)=z；其中p=1,2,m,=1,2k；For i=n to 2 do:For all(v(i-1)pxv,vipyw)A,px,py=1,2,m,v,w=1,2,k do:若d(v(i-1)pxv)d(vipyw)+w(v(i-1)pxv,vipyw)置d(v(i-1)pxv)=d(vipyw)+w(v(i-1)pxv,vipyw)；p(v(i-1)pxv)=vipyw；For all v1pV,p=1,2,m，=1,2,k do:输出顶点v1p到顶点z的最短路长d(v1p)；反向追踪数组P(v1p)，输出顶点v1p到顶点z的最短路；图6并行SHORT算法流程图图4有向串并联分配图数理研究16-在算法设计中我们会用到并行SHORT算法的思想7，当有向串并联任务优先图两个顶点之间有多条路时，我们称之为任务优先图的并行结构，如图6(a)虚线部分，它所对应的有向串并联分配图部分称之为分配图的并行分支6(b)；调用并行SHORT算法能够找到两个顶点之间多条并行的最短路如图6(b)加粗虚线弧，最后将并行的最短路收缩为两层结构的同一条最短路如图6(c)。3.3带有时间惩罚的有向串并联图最小成本分配问题算法设计在一些有向串并联结构任务分配问题中，其产品生产流程工艺之复杂往往需要跨越不同的国家、产业、公司，在任务带有时间段限制的惩罚之下，生产商需要考虑在符合子任务加工性能的标准之上，使得总成本达到最小，做出好的分配决策使得产品的获益大大增加。问题描述：对于一个给定的赋权有向串并联图G(T,E,dj),d:ER+,p:TP为所有任务分配给对应处理器的分配函数，:T为所有任务分配给对应时间段的分配函数，为使异构处理器系统下带有时间惩罚的有向串并联图任务分配问题总成本达到最小，有目标函数如下：miniTeip(i)(i)+(i,j)E(dj,p(i),p(j),(i),(j)+jTFj,(j)-1（1）根据有向串并联图G(T,E,dj)构造带有时间惩罚的有向串并联分配图D(V,A,w)，w:AR+，并定义弧权重赋权规则如下：(1)与源点s相连的弧权重为w(s,ipx,v)=eipxv。(2)与终端点z相连的弧权重为w(ipxv,z)=0。(3)对顶点层之间的其余弧权重赋值规则为w(ipxv,jpyw)=ejpyw/d-(j)+(dj,px,py,v,w)+Fj,w-1其中，(ipxv,jpyv)A,d-(j)为有向串并联图中顶点j的入度。Fj,w-1表示在任务j在前一个时间段w-1结束后未完成的惩罚费用。若带有时间惩罚的有向串并联图最小成本分配问题可行解示例图D1，如图7所示，则该分配方案所对应分配成本即为当前分配示例图总权重和w(D1)。为得到带有时间惩罚的有向串并联图最小成本分配问题最优分配解我们设计了Min-PSA算法。Min-PSA算法流程具体如下：定理1：Min-PSA算法是带有时间惩罚的有向串并联图最小成本分配问题的一个精确算法，其时间复杂性为O(nm2k2)，n为任务数量，m为处理器数量，k为时间段限制数量。证明：Min-PSA算法首先找到带有时间惩罚的有向串并联分配图D=(V,A,w)中的并行分支结构，对其调用SHORT算法找到顶点之间的最短路并进行标记找到局部最优解，并将其分支收缩合并为两层有向结构；按上述过程进行迭代更新D(V,A,w)直到无并行分支结构，最后调用SHORT算法找到中从D=(V,A,w)到s的最短路，