3 基于QPSO的DAG并行任务调度
　　3.1 编码与解码
　　任务调度的常见编码包括基于任务的编码、基于操作的编码和基于优先规则的编码等。由于DAG并行任务调度的复杂性，采用任一种上述编码形式均无法保证所有解的合法性，这将浪费大量的求解时间。本文设计了一种复合的编码方案:编码长度为2 m，可描述为两个向量，第一个向量采用基于优先规则的编码方式，为一个包含m维的向量(R?1，R?2，…，R?m)。其中R?i表示在算法迭代过程中第i次迭代时发生的冲突利用优先规则R?i消除。本文选择了五种优先规则，包括最短执行时间(SPT)、最长执行时间(LPT)、最早开工时间(EST)、最早完工时间(EFT)、最晚完工时间(LFT)，数字0、1、2、3、4分别对应优先规则SPT、LPT、EST、EFT、LFT。第二个向量是处理机分配向量，即一个包含m维的向量(M?1，M?2，…，M?m)。其中M?i表示编号为i的子任务被分配到编号为(M?i)的处理机上执行(所有处理机编号为0，1，…，n-1)。
　　在解码过程中，设t为调度的时间步，PS为调度列表。其中PS?t为第t步调度执行的子任务;TS为所有前驱已经被调度的子任务所构成的集合。解码算法如下:
　　a)令t=1，PS为空，TS由所有无前驱的子任务构成。
　　b)由TS中所有子任务编码，在处理机分配向量(M?1，?M?2，…，M?m)中找到分配给每个子任务的处理机，并在Θ中找到具体执行时间。
　　c)依据约束条件和执行时间，得到TS中每个子任务对应的指标时间(开工、完工或执行时间)，由编码R?t所对应的优先规则选出一个子任务(如优先规则为最短执行时间，则选TS中执行时间最短的子任务，如果有多个子任务符合优先规则，则任选一个)，该子任务就是PS?t，从TS中删除它，并将其加入PS的尾部。
　　d)逐个考察PS?t的后继子任务，如果该子任务无其他前驱，或其他前驱都已被调度执行，则将其加入TS中。
　　e)令t=t+1，若t　　通过下面示例说明解码过程:
　　任务的DAG如图1所示。
　　
　　优先规则向量:
　　(032140)
　　即:(SPT EFT EST LPT LFT SPT)
　　处理机分配向量:
　　(0 1 1 0 1 0)
　　即(P1 P2 P2 P1 P2 P1)
　　在Θ中查到的处理时间:
　　(2 4 6 5 3 7)
　　处理时间指1～6号子任务在对应处理机上的执行时间。
　　
　　根据示例数据得到的调度列表PS为(T?1 T?2 T?4 T?6 T?3 T?5)，甘特图如图2所示。
　　
　　由上述编码方式和解码过程可知，本文编码能保证调度的可行性，且码长较短，无冗余，解码复杂性不高。
　　3.2 QPSO中向量的计算方法
　　对每个粒子，它的优先规则向量和处理机分配向量可以表示为Xpriority(1..m)和Xmachine(1..m)，按式(5)~(7)计算这两个向量。由于前面所述的QPSO为连续空间算法，而DAG并行任务调度问题为整数规划问题，将离散优化转变成对实数向量的连续优化，具体过程如下:

　　a)将每个向量切断分成若干个子串，各段子串的长度可以相等，也可以不相等，子串形如(q?1，q?2，…，q?k)。
　　b)从整数组成的子串到实数作一个映射，可表示为
　　r=c×?ki=1q?i×b??k-i(9)
　　其中:r为映射的实数;c是常数，一般取足够小的实数，本文取值为0.01;b为基数，对于Xpriority，b取值为5，对于Xmachine，b取值为n。
　　c)在计算任务执行总时间前，需将r转换为子串，即式(9)的逆映射:
　　
　　q?i=(rc-?i-1j=1q?j×b??k-j)p b??k-i(10)
　　其中:p为整除，得到的商q?i为整数，在实际运算时，可用一个循环，i从1~k得到子串中所有分量。
　　例如9个子任务的情况，Xpriority=(2 4 2 1 4 3 4 1 0)，分为三段，各子串长度均为3。
　　子串 (242); (143); (410)
　　变换后得到
　　r0.720.481.05
　　经过迭代后的情况:
　　逆变换后得到
　　r0.531.120.91
　　子串(203)(422)(331)
　　在初始化时，可省掉式(9)的转换过程，直接给粒子位置赋实数。
　　解决了连续化问题之后，还有一个边界问题，如上例r的取值为[0，1.24]，如迭代过程中z的运算结果超出范围时，将r值取在边界上。若r<0，取值0;r>1.24，取值1.24。
　　
　　通过上述映射和逆映射，整数规划问题转换为连续优化问题，从而可以利用QPSO优化获得高质量的解。
　　3.3 算法流程
　　a)初始化粒子群，根据编码方案设定各粒子的随机位置。
　　b)根据式(10)将每个粒子的实数向量转换为整数向量。
　　c)对每个粒子的整数向量解码后，计算每个粒子的目标函数值。
　　d)更新每个粒子的局部最优值P?i。
　　e)更新粒子群的全局最优值P?g。
　　f)根据式(5)计算mbest。
　　g)根据式(6)计算每个粒子随机点PP?i。
　　h)根据式(7)更新每个粒子的新位置。
　　i)返回b)步，直到满足迭代的次数。
　　4 仿真实验与结果分析
　　4.1 实验参数选取
　　本文的仿真实验是在MATLAB软件上实现的。实验所用DAG图随机生成，每个任务节点有1～4个前驱与后继，估计运行时间θij为1～50 s的随机数。实验计算了文献[3，4]的算法、PSO与本文的QPSO共四种情况，算法中主要参数:种群大小为80，终止代数为1 500，amax取值1，amin取值0.5;PSO的惯性权重w与QPSO中的收缩扩张系数a取值相同，c?1和c?2均为2，编码、解码、连续化与边界问题均使用本文的方案;文献[3]算法的杂交概率为1.0，变异概率为0.05;文献[4]算法的内部杂交概率为0.8，迁移概率为0.2，演化策略中的参数为μ/λ=5。
　　4.2 计算结果与分析
　　对于随机生成的同一个DAG图，分别用上述四种算法进行计算，记录各算法收敛时得到的最优解的完成时间和收敛时的进化代数。计算结果如表1所示。为了消除数据随机性的影响，更好地反映算法的性能，表1中的进化代数是100次进化的平均收敛代数，完成时间是所有100次进化中得到的最优解的平均完成时间。图3为四个处理机100个子任务情况下四种算法分别进化的静态性能曲线，列出了各算法在不同进化代数时所找到的最优解。表2为四种算法在进化中能收敛到其最优解的次数占实验总次数的百分比。
　　表1 仿真实验结果
　　
　　处理机?个数子任务?个数
　　
　　完成时间/s
　　
　　文献[3]?算法文献[4]?算法PSO?算法本文?算法
　　
　　收敛时的进化代数
　　
　　2528527127926539312529
　　250565543551538166131108125
　　1001 5481 4291 4271 416418339285323
　　2519318618817953463338
　　450457429428417194168135157
　　1001 1981 1361 1391 073516468323339
　　2515214113813473544952
　　850341297292281336217163212
　　1001 106911923875727621538601
　　
　　表2 收敛到其已知最优解的次数占进化总次数的百分比%
　　
　　各算法子任务个数25子任务个数50子任务个数100
　　文献[3]算法876448
　　文献[4]算法969281
　　PSO算法928967
　　本文算法1009996
　　
　　由表1、2和算法的静态性能曲线可以得出:
　　a)在任务数较多、处理机较多的情况下，PSO与本文QPSO算法的收敛速度比文献[3]算法快很多，但与文献[4]算法比较时，PSO算法的收敛速度明显比文献[4]算法快，本文QPSO算法则与文献[4]算法相当;而在任务数少的情况下，除文献[3]算法稍慢，其他算法相差不大。
　　b)本文QPSO算法能找到的最优解比文献[3，4]算法有明显的提高，尤其是子任务数较多、处理机数较多时。
　　c)PSO与本文QPSO算法比较时，发现QPSO算法的收敛速度比PSO算法慢，但得到的最优解比PSO算法好。
　　这是因为:首先，本文对问题的编码能够覆盖整个解空间，相对来说文献[3，4]的算法只能从一个相对较小的空间内搜索;其次，本文采用了离散空间到连续空间的转换过程，它不仅满足了QPSO算法对待解问题的取值要求，还在一定程度上能更好地保护与遗传优良的解片段。另外，PSO算法收敛过快，而QPSO的量子搜索方式对传统的PSO算法有了很大的改进，实验证明可防止早熟。
　　5 结束语
　　基于DAG的并行任务调度问题是NP难问题，传统的优化算法很难求得全局最优解，虽然已有人将遗传算法应用于此问题，但结果有待进一步改善。本文给出了新的问题定义，对QPSO算法作出调整与改进，编码表示采用了适合于任务调度问题的优先规则与处理机分配相结合的形式，并将离散空间优化问题转换为连续空间优化问题，使得QPSO有较好的搜索能力。最后通过仿真实验得到的一系列数据，表明了本文的改进QPSO算法比遗传算法和PSO算法有更好的性能，并有理由认为，合理的编码表示与高效的搜索策略相结合是任务分配调度问题全局寻优的有效途径。
　　

参考文献

　　[1]
　　GRAY M R，JOHNSON D S.Computers and intractability:a guide to the theory of NP-completeness[M].New York:W.H.Freeman and Co.，1979.
　　[2]AHMAD I，KWORK Y K.On parallelizing the multiprocessor scheduling problem[J].IEEE Trans on Parallel and Distributed Systems，1999，10(4):414-432.
　　[3]HOU E S H，ANSARI N，HONG Ren.A genetic algorithm for multiprocessor scheduling[J].IEEE Trans on Parallel and Distributed Syetems，1994，5(2):113-120.
　　[4]钟求喜，谢涛，陈火旺.基于遗传算法的任务分配与调度[J].计算机研究与发展，2000，37(10):1197-1203.
　　[5]张聪，马义忠.异构计算系统中基于遗传算法的任务分配与调度[J].微电子学与计算机，2004，21(6): 74-78.
　　[6]KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.Pisca-?taway:IEEE Press，1995:1942-1948.
　　[7]SUN Jun，FENG Bin，XU Wen-bo.Particle swarm optimization with particles having quantum behavior[C]//Proc of Congress on Evolutionary Computation. 2004: 325-331.
　　[8]SUN Jun，XU Wen-bo，FENG Bin.A global search strategy of quantum behaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems. 2004: 111-116.