1

实验成绩

华中师范大学计算机科学系

实 验 报 告 书

实验题目：基于遗传算法的多任务调度研究

课程名称：

智能计算

主讲教师： 沈显君

辅导教师：

课程编号：

班 级： 2011级

实验时间： 2011年11月 姓名 何印标

学号 2011112915

2

基于遗传算法的多任务调度研究

摘要：

本文主要讨论了遗传算法在工程项目中多任务执行优化中的应用，重点对多任务调度 (Resource—constrained project scheduling problem，RCPSP)问题进行了研究。讨论了资源受限的多任务调度问题，提出了改进的遗传算法优化多任务调度问题的方法，主要从优化算法模型的建立，优化算法设计，算法的实现以及结果分析等几个方面进行了详细论述，并与其它启发式方法进行了对比分析。

关键字：效益最优化；遗传算法；多任务

1．简介

任务调度优化在工程项目管理中是非常重要的，它决定了工程项目利润的高低。遗传算法是一种并行的全局搜索的高效求解问题的方法，本质上就是处理离散优化搜索问题的，它不要求问题空间的连续性，不需要梯度信息，其鲁棒性(Robust)已经得到了证实，在处理大型复杂优化问题上己经取得了显著的成绩，所以在解决多任务调度优化问题时，具有其它方法无法比拟的优势。

2．多任务调度模型的建立

假设存在若干并行任务和一个共享的资源库，包含有若干种可更新资源(renewable resources)，并且所有资源都只有有限的供给量。任务之间除了共享资源外互相独立。为方便对问题进行描述，建立如下的数学模型：多任务调度问题有P个相互独立的任务，第k个任务包含nk+1个工作,其中第nk+ 1个任务为任务虚拟的终止工作,不占用资源和时间。这P个任务共享M种可更新资源，其中第m 种资源的总量为Rm。用Wi表示第i个任务的工作集，Wij表示第i 个任务中的第j 个工作,其工期为dij，对第m 种资源的需求量为rijm，任务的开始时间标记为Sij ,它的所有紧前任务形成的集合记为Pij。在时间t 时正在进行的所有任务的集合标记为It。考虑到不同任务的重要程度不同,用ak表示第k个任务的权重。综合上述假设和采用的符号，资源约束下的多任务调度问题可以描述为公式（1）-(6)：

PknkkkS11,)(*min （1）

jiPhdSStsijhihiji,,,..,,, （2）

.,,,tjiIwmijmtmRr （3）

3 kjkjkjPkdStSWkWkjtI|)(1 （4）

0ijmr （5）

Pkk11 （6）

3．算法设计

3．1资源约束的多任务调度问题的求解

由于是多个任务的之间的工作共享共同的资源，所以解决的方法与单个任务的之间的工作共享共同的资源的方法不同。在解决该问题的方法中，目前有文献[5]中提出的多种资源受限多任务排序问题的两层决策方法，但是该方法有两个很大的缺陷。首先，该方法中假设的前提条件是每个任务中共享资源的工作持续时间由所分配到的资源量决定，使用共享资源的工作持续时间与资源分配量成反比关系(如2台机器干6

天, 4台机器就干3天)，即工作持续时间=工作的工作量÷资源量。而在现实生活中，很多工作的工作量并不是可累加的，即工作持续时间!= 工作的工作量÷资源量,所以对于任务中的工作是工作量不可累加的工作的问题，该模型就无法求解。第二个缺陷是，该模型对各个任务之间采取的是特定的资源分配策略，当资源分配给某个任务以后，就始终属于该任务了，其它任务就不能再使用该部分资源。这种资源分配方法会造成资源的较大浪费。因为在这种分配策略中，任务之间的资源不能相互流通调整。所以当其中某个任务有某类资源空闲时，其它任务均不能利用，这样该类资源就浪费了。

本文提出基于遗传算法的方法，能够求解任务中工作类型为不可累加的工作的多任务问题，而且各个任务之间资源是能够动态相互流通的，不会造成资源闲置而浪费，并且不用对多任务中各个任务的网络计划进行任何合并，只需要分别输入各个任务的工作的时间、资源等信息，就能对各个任务进行调度，按照各个任务的权重，使所有任务能以尽可能短的工期完工。

3．2算法中基本的数据结构的建立

在生成初始种群以前，首先要建立数据结构对各个任务的信息进行存储。

首先定义了一个二维数组benefit_matrix[m][n]。

其中，m表示任务的数目，n表示处理机数目。benefit_matrix[i][j]表示任务i在处理机j上处理所得的效益值。

int num_of_job; // 任务数，存储在文件numoftm.txt

int num_of_machine; // 处理机数，存储在文件numoftm.txt

int num_of_chromosomes; //群体数 ，存储在文件numofcolony.txt

int num_of_gen; // 产生的代数，也就是最后产生的那个代的序数，存储在文件num_of_gen.txt

int **colony = NULL; //任务序列

int *benefit_array = NULL; // 任务调度序列中每个任务的效益组成的数组

4 3．3染色体结构和编码设计

资源受限的多任务调度问题可以也看作是服从某些约束条件的排序问题。解决问题的关键是如何应用遗传算法找到一个多任务中所有工作的一个合适排列顺序。在这里用按一定顺序排好的所有工作列表对问题进行染色体编码。设有m个任务，每个任务有n个工作，则共有m*n个工作，即该染色体的长度为m*n。令Vk表达当前种群中的第K个染色体，令Pkij为染色体的一个基因，表示在染色体j位置上的第Pk个任务中的工作，染色体可表达如下：

Vk=[P1i1,…, P1ii,…,P1in,…,Pki1,…, Pkii,…Pkin,…,Pmi1,…, Pmii,…,Pmin]

其中Pkij的顺序可在满足约束条件的前提下任意排列。

3．4染色体的初始化

对于染色体的初始化，本文分为两部分进行，一部分是通过拓扑排序的方法随机生成各个染色体，另一部分是通过各种启发式方法生成染色体。

方法一：随机生成初始染色体

该方法与单个任务的资源有限时间最短的优化调度方法类似,不同之处在于对于每个工作，首先要判断它属于哪个任务，然后才能确定它的约束关系。方法为以从左向右的固定顺序一次考虑一个未被确定最早开始时间的工作。在每一阶段，保持已排序的工作的集合，并完全随机的从可调度工作集合中选中一个工作安排到该集合中。这个过程一直重复下去，直到所有工作被安排。该过程的每一次迭代中所有的工作都处于下列三种状态之一：

①已排序的工作：已经在构造的部分染色体中的工作。

②可调度工作：那些所有紧前工作都是已排序工序的工作。

③自由工作：所有其他工作。

令tkv是v的一个部分染色体，包括t个活动。tQ是在阶段t与给定的tkv对应的可安排活动的集合，令Pi是活动i所有紧前活动的集合，则与给定tkv对应的可安排活动集合tQ定义为:

tkitvPjQ| （7）

它包括终节点在特定安排tkv中的活动，并且是所有竞争活动的集合。

其中修改可调度工作集Qt的方法如下：a、从Qt中删除已经选中的工作j。b、判断工作j的紧后工作中是否存在这样的工作k（工作k属于自由工作），它的所有紧前工作都在已生成的部分染色体中，即它的所有紧前工作都是已排序工作。c、若存在k,则把k加入到可调度工作集Qt中。

方法二：通过各种启发式方法生成初始染色体

白思俊一共归纳了31种启发式方法[7][8]。本文在此处选择了对任务资源优化调度比较有效的11种启发式方法，应用这11种方法生成了调度效果比较好的若干个染色体。

11种启发式准则如下：

(1)最小总时差优先准则(MinTS)，若相同则按工作最早开始时间排。

(2)最大总时差优先准则(MaxTS)，若相同则按工作最早开始时间排。

(3)最小工期优先准则(SOF)，若相同则按工作编号排。

(4)最大工期优先准则(MOF)，若相同则按工作编号排。

(5)最小LS优先准则(MinLS)，若相同则按工作编号排。

5 (6)最小EF优先准则(MinEF)，若相同则按工作编号排。

(7)最小LF优先准则(MinLF)，若相同则按工作编号排。

(8)ACTIM准则，即关键路径的长度与工作最迟开始时间之差，值越大越优先。

(9)最大资源需求强度优先准则 (MaxR)。

(10)最小资源需求强度优先准则(MinR)。

(11)最多紧后工作优先准则(MostIS)。

文献[9]中还提出了如下几种启发式准则：最先考虑位于关键路径上的工作，若几个任务中的关键工作发生冲突时，分别考虑以下几种方案（1）总时差最小的工作优先。（2）最先开工的工作优先。（3）最早完工的工作优先。（4）优先考虑最紧张的工作，即剩余交货期与剩余加工时间之比越小则该任务越紧张。

3．5遗传算子设计

当在建立的十字链表的基础上对各个任务中的工作进行重新编号，然后应用本文所述的调度算法，将所有任务中的工作都混合在一起，编码成一条染色体后，问题就变得相对简单了，此时，对染色体的遗传操作方法就与对单任务中的染色体遗传操作方法比较类似了。

3.5.1 交叉

在文献[10]中使用的是PMX(部分交叉算子)，但使用该算子后会产生非法个体，需要对

染色体进行修复，这将会降低程序的执行效率，此处仿照离散交叉算子提出一种不需要对染色体进行修复的方法。

记参与交叉运算的两个个体为母亲M和父亲F,选择一随机整数q, 1 ≤ q ≤J ,J为染色体长度，由M和F通过在q 点交叉运算产生两个后代分别为女儿D和儿子S. 在D 的工作链表中, 前q 个工作继承于M , 即

,MiDijj i=1, 2,…, q

而i = q + 1, …, J 位置的工作来自于F , 并保留F中各工作的相对位置, 即

,FkDijj i=q+1,q+2,…,J

其中

},,2,1},,,,{|min{121JkjjjjkkDiDDFk

S的工作链表形成过程与D 相似，这里不再重复。

3.5.2 变异

变异算子采用集中搜索策略设计，结合邻域技术寻找改进的后代。将调度x不超过d个基因的变化所得到的调度集合称为调度x的邻域（如图1）, 如果x比其邻域的任何其它解好，则调度x被称作优化。变异过程如下：

图 1 染色体邻域示意图