第4期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·663· 调度问题，并采用NSGA-Ⅱ算法求解；文献[9]提 忌搜索算法叨采用禁忌表避免重复搜索，对初始 出了涉及剩余寿命的调度模型，采用改进遗传算 解敏感；遗传算法采用选择、交叉、变异算子对 法求解；文献[10]提出了鲁棒双目标混合整数线 初始种群进行优化，搜索能力强但速度缓慢；人工 性规划模型，在不确定条件下同时最小化维修总 智能方法采用智能系统动态优化，如神经网络 成本和最大化任务总浮动：文献[11]在车辆正常 专家系统0、蚁群算法U、粒子群算法四等。 运行的情况下，模拟车辆的周期维修，在给定的 综上，当前针对资源受限的任务调度问题研 时间内安排维修任务，优化车辆运营、降低成本 究仍存在以下问题： 和提高服务可靠性；文献[12]提出了带重调度的 1)目前对于装备维修保障的研究与作战实践 维修方案，信息跟新后进行重调度；文献[13]利 背景、任务装备重要度等结合不够紧密。 用混合粒子群遗传算法解决无人机装备军事维修 2)装备维修保障任务种类多、需求大，在资 任务调度问题；文献[14]提出了混合整数线性规 源有限情况下，必须优先修复关键装备，故确定 划以优化列车运行维修延成文；文献[15]研究了 任务优先级是首要工作。现阶段对任务优先级的 任务优先级，改善马氏距离，并提出了逼近理想 研究常忽略了装备重要度。 解排序法；文献[16]以优化维修重要度为目标， 3)信息化条件下，保障需求可及时传达，这 采用改进蚁群算法求解；文献[17-18]给出的方案 对维修时效性要求更加苛刻。但现阶段任务调度 可用于伴随维修；文献[19]利用采用离散事件仿 常为静态问题，不能满足实际需求。 真对定点维修任务调度求解。 2工序调度 1.4动态调度算法 其中，因战时维修任务多、时间紧，维修部队 军用装备保障对象复杂、要素众多、环境多 赶至战损装备处的伴随维修，可参考动态车辆路 变。任务调度需要根据维修保障任务与资源的关 径问题(dynamic vehicle routing problem,DVRP)或 系及任务间工序的关系，建立约束性规则，主要 动态旅行商问题(dynamic traveling salesman prob- 包括： lem,DTSP)以求解o。 1)资源充足前提下，任务才能开始： 1)静态化动态问题 2)维修任务须按工序流程进行； 目前研究成果常对动态调度静态化转换P以 3)正在使用的资源不得同时被任务占用，直 求解。文献22]分割调度时间，将动态车辆路径 到任务完成： 问题静态化；文献[23]对DVRP优化时间选择以 4)维修任务独立，任务间互不影响。 静态化求解；文献[24]拆分DVRP为车辆选择及 在最短时间内形成维修保障工序调度方案 路线优化问题，并两阶段法数学规划求解；文献 可提升保障效能。维修时人员分配不当、维修调 [25]动态调度多维修点、多任务、多维修队，划分 度不周等影响任务完工时间，资源受限工序调度 时间保证任务优先级以实现静态化求解。 诣在合理的安排工序调度以缩短工时、减少成 2)静态问题算法 本，可转化为资源受限项目调度问题(resource- 维修任务调度是NP-hard问题，需采用模拟 constrained project scheduling problem,RCPSP). 退火、禁忌搜索等算法求解。模拟退火算法采 装备维修工序调度流程如图4所示。常见调 用蒙特卡罗迭代求解，效果良好但收敛缓慢：禁 度问题如下： 准备 资源请求 开始 维修排故 结束 维修保过 资源需求 工序调度 工序调度 工序调度过 资源分配 资源池 图4装备维修工序调度流程 Fig.4 Equipment maintenance process scheduling process调度问题，并采用 NSGA-II 算法求解；文献 [9] 提 出了涉及剩余寿命的调度模型，采用改进遗传算 法求解；文献 [10] 提出了鲁棒双目标混合整数线 性规划模型，在不确定条件下同时最小化维修总 成本和最大化任务总浮动；文献 [11] 在车辆正常 运行的情况下，模拟车辆的周期维修，在给定的 时间内安排维修任务，优化车辆运营、降低成本 和提高服务可靠性；文献 [12] 提出了带重调度的 维修方案，信息跟新后进行重调度；文献 [13] 利 用混合粒子群遗传算法解决无人机装备军事维修 任务调度问题；文献 [14] 提出了混合整数线性规 划以优化列车运行维修延成文；文献 [15] 研究了 任务优先级，改善马氏距离，并提出了逼近理想 解排序法；文献 [16] 以优化维修重要度为目标， 采用改进蚁群算法求解；文献 [17-18] 给出的方案 可用于伴随维修；文献 [19] 利用采用离散事件仿 真对定点维修任务调度求解。 1.4 动态调度算法 其中，因战时维修任务多、时间紧，维修部队 赶至战损装备处的伴随维修，可参考动态车辆路 径问题 (dynamic vehicle routing problem, DVRP) 或 动态旅行商问题 (dynamic traveling salesman prob￾lem, DTSP) 以求解[20]。 1) 静态化动态问题 目前研究成果常对动态调度静态化转换[21] 以 求解。文献 [22] 分割调度时间，将动态车辆路径 问题静态化；文献 [23] 对 DVRP 优化时间选择以 静态化求解；文献 [24] 拆分 DVRP 为车辆选择及 路线优化问题，并两阶段法数学规划求解；文献 [25] 动态调度多维修点、多任务、多维修队，划分 时间保证任务优先级以实现静态化求解。 2) 静态问题算法 维修任务调度是 NP-hard 问题，需采用模拟 退火、禁忌搜索等算法求解。模拟退火算法[26] 采 用蒙特卡罗迭代求解，效果良好但收敛缓慢；禁 忌搜索算法[27] 采用禁忌表避免重复搜索，对初始 解敏感；遗传算法[28] 采用选择、交叉、变异算子对 初始种群进行优化，搜索能力强但速度缓慢；人工 智能方法采用智能系统动态优化，如神经网络[29] 、 专家系统[30] 、蚁群算法[31] 、粒子群算法[32] 等。 综上，当前针对资源受限的任务调度问题研 究仍存在以下问题： 1) 目前对于装备维修保障的研究与作战实践 背景、任务装备重要度等结合不够紧密。 2) 装备维修保障任务种类多、需求大，在资 源有限情况下，必须优先修复关键装备，故确定 任务优先级是首要工作。现阶段对任务优先级的 研究常忽略了装备重要度。 3) 信息化条件下，保障需求可及时传达，这 对维修时效性要求更加苛刻。但现阶段任务调度 常为静态问题，不能满足实际需求。 2 工序调度 军用装备保障对象复杂、要素众多、环境多 变。任务调度需要根据维修保障任务与资源的关 系及任务间工序的关系，建立约束性规则，主要 包括： 1) 资源充足前提下，任务才能开始； 2) 维修任务须按工序流程进行； 3) 正在使用的资源不得同时被任务占用，直 到任务完成； 4) 维修任务独立，任务间互不影响。 在最短时间内形成维修保障工序调度方案， 可提升保障效能。维修时人员分配不当、维修调 度不周等影响任务完工时间，资源受限工序调度 诣在合理的安排工序调度以缩短工时、减少成 本，可转化为资源受限项目调度问题 (resource￾constrained project scheduling problem, RCPSP)。 装备维修工序调度流程如图 4 所示。常见调 度问题如下： 准备 资源请求 开始 维修排故 结束 资源需求 工序调度 资源分配 工序调度 资源池 维修保障过程 工序调度过程 图 4 装备维修工序调度流程 Fig. 4 Equipment maintenance process scheduling process 第 4 期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·663·