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

《基于遗传算法的任务调度研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、姓名何印标学号2011112915实验成绩9华中师范大学计算机科学系实验报告书实验题目：基于遗传算法的多任务调度研究课程名称：智能计算主讲教师：沈显君辅导教师：课程编号：班级：2011级实验时间：2011年11月9基于遗传算法的多任务调度研究摘要：本文主要讨论了遗传算法在工程项目中多任务执行优化中的应用，重点对多任务调度(Resource—constrainedprojectschedulingproblem，RCPSP)问题进行了研究。讨论了资源受限的多任务调度问题，提出了改进的遗传算法优化多任务调度问题的方法，

2、主要从优化算法模型的建立，优化算法设计，算法的实现以及结果分析等几个方面进行了详细论述，并与其它启发式方法进行了对比分析。关键字：效益最优化；遗传算法；多任务1．简介任务调度优化在工程项目管理中是非常重要的，它决定了工程项目利润的高低。遗传算法是一种并行的全局搜索的高效求解问题的方法，本质上就是处理离散优化搜索问题的，它不要求问题空间的连续性，不需要梯度信息，其鲁棒性(Robust)已经得到了证实，在处理大型复杂优化问题上己经取得了显著的成绩，所以在解决多任务调度优化问题时，具有其它方法无法比拟的优势。2．多任务调

3、度模型的建立假设存在若干并行任务和一个共享的资源库，包含有若干种可更新资源(renewableresources)，并且所有资源都只有有限的供给量。任务之间除了共享资源外互相独立。为方便对问题进行描述，建立如下的数学模型：多任务调度问题有P个相互独立的任务，第k个任务包含nk+1个工作,其中第nk+1个任务为任务虚拟的终止工作,不占用资源和时间。这P个任务共享M种可更新资源，其中第m种资源的总量为Rm。用Wi表示第i个任务的工作集，Wij表示第i个任务中的第j个工作,其工期为dij，对第m种资源的需求量为rijm，

4、任务的开始时间标记为Sij,它的所有紧前任务形成的集合记为Pij。在时间t时正在进行的所有任务的集合标记为It。考虑到不同任务的重要程度不同,用ak表示第k个任务的权重。综合上述假设和采用的符号，资源约束下的多任务调度问题可以描述为公式（1）-(6)：（1）（2）（3）9（4）（5）（6）3．算法设计3．1资源约束的多任务调度问题的求解由于是多个任务的之间的工作共享共同的资源，所以解决的方法与单个任务的之间的工作共享共同的资源的方法不同。在解决该问题的方法中，目前有文献[5]中提出的多种资源受限多任务排序问题的两层

5、决策方法，但是该方法有两个很大的缺陷。首先，该方法中假设的前提条件是每个任务中共享资源的工作持续时间由所分配到的资源量决定，使用共享资源的工作持续时间与资源分配量成反比关系(如2台机器干6天,4台机器就干3天)，即工作持续时间=工作的工作量÷资源量。而在现实生活中，很多工作的工作量并不是可累加的，即工作持续时间!=工作的工作量÷资源量,所以对于任务中的工作是工作量不可累加的工作的问题，该模型就无法求解。第二个缺陷是，该模型对各个任务之间采取的是特定的资源分配策略，当资源分配给某个任务以后，就始终属于该任务了，其它任

6、务就不能再使用该部分资源。这种资源分配方法会造成资源的较大浪费。因为在这种分配策略中，任务之间的资源不能相互流通调整。所以当其中某个任务有某类资源空闲时，其它任务均不能利用，这样该类资源就浪费了。本文提出基于遗传算法的方法，能够求解任务中工作类型为不可累加的工作的多任务问题，而且各个任务之间资源是能够动态相互流通的，不会造成资源闲置而浪费，并且不用对多任务中各个任务的网络计划进行任何合并，只需要分别输入各个任务的工作的时间、资源等信息，就能对各个任务进行调度，按照各个任务的权重，使所有任务能以尽可能短的工期完工。3

7、．2算法中基本的数据结构的建立在生成初始种群以前，首先要建立数据结构对各个任务的信息进行存储。首先定义了一个二维数组benefit_matrix[m][n]。其中，m表示任务的数目，n表示处理机数目。benefit_matrix[i][j]表示任务i在处理机j上处理所得的效益值。intnum_of_job;//任务数，存储在文件numoftm.txtintnum_of_machine;//处理机数，存储在文件numoftm.txtintnum_of_chromosomes;//群体数，存储在文件numofcolon

8、y.txtintnum_of_gen;//产生的代数，也就是最后产生的那个代的序数，存储在文件num_of_gen.txtint**colony=NULL;//任务序列int*benefit_array=NULL;//任务调度序列中每个任务的效益组成的数组93．3染色体结构和编码设计资源受限的多任务调度问题可以也看作是服从某些约束条件的排序问题。解决问题的关