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

1实验成绩华中师范大学计算机科学系实验报告书实验题目：基于遗传算法的多任务调度研究课程名称：智能计算主讲教师：沈显君辅导教师：课程编号：班级：2011级实验时间：2011年11月姓名何印标学号20111129152基于遗传算法的多任务调度研究摘要：本文主要讨论了遗传算法在工程项目中多任务执行优化中的应用，重点对多任务调度(Resource—constrainedprojectschedulingproblem，RCPSP)问题进行了研究。讨论了资源受限的多任务调度问题，提出了改进的遗传算法优化多任务调度问题的方法，主要从优化算法模型的建立，优化算法设计，算法的实现以及结果分析等几个方面进行了详细论述，并与其它启发式方法进行了对比分析。关键字：效益最优化；遗传算法；多任务1．简介任务调度优化在工程项目管理中是非常重要的，它决定了工程项目利润的高低。遗传算法是一种并行的全局搜索的高效求解问题的方法，本质上就是处理离散优化搜索问题的，它不要求问题空间的连续性，不需要梯度信息，其鲁棒性(Robust)已经得到了证实，在处理大型复杂优化问题上己经取得了显著的成绩，所以在解决多任务调度优化问题时，具有其它方法无法比拟的优势。2．多任务调度模型的建立假设存在若干并行任务和一个共享的资源库，包含有若干种可更新资源(renewableresources)，并且所有资源都只有有限的供给量。任务之间除了共享资源外互相独立。为方便对问题进行描述，建立如下的数学模型：多任务调度问题有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上处理所得的效益值。intnum_of_job;//任务数，存储在文件numoftm.txtintnum_of_machine;//处理机数，存储在文件numoftm.txtintnum_of_chromosomes;//群体数，存储在文件numofcolony.txtintnum_of_gen;//产生的代数，也就是最后产生的那个代的序数，存储在文件num_of_gen.txtint**colony=NULL;//任务序列int*benefit_array=NULL;//任务调度序列中每个任务的效益组成的数组43．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染色体邻域示意图6BeginIf(rand()pmutation)在该染色体中任取n个连续的基因；对n个基因进行排列组合；检查各个基因序列，如果该基因序列不合理则将其舍弃；评估所有邻域调度；选择最好邻域作为后代；End因为在变异过程中是对n个连续的基因进行完全排列组合，则其中必然存在违反约束关系的基因序列，此处直接将其舍弃即可，而不会对最好邻域的选择产生影响，使用本方法可以避免变异后对染色体的修复，提高了程序的效率。3．6评价函数要计算出多个任务的最短工期，首先要对染色体进行解码，计算所有工作的最早可能开始时间，然后求出每个任务的最早完工时间，最后根据各个任务的权重比例，计算出加权的最短平均工期。得出目标函数公式（8）：PknkkkS1,)1(*min（8）由于RCPSP问题是最小化任务总工期，所以要对原始目标函数进行转换，以确保适合的个体具有最大的适应值。设vk是当前种群的第k个染色体，g(vk)是适应值函数，f(vk)是原始目标值，fmax和fmin分别是当前种群的最大目标值和最小目标值。转换方法如公式（9）minmaxmax)()(ffvffvgkk（9）其中ε是正实数，通常限制在开区间（0，1）中。3．7选择算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择。目前常用的选择策略有基于“繁殖池(BreedingPool)选择”、“适应值比例的选择”、“基于排名的选择(RankingSelection)”。“基于局部竞争机制的选择”等。轮盘式选择(RouletteWheelSelection)[11]是基于适应值比例的一种应用最多的选择方式。它是先计算个体的相对适应值fi/∑fi，记为Pi，然后根据选择概率{pi,i=1,2,…,N}把一个圆盘分成N份（如图2），其中第i扇形的中心角为2лPi。在进行选择时，可以假想转动圆盘，若某参考点落入到第i个扇形内，则选择个体i。如图1所示,：7图2转盘式选择先生成一个[0，1]内的随机数r，若Po+Pi+…+Pi-1rPl+P2…+Pi，则选择个体i，此处