研究多次抢占式资源受限的项目调度问题，假设任意时间点可作为资源抢占节点且抢占次数不受限制，建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷，在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数，并以标准算例集（Project Scheduling Problem Library，PSPLIB）对算法进行可行性检验。实验结果表明，资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期，设计的算法对问题求解效果良好。
祝政,等:多次抢占项目调度问题的混合遗传算法 2019,55(6)227 表1参数符号及其含义 上述小规模 RCPSP,由于其网络复杂度较低,通过 符号 含义 精确算法求得工作·次性调度下的最优方案。项目单 JTR 项目工作集合 位时间资源使用量如图2所示。 项目上期上界 资源集合,k=1,2,…,K 工作序号,j=(,1,…,n+1 执行T作所需必要T作时门 执行工作从开始到结束实际消耗时 工作的结束时间点 执行工作;时资源的使用量 决策变量 10 15 T 时间/天 建立 Im PRCPSP调度模型如下 图2不含资源抢占的 RCPSP最优调度方案 min 从图2屮可以看出,项目整体持续时问为15天,其 ●(2)中7天未实现资源利川最大化,特确算法虽可以求得 RCPSP的最优调度方案,但是上述方案仍然有大量资源 ∑y2=1,j=0,1,2 (3)出现闲置,难以实现资源连续高效使用。由于完成项目 l2≤l-l1,V()∈G (4)所需的资源总量确定,项目T期会随单位时间资源利用 率的降低而延长,若能提高单位时间资源利用率,就能 >(t2-41+1)+Ty1+y2-2<(5)缩短整个项的完成时间。 ∑k:≤R,k=,2…,K (6) PRCPSP以单位时间节点作为L作抢占点,在满足 7≤∑ym2=0,1,2,…,n+1 (7) 资源约束和前后关系约東的前提下,允许其他满足进行 糸件的工作抢占当前进行T作的资源并优先进行。当 0,1} (8)采取抢占式调度方案时,能有炇地避免上述资源闲置所 目标函数(1),要求完成全部工作所需时间最小;约带来的工期顺延。 束函数(2)表示工作j最小完成工期;约束函数(3)表示 工作在资源抢占环境下的实际工期;约束函数(4)表3算法设计 示工作的时序约束,即紧前工作全部完成方可进行后续 遗传算法是模拟生物进化过程搜索最优解的方法, L作;约束函数(5)表示活动进行过程中的任意时间间算法将其求解的问题以“染色体”的形式表现,采用“适 隔不超过当前工作总时间;约束函数(6)表示任意时刻者生存”的原则对种群内染色体进行选择、交义、变异操 资源使用量不超过资源总量;约束函数(7)表示工作实作,以获得高适应度子代个体。遗传算法因其本身具有 际持续时间不能少于必要时间;约束函数(8)表示决策强大的自适应性、可扩展性及群体进化能力被广泛应川。 变量。 棼忌搜索算法属于邻域搜索算法,具有自适应的仵 假设一个包含11个工作的项目,作0和工作10储记忆功能。算法从一个初始可行解开始,搜索过程屮 分别是表示开始和结束的虚拟任务,其余工作均为需要通过禁忌表避免迂叫搜索,同时可通过藐视准则特赦被 时间和可再生资源的实际工作。工作之间的树络关系禁忌的最优解,从而实现对问题的高效优化。 与约東信息如图1所示 通过将禁忌搜索引入遗传算法,充分利川遗传算法 3/7 3/6 的全局搜索能力,使群体中的个体广泛分布于解空间, 同时利用禁忌搜索对初始解进行局部搜索,禁忌搜索所 0/0 具有的记忆能力和藐视准则,有助于在搜索过程中跳出 5)8)10 局部最优解,从而保证种群个体多样性,避免算法“早熟” 1/4 4/3 3.1基于优先权值的编码方案 本文采用优先权值编码方案,其屮包含活动编号和 图1工厅关系与约束信息图 优先权值两部分构成,其中优先权值m)由基础优先 以T作8为例,下作8的开始以下作5和6同时完成权值v和随机优先权值ym构成。首先基于关键路 为前提,工作8的开始时间为前序任务的最晚的结束时径技术分别赋予各链路上任务不同的基础优先权值 间,且完成工作8需要至少3个单位时间,各单位时间内,其中w=1,2.…,J;然后在基础优先权值w的基础 供应的可更新资源不少于2个单位数量。 对子工作赋予随机优先权y1,其中y(m)=1,2…,J, 2282019,55(6) Computer Engineering and Applications计算机工程与应用 表2基于优先权的编码方案 活动编号 子工作 (21)(2,2) (1)(2) 优先权ga,na,2 m2=1,2,…,d,。从而工作间优先权值互不相等,当多个越短对应的种群适应度越大。因此,函数f()可转化为 任务同时被调度时,算法根据可执行工作的优先权值对 T-f(k) 其进行排序,选择优先权值最高的L作优先执行。针对 gk- TO 抢占这特点预设每个整数时间点均为潜在的被抢占其中,了代表集合全部工作必要时间总和,x为 时间点,被抢占后的子工作记做(m),故工作的子适应度函数,保证了完成时间短的个体获得更高适应度 工作对应优先集合记做9…9=}。染色34选择算子 体结构如表2所示 通过对种样个体进行适应度计算,从旧种群中选取 士述编码方式在保址高优先级T作获得优先调度适应度高的染色体组成新种群。文中采用比例选择 资格的同时,对项目工作赋予了两两互不相等的优先权( proportional selection)略,根据个体适应度的不同 值,避免不同工作相同优先权带来的冲突,提高了算法以相应概率进入下一代,种群屮个体适应度越高,被选 的计算性能 择的概率也就越大,保证了下一代获得更多高适应度个 3.2基于串行调度生成机制的解码方案 体。公式如下 串行调度生成机制( Serial schedule generation =8(k) (10) Scheme,SSGS)2是·种基于CPM/PERT原理设计的将 工作优先权转化成可行调度计划的算法。 本文SsGs解码方案具体思路是:将活动调度划分3 5交又算子 为若干阶段∈1.2.…,T,其中T代表当每个单位时 交叉算子模拟经自然选择后存留的亲代染色体交 间点都被抢占的情况下的最大子⊥作个数,建立代表已又重组产生新染色体的过程。本文采用基于部分映射 确定开始时间并分配了满足所需资源的工作集合17n 策略的两点交叉(two- point crossover)算子。种群屮任 建立代表尚未确定开始时间且未分配所需资源的工作意选取一对染色体父本和母本分别记作Xx=h 集合m/1,要求所,和m集合中任一工作在任意调}、X=团…,随机选取整数x和乙2作为染 度阶段中均互斥且交焦为所有子工作集合。对每一调色体交叉点,其中1≤≤z≤7,将染色体中基因位序 度阶段抽取当前阶段中满足紧前逻辑关系的工作集合号满足1,可]的基因交叉互换,对产生的一对子代进行 D,及集合D中工作对应的优先权值,基于优先权的高冲突检验,当单个子代中含有成=,取不属于集合 低从工作集合my中选择满足项目当前时间点最大可[r,2]的基因建立重复工作集合矩阵=i;,在一对 用资源约束的活动疒,令其开始实施并赋予相应資源,子代中取序号为引、2:0≤≤J相互交换,保证子代中 直至阶段结束并更新fn2、mn以及资源集合 工作不被重复。 解码方案流程描述如下 3.6禁忌变异算子 BEGI 变异算子模拟染色体在遗传过程中基因突变的过 f2=[1; 程。解决 RCPSP的变异算子大多采用任务链表的插入 WHILE-isempty(unp) 变异法,即将抽取变异基因插入满足条件的新基因位。 Compute: D,∈f} 山于 RCPSP插入基因需要同时考虑工序与资源双重约 sect:mxOD2)=j,∈D 東,上述变异策略难以提高解的多样性。 StribuLIoll:T 为解决上述问题,设计禁忌变异算子,思路如下:取 Update: R, -R,->>0,/inp, un/ 选择、交叉后的某较优个体作为禁忌的初始解xm,同 END WHILE 时初始化禁忌表L与迭代次数Nwm;根据两两交换规 END 则生成当前解的邻域解sxm),并从中选取候选解xMm 33适应度函数 若解满足藐视准则,则将其设置为当前解τυ,替换禁 算法中解码调度函数∫为项目全部T作的完成忌对象,并更新最优值,否则取非禁忌对象中最优解作 时间, RCPSP以求取最短的项H完成时间为H标函数,为当前解,并替换禁忌表中对象,迭代直至满足终止条 即要求种群中染色体解码产生的进度计划完成总时间件Nam 祝政,等:多次抢占项目调度问题的混合遗传算法 2019,55(6)229 37算法步骤 同时,缩短了项目的总体完成时间 设种群规模记作P2,当前种群代数记作gemn,为进步检证文中所提抢占模型及其算法可行性, 其中最大代数为 Maxgen,交叉概率记作P,算法基本采用 Kolisch构建的标准算例库 PSPLIB中单模式RCP 流程如卜 SP算例进行算法性能测试。算例中的每个工作最多有 BEGI 3个紧后任务,共涉及调度4种可更新资源,并限制每种 Parametcr: Popsieeo, MarGen, P. 资源的可用上限。算例库中算例有4种规模,以其⊥作 Set: InitPop; gen=l 数量划分分别为J30、J60、J90、J120,其中算例库已公布 Compute: Fitness gen J30算例在非抢占情况下的精确算法最优解。本文采用 While ge7≤ Margen; J30算例作为算法的实验数据对算法进行可行性验证。 Pair: Group=Popsize /2 遗传算法求解受算法参数影响,为保证算法求解效 er: turo foint 果,拟对交叉概率P和变异概率Pn进行参数调试。首 先对30中部分算例进行实验,确定算法参数。统计 Compute Fitness(mergen 中各算例的持续时间,依据分层抽样原则,将J30的480 Popszie=2xpops 个算例依最优工期长短分成6组,后从各组中按比例随 Update:gen=gen+1 机抽取相应个数算例作为调试参数样本,计算样本在不 Select:Popsize=Popsize. 同参数下的求解效果。此处以最优解比率Op作为参 END WIIILE 数有效性评价标准,即算法产生的最优调度数占全部调 END 度次数的百分比。 当初始种群规模预设为100,不同P、Pm对Opt的 4算例分析 影响如图5和图6所 结合本文模型及所提算法对所举算例进行分析 假设其工作允许抢占,但是限制其最大抢占次数为 0.720 0.715 时,其他条件不做变化,得到相应调度方案2,项目咩位 0.710 时间资源使用量如图3所示。 0.705 0.695 2 7 0.690 0.685 040.50.60.70.80.9 2 9 图5不同P对优化结果的影响 10 .720 时间/天 图3一次抢占 PRCPSP最优调度方案 0.715 0.710 调度方案2总持续天数为15,项目实现资源最人利 用时间为12。相比方案1其前期资源得到了连续高效 .705 使用,实现了利用率最大化,但1 PRCPSP的项目完成 0.700 时间没有得到缩减 0.695 针对此案例采用多次抢占策略做进一步优化,得到 00.050.100.150.20 相应调度方案3,项目单位时间资源使用量如图4所示。 图6不同P。对优化结果的影响 经上述分析,设置算法屮种群规模为100,交叉概率 2 为0.75,变异概率为0.05,每个算例均进行5000次调 度,并统计其调度结果 算法性能衠量指标为最优解比率Oφt、更优解比率 Betr最大偏差率MaDe以及平均偏差率 AgdEr。 Her为所有调度结果中小于 RCPSP模聖最优斛的个 时间/天 数占调度总数的比例,其数值主要用于评估算法的求解 图4多次抢占 PRCPSP最优调度方案 质量, beller值越大,算法对问题优化性能越好; Aug Dea 调度方案3总持续天数为14,顼目实现资源最大利为所有调度结果与 RCPSP模型最优解的偏差比率均 用时间为11。方案3在实现资源使用的稳定性优化的值, Mardev为所有调度结果与 RCPSP模型最优解的 2302019,55(6) Computer Engineering and Applications计算机工程与应用 最大偏差比率,各偏差率指标可以综合评估算法的求解2]| Kolisch r, Drexl A Local search for nonpreemptive multi 稳定性以其对模型的优化性能,分析结果见表3。 mode resource-constrained project scheduling j]. IIE Tran 表3两种抢占策略对J30算例的优化结果 actions,1997,29(11):987-999 [3]Zhao w, Ramamritham K, Stankovic J A Preemptive sched Opt Better Max Dev AvgDev uling under time and resource constraints[J].IEEE Trans RCPSP(GA 0 6.73 actions on Computers, 1987,36(8):949-960 RCPSP(PSO)4.96 6.78 0.40 I PRCPSP(GA)”68.1323755.88 4 Cheng 3, Fowler JMulti-mode resource-constrained project PRCPSP(PSO)68.752438441 0.43 scheduling problems with non-preemptive activity splitting m PRCPSP(GA) 67. 15 26.467.6 Computers Operations Research, 2015, 53(C): 275-287 m PRCPSP(GTSA)71.2427.0146.32 [51 Ballestin F, Valls V, Quintanilla S Preemption in resource- constrained project scheduling[]. European Journal of Oper- 考虑到程序的不同运行环境可能会带来的求解时 tional research,2008,189(3):1136-1152 间差异,故仅对模型及算法对算例的优化效果进行对6 Demeulemeester E l, Herroelen W s. An efficient optimal 比。从表3可以看出, m PrCPsP(GA)有6715%的解 solution procedure for the preemptive resource-constrained 实现精确算法对非抢占条件下的最优调度王期其中有 project scheduling problem[J]. European Journal of Op 26.46%结果优于最优工期,而 m PRCPsP(GTSA)所求 ational Research, 1996, 90(2): 334-348 结果中有71.24%实现最优调度,其中27.01%结果实现7 Kaplan L AResource-constrained project scheduling with 对最优解的进一步优化,且 m PRcpsp(GTSA)相对于 preemption of jobs[D- Michigan: University of Michigan M PRCPSP(GA)调度优化程度以及算法稳定性均有所 提升;对比1 PRCPSP与 m PRCPsP数据可以看出 [8] Damay JLinear programming based algorithms for pre 1 PRCPSP(PSO)其有最小的 Max Dev值,即其有较高的 ptive RCPSPuI 求解稳定性,然而对算例的优化比例稍差于 m PRCPSP nal of Operational Research, 2007, 182(3): 1012-1022 [9] Muukrim A, Quilliot A, Toussaint HAl (GTS∧);参照 RCPSP的求解数据,抢占机制的引入可 price algorithm for the preemptive resource constrained 有效缩短项日工期,但是Opt值也出现不同程度的下 project scheduling problem based on minimal interval 降,即算法的求解性能会随网络复杂度的升高而降低。 order enumeration [J] .European Journal of Operational 实验结果分析表明,相比单纯的遗传算法,遗传禁忌搜 Research,2015,244(2):360-368 索算法可以有效避免其陷入局部最优解,从而获得更多[10陆志强,杨超基于项冈络拆分决策的多项日协同调度 高质量解。 回题建模[J.上海交通大学学报,2017,51(2):193-2 [l]1王磊,聂兰顺,战德臣,等.求解任务可拆分多项目协同 5结束语 调度问题的启发式算法门.控制与决策,2017,32(6) 1013-1018 当前 RCPSP的研究主要局限于经典情形下的单模12寿涌毅,彭晓峰,李菲抢占式资源受限项目调度问题的 式或多模式问题,少有研究涉及到抢占式调度。本文对 遗传算法浙江大学学报(工学版),2014(8):1473-1480 有限资源情形下多次抢占项目调度问题展开讨论,设置13] Kelley j F The critical- ath method: resource plannin 仟意整数时点为抢占点,建立多次抢占的 PRCPSP模 and scheduling [J]. Industrial Scheduling, 1963, 37(11) 型。利川GA求解项目调度问题的高效性,设计基于多 108-111 次抢占的改进优先级编码及牛行调度生成机制解码方[14] Shou y,LiY, Lai C Hybrid particle swarm optimize 案,确保高优先级任务能被及时实施,被抢断的T作尽 lion for preemptive resource-constrained project sched 早恢复;同时结合禁忌搜索的局部搜索能力,设计改进 ung[小」 Neurocomputing,2015,148:122-128 的禁忌变异算子,调试算法参数,提高算法在出现大规151 Javanmard, Afshar-Nadjafi B, Niaki S T A Preemptive 模抢占情况下的运算效率。实验结果表明, RCPSP中引 multi-skilled resource investment project scheduling prob 入多次抢占能有效缩短项目工期,改进的遗传禁忌搜索 lem mathematical modelling and solution approaches[I] 算法比单纯的遗传算法具有更强的稳定性与搜索能力 Computers Chemical Engineering, 2016, 96(C): 55-68 模型对多次抢占的 PRCPSP基本问题进行求解研l61王伟鑫,王旭,葛显龙任务可拆分的多模式多项目调度模 型与算法门J计算机集成制造系统,2014,20(6):1388-139′ 究,而此问题中抢占惩罚这一假设的加入可以提高模型 [17 Kolisch R, Sprecher A PSPLIB: a project scheduling prob- 的实际意义,故在后续的工作中将对其进一步探讨 lem library[J]. uropean Journal of Operational Research 1996,96(1):205-216. 参考文献: [18 Peteghem VV, Vanhoucke MA genetic algorithm for [ 1] Weglarz J, Mika M Project scheduling with finite or infi the preemptive and non-preemptive multi-mode resource nite number of activity processing modes-a survey[J].Euro constrained project scheduling problem []. European Jour- pean Journal of Operational Research, 2011. 208(3): 177-205 nal of Operational Research, 2010, 201(2): 409-418