1引言任务分配问题是组合领域中重点课题，受到广泛关注和研究。许多经济决策涉及如何将特定的任务有效地分配给厂商或处理器加工，使得其最终能够获得最大的利益。Stone于1977年首次讨论了无向图结构的任务分配问题，对于给定的图G=(T,E,dj)，其中顶点集合T表示n个任务，边集合E表示任务之间的通信关系，向量函数e:T→R+m表示任务的加工成本函数，分量eip(i)表示任务i∈T在处理器p(i)∈P上的加工成本，向量函数α:E→R+表示任务之间的通信成本函数，任一边ij∈E的通信成本为α(dj)，这里的任务之间通信成本仅与任务有关而与处理器无关，但当分配给同一个处理器时任务通信成本为0，目标是寻找使所有任务得到加工后加工成本和通信成本之和达到最小的分配方案，即min{∑i∈Teip(i)+∑j∈Eα(dj)}，p:T→P为所有任务分配给对应处理器的分配函数。当处理器数量|p|=2时，Stone构造了一个赋权网络，利用Ford-Fulkerson算法寻找网络中的最大流从而得到该问题的最优分配方案[1]。Lo基于Stone得到的前缀属性提出了求解无向图结构通信的任务分配问题的启发式算法[2]。1981年，Bokhari证明了当|p|≥3时，无向图结构通信的任务分配问题是NP困难的[3]。随后，Baca得到了一些该问题复杂性方面的结果：除非P=NP，否则不可能存在1+e近似的多项式时间算法[4]。但是在一些具有特殊结构通信任务分配问题中，我们能够找到最优的分配方案。Bokhari首次提出树形图结构的任务分配问题，结合动态规划算法和最短路算法，弧集合E表示任务之间的通信关系，p:T→P为所有任务分配给对应处理器的分配函数，为使得所有任务得到加工后加工成本和通信成本之和达到最小，即min{∑i∈Teip(i)+∑(i,j)∈Eα(dj,p(i),p(j))}[5]。Bokhari设计了求解该问题最小成本最优解的一个时间复杂性为O(nm2)多项式时间算法。在树结构的一致通信中，任务的通信与处理器无关时，即min{∑i∈Teip(i)+∑(i,j)∈Eα(dj)}，Billionnet将其时间复杂性减少到O(nm)[6]。基于静态分配和任务执行的可重复性的特性（如程序等类型任务），Towsley考虑了任务分配图是串并联图时，如何将n个任务分配给m个异构处理器，找到一个最优分配方案使得总成本达到最小，并得到了一个时间复杂性为O(nm3)的静态多项式精确算法[7]。传统的任务调度分配算法大多是针对同构或异构系统设计的，而异构多核并行系统的发展对任务调度分配算法也提出了新的挑战[8-11]。带时间惩罚的有向串并联图任务分配问题胡淑珂，庞留勇，周向前（黄淮学...
