第4期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·665· 对人力资源进行再进一步的划分，有不同维 {j{C.UA),P,∈Cn,rt≤Ru,k=1,2,…,Ko 修作业对用的维修人员种类以及根据不同维修能 并行调度方案产生从阶段n到阶段n+1描述 力不同导致的维修时间不等将维修人员划分为不 如下： 同等级： ①计算tn+,Ca+,An+,更新资源剩余量πRu和 ∑r度≤1=1,2…，Sk=12,,K Entli jEA ②若En+1中的工序资源需求不超过资源剩 2)消耗性资源是在装备维修保障作业启动时 余量，则执行j,更新En1,重复2)直至En+1为空。 以总量出现，并随着作业进展逐渐消耗的资源， 并行调度方案产生流程如下： 例如各种原材料、能源等。消耗性资源的约束表 ①初始化： 示为 n:=1,n=0,Em:=(1,An:Cn:=8Ru:=Rk,k=1, ≤k=lK 2.,Ko 3)时序约束：根据工艺要求限制工序顺序。 ②当1A.UCI<J时，对于每一阶段n: 如工序i未结束，工序j不开始。 t:min(ST;+diljEA1,A =A-\jljEA, 2.3常用算法 ST,td,=tn,Cn=Ca-u(jljEA-,ST,+d,=tnl,计算 常用遗传算法、禁忌搜索等算法解决任务调 Ra(t=1,2,…,K)和En;j广：=min,{jlv()=maXieE. 度问题。这些算法需合理编码，产生随机方案集 {v(0l,STn=tn,An=AnU{j},计算R(1=1,2,…, 并不断筛选更新种群，以求解问题。 K)和Emo 2.3.1编码 ③如果En≠空，继续执行②，否则n=n+1 1)活动编码0前部分表示子工序，后部分表 在解决问题方面，目前研究常建立多约束模 示工序工时； 型并利用启发式算法求解。但当前研究不能很好 2)资源编码表示工序维修在某时间内消 满足实际的RCPSP问题，文献[44]采用一种改进 耗资源量； 的离散布谷鸟搜索算法(IDCS)来解决RCPSP问 3)优先级编码前部分表示子工序，后部分 题，将搜索空间划分为多个区域，每个子群体将 表示占用工时。 专注于在其指定区域内搜索解决方案；文献[45] 2.3.2解码 考虑到每个活动都有固定的持续时间和资源需 调度方案(schedule generation scheme,.SGS)有： 求，将其建模为一个矩形块，其高度代表资源需 l)串行调度方案(serial SGS,SSGS) 求，宽度代表持续时间，将移动块序列解码为有 SGS随工序展开而进行扩展，分为J个阶 效的时间表，根据每个区块如何从其初始位置移 段，阶段n有对应不完全计划PS和对应的可行工 动到适当位置的情况，设计了4种移动模式，以最 序集En={jPSn,P,ePSn}。调度中新阶段n,选 大限度地缩短项目的完成时间，并采用多智能体 择En中某工序并入PS,工序开始时间满足资源和 进化算法(MAEA)求解RCPSP问题；文献[46]通 紧前约束。设工序j最晚开始时间ST,在t阶段， 过在最大的分割次数和最小的连续执行周期的约 正在维修的工序集合A,资源k剩余量R,则有 束条件下，研究在离散时间点上分割活动的资源 R=R-∑r,任务工期上限D,串行调度方案产 约束项目调度的并行调度方案产生流程问题；文 生流程为 献[4]通过将每个任务的处理时间被建模为其开 ①初始化n=1,PSn=1,ST1=0 始时间和特定退化日期的阶跃函数，利用改进的 ②当PS.l<j时，对于每一阶段n:计算En和 禁忌搜索算法进行求解，提出了基于问题特征的 Ru t=1,2,....K j:minjeE,[jlv(j)maxieE,(v(i) 4种邻域结构和两种变异算子；文献「48]提出基 ES,:=max{ST;+diiepr};STy:=min{teS,≤t≤ 于分散搜索的混合元启发式算法对工期最小资源 LSr≤Ru,T=t,t+1,…,t+d-1,k=1,2,…,K}; 约束项目调度问题求解；文献[49]提出基于蚁群 PS+1=PSnU{j};n=n+1。 的元启发式算法对考虑抢占惩罚的多技能资源约 2)并行调度方案(parallel SGS,PsGS) 束项目调度问题求解；文献[50]提出两阶段优化 PSGS随时间进行扩展，包含J个阶段，阶 算法对考虑人员能力差异的RCPSP求解；文献[5I] 段n调度时刻tn的3个工序集合：已完成工序Ca、正 研究了连续时间柔性资源配置的项目调度问题； 在维修工序An和可进行维修工序Ea,满足：En= 文献[52]采用预处理和在线调度两阶段策略及两对人力资源进行再进一步的划分，有不同维 修作业对用的维修人员种类以及根据不同维修能 力不同导致的维修时间不等将维修人员划分为不 同等级： ∑ j∈At r x jk ⩽ R x k , t = 1,2,··· ,SJ , k = 1,2,··· ,K 2) 消耗性资源是在装备维修保障作业启动时 以总量出现，并随着作业进展逐渐消耗的资源， 例如各种原材料、能源等。消耗性资源的约束表 示为 ∑ j∈J njk ⩽ nk , k = 1,··· ,K i j 3) 时序约束：根据工艺要求限制工序顺序。 如工序 未结束，工序 不开始。 2.3 常用算法 常用遗传算法、禁忌搜索等算法解决任务调 度问题。这些算法需合理编码，产生随机方案集 并不断筛选更新种群，以求解问题。 2.3.1 编码 1) 活动编码[40] 前部分表示子工序，后部分表 示工序工时； 2) 资源编码[41] 表示工序维修在某时间内消 耗资源量； 3) 优先级编码[42] 前部分表示子工序，后部分 表示占用工时。 2.3.2 解码 调度方案 (schedule generation scheme, SGS) 有： 1) 串行调度方案 (serial SGS, SSGS) J n PSn En = { j| j < PSn,Pj ∈ PSn } n En PSn j STj t At k Rkt Rkt = Rk − ∑ j∈At rjk D SGS 随工序展开而进行扩展[43] ，分为 个阶 段，阶段 有对应不完全计划 和对应的可行工 序集 。调度中新阶段 ，选 择 中某工序并入 ，工序开始时间满足资源和 紧前约束。设工序 最晚开始时间 ，在 阶段， 正在维修的工序集合 ，资源 剩余量 ，则有 ，任务工期上限 ，串行调度方案产 生流程为 ① 初始化 n := 1,PSn := {1},ST1 = 0 |PSn| < j n En Rkt t = 1,2,··· ,K j ∗ : = minj∈En { j|v (j) = maxi∈En {v (i)} } ESj ∗ : = max{ STi + di |i ∈ pj ∗ } STj ∗ : = min{ t|ESj ∗ ⩽ t ⩽ LSj ∗ ,rj ∗ k ⩽ Rkt,τ = t t+1, ··· , t+dj ∗ −1, k = 1, 2, ··· , K} PSn+1 = PSn ∪{j ∗ } n := n+1 ② 当 时，对于每一阶段 ：计算 和 ， ； ； ； ， ； ； 。 2) 并行调度方案 (parallel SGS, PSGS) J n tn Cn An En En = PSGS 随时间进行扩展[43] ，包含 个阶段，阶 段 调度时刻 的 3 个工序集合：已完成工序 、正 在维修工序 和可进行维修工序 ，满足： { j| j < {Cn ∪ An},Pj ∈ Cn,rjk ⩽ Rktn , k = 1,2,··· ,K }。 并行调度方案产生从阶段n到阶段n+1 描述 如下： tn+1 Cn+1 An+1 πRkt En+1 ① 计算 ， ， ，更新资源剩余量 和 ； En+1 j j En+1 En+1 ② 若 中的工序 资源需求不超过资源剩 余量，则执行 ，更新 ，重复 2) 直至 为空。 并行调度方案产生流程如下： ① 初始化： n := 1,tn := 0,En := {1},An : Cn := φ Rkt0 := Rk , k = 1, 2,··· ,K ， 。 ② 当 |An ∪Cn| < J 时，对于每一阶段n： tn : = min{ STj +dj | j ∈ An−1 } An : = An−1\ {j| j ∈ An−1, STj +dj = tn } Cn := Cn−1 ∪ { j| j ∈ An−1,STj +dj = tn } Rkt (t = 1, 2, ··· , K) En j ∗ : = minj∈En { j|v (j) = maxi∈En {v (i)}} STj∗ := tn An := An ∪{j ∗ } ， ， ，计算 和 ； ， ， ，计算 Rkt(t=1, 2, ···, K) 和 En。 ③ 如果 En , 空 ，继续执行②，否则n := n+1 在解决问题方面，目前研究常建立多约束模 型并利用启发式算法求解。但当前研究不能很好 满足实际的 RCPSP 问题，文献 [44] 采用一种改进 的离散布谷鸟搜索算法（IDCS）来解决 RCPSP 问 题，将搜索空间划分为多个区域，每个子群体将 专注于在其指定区域内搜索解决方案；文献 [45] 考虑到每个活动都有固定的持续时间和资源需 求，将其建模为一个矩形块，其高度代表资源需 求，宽度代表持续时间，将移动块序列解码为有 效的时间表，根据每个区块如何从其初始位置移 动到适当位置的情况，设计了 4 种移动模式，以最 大限度地缩短项目的完成时间，并采用多智能体 进化算法（MAEA）求解 RCPSP 问题；文献 [46] 通 过在最大的分割次数和最小的连续执行周期的约 束条件下，研究在离散时间点上分割活动的资源 约束项目调度的并行调度方案产生流程问题；文 献 [47] 通过将每个任务的处理时间被建模为其开 始时间和特定退化日期的阶跃函数，利用改进的 禁忌搜索算法进行求解，提出了基于问题特征的 4 种邻域结构和两种变异算子；文献 [48] 提出基 于分散搜索的混合元启发式算法对工期最小资源 约束项目调度问题求解；文献 [49] 提出基于蚁群 的元启发式算法对考虑抢占惩罚的多技能资源约 束项目调度问题求解；文献 [50] 提出两阶段优化 算法对考虑人员能力差异的 RCPSP 求解；文献 [51] 研究了连续时间柔性资源配置的项目调度问题； 文献 [52] 采用预处理和在线调度两阶段策略及两 第 4 期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·665·