第17卷第4期 智能系统学报 Vol.17 No.4 2022年7月 CAAI Transactions on Intelligent Systems Jul.2022 D0:10.11992/tis.202109009 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20220614.1319.002.html 面向多维修中心的资源受限任务调度问题研究 齐小刚，陈玲琳2，宋卫星3，王亚洲，刘立芳4 (1.西安电子科技大学数学与统计学院，西安710071；2.陆军工程大学军械士官学校，武汉430075,3.中国人 民解放军32272部队11分队，兰州730060：4.西安电子科技大学计算机科学与技术学院，西安710071) 摘要：装备维修保障对推进作战顺利进行具有重要作用，合理高效的维修任务调度是维修保障的主要内容。 首先讨论了资源受限伴随维修保障任务调度下的资源分类、优先级评估指标、维修调度模型、动态调度算法： 其次分析了装备维修工序调度的流程：然后介绍了常见调度问题的目标函数、约束条件、求解算法：最后总结 了资源受限任务调度存在的开放性问题和未来的发展方向。 关键词：维修保障；多维修中心；资源受限：调度模型：评估指标：动态调度：抢占；工序调度 中图分类号：TP273文献标志码：A文章编号：1673-4785(2022)04-0661-09 中文引用格式：齐小刚，陈玲琳，宋卫星，等.面向多维修中心的资源受限任务调度问题研究.智能系统学报，2022,17(4)： 661-669. 英文引用格式：QI Xiaogang,CHEN Linglin,SONG Weixing,ctal.Resource constrained task scheduling for multiple maintenance centersJ.CAAI transactions on intelligent systems,2022,17(4):661-669. Resource constrained task scheduling for multiple maintenance centers QI Xiaogang',CHEN Linglin',SONG Weixing,WANG Yazhou',LIU Lifang' (1.School of Mathematics and Statistics,Xidian University,Xi'an 710071,China;2.Ordnance NCO Academy,Army Engineering University of PLA,Wuhan 430075,China;3.Unit 11 of the 32272 Troop of the Chinese People's Liberation Army,Lanzhou 730060, China;4.School of Computer Science and Technology,Xidian University,Xi'an 710071,China) Abstract:Equipment maintenance support plays an important role in advancing the smooth progress of operations. Reasonable and high-efficiency maintenance task scheduling is the main content of maintenance support.In this study, the resource classification,priority evaluation index,maintenance scheduling model and dynamic scheduling algorithm under resource constraints and maintenance support task scheduling are discussed firstly,then the scheduling process of equipment maintenance procedures is analyzed,and then the objective function,constraint conditions and solving al- gorithm of common scheduling problems are introduced.Finally,the open problems and future development directions of resource-constrained task scheduling are summarized. Keywords:maintenance support;multi-maintenance center,resource constraints;scheduling model;evaluation index; dynamic scheduling;preemption;process scheduling 当今信息化作战条件下，充分利用战场信息 能力；其次，装备的研制也需要合适的调度，以减 资源、合理进行维修任务调度，影响着我军作战 少费用；再次，战时维修任务时间紧迫，维修资 胜利使命的完成。首先，战时维修时间有限，我 源有限，如何在最短的时间内合理安排各工序的 军需合理进行任务调度以快速恢复故障装备作战 顺序，分配维修保障资源使得调度方案最优也是 至关重要的。 收稿日期：2021-09-02.网络出版日期：2022-06-14. 基金项目：国家自然科学基金项目(61877067)：装备预研领域 1资源约束的任务调度 基金项目(80904010301). 通信作者：齐小刚.E-mail:xgqi@xidian..edu.cn. 资源约束的维修任务调度涉及任务的分配
DOI: 10.11992/tis.202109009 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20220614.1319.002.html 面向多维修中心的资源受限任务调度问题研究 齐小刚1 ，陈玲琳2 ，宋卫星3 ，王亚洲1 ，刘立芳4 （1. 西安电子科技大学 数学与统计学院，西安 710071; 2. 陆军工程大学 军械士官学校，武汉 430075; 3. 中国人 民解放军 32272 部队 11 分队，兰州 730060; 4. 西安电子科技大学 计算机科学与技术学院，西安 710071） 摘 要：装备维修保障对推进作战顺利进行具有重要作用，合理高效的维修任务调度是维修保障的主要内容。 首先讨论了资源受限伴随维修保障任务调度下的资源分类、优先级评估指标、维修调度模型、动态调度算法； 其次分析了装备维修工序调度的流程；然后介绍了常见调度问题的目标函数、约束条件、求解算法；最后总结 了资源受限任务调度存在的开放性问题和未来的发展方向。 关键词：维修保障；多维修中心；资源受限；调度模型；评估指标；动态调度；抢占；工序调度 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2022)04−0661−09 中文引用格式：齐小刚, 陈玲琳, 宋卫星, 等. 面向多维修中心的资源受限任务调度问题研究 [J]. 智能系统学报, 2022, 17(4): 661–669. 英文引用格式：QI Xiaogang, CHEN Linglin, SONG Weixing, et al. Resource constrained task scheduling for multiple maintenance centers[J]. CAAI transactions on intelligent systems, 2022, 17(4): 661–669. Resource constrained task scheduling for multiple maintenance centers QI Xiaogang1 ，CHEN Linglin2 ，SONG Weixing3 ，WANG Yazhou1 ，LIU Lifang4 (1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China; 2. Ordnance NCO Academy, Army Engineering University of PLA, Wuhan 430075, China; 3. Unit 11 of the 32272 Troop of the Chinese People’s Liberation Army, Lanzhou 730060, China; 4. School of Computer Science and Technology, Xidian University, Xi’an 710071, China) Abstract: Equipment maintenance support plays an important role in advancing the smooth progress of operations. Reasonable and high-efficiency maintenance task scheduling is the main content of maintenance support. In this study, the resource classification, priority evaluation index, maintenance scheduling model and dynamic scheduling algorithm under resource constraints and maintenance support task scheduling are discussed firstly, then the scheduling process of equipment maintenance procedures is analyzed, and then the objective function, constraint conditions and solving algorithm of common scheduling problems are introduced. Finally, the open problems and future development directions of resource-constrained task scheduling are summarized. Keywords: maintenance support; multi-maintenance center; resource constraints; scheduling model; evaluation index; dynamic scheduling; preemption; process scheduling 当今信息化作战条件下，充分利用战场信息 资源、合理进行维修任务调度，影响着我军作战 胜利使命的完成。首先，战时维修时间有限，我 军需合理进行任务调度以快速恢复故障装备作战 能力；其次，装备的研制也需要合适的调度，以减 少费用[1-2] ；再次，战时维修任务时间紧迫，维修资 源有限，如何在最短的时间内合理安排各工序的 顺序，分配维修保障资源使得调度方案最优也是 至关重要的[3-4]。 1 资源约束的任务调度 资源约束的维修任务调度涉及任务的分配， 收稿日期：2021−09−02. 网络出版日期：2022−06−14. 基金项目：国家自然科学基金项目（61877067）；装备预研领域 基金项目（80904010301）. 通信作者：齐小刚. E-mail：xgqi@xidian.edu.cn. 第 17 卷第 4 期 智 能 系 统 学 报 Vol.17 No.4 2022 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2022
·662· 智能系统学报 第17卷 以解决由谁完成何种任务的指派问题。是装备保 杂、约束众多，且涉及循环往复的不断优化，详情 障实施的直观表现。装备保障任务调度流程复 如图1所示。 维修保障资源 维修作业时间 约束 计划外的维 影响维修保障 基于维修任务优 维修保障任务 新维修保障任务 修保障任务 任务实施计划 先级的调度模型 调度决策结果 实施计划 减小 反馈调节 图1装备维修任务调度基本流程及约束条件 Fig.1 Basic process and constraints of equipment maintenance task scheduling 11维修资源分类 级。综合考量中外军事经验，得以下结论：战时 维修资源分配需要分类资源以便实际管理与 装备作用大则先维修；故障装备易修复则先维 后续研究。《军用装备维修基本术语》将维修保 修；耗时少则先维修；可修性好则先维修。故维 障资源表述为“人力、设备、备件、花费、技术、信 修任务优先级评估指标如下： 息和工时的统一。维修资源分消耗性资源和 1)重要级别：根据作战功能大小得出； 复制性资源，如图2所示。 2)技术状态：采用技术状态系数评估： 装备维修保障资源分类 3)耗费工时：开始至完成维修的时间； 4)所需设备：根据所需设备数及获取难度划 分级别： 消耗性 复制性 5)所需技术：根据维修水平将所需技术划分； 6)可维修性：采用可维修性系数评估。 优先级评估流程如图3所示。 非 可 可复制资 装备重要度 维修保障任 耗性资 复制 务基本属性 资 源 装备 维 对作 修 的 维修 时 备品备件 人员工具 技术资料 设备 贡献 资源需 位 程度 置 图2装备维修保障资源分类图 输人 Fig.2 Classification chart of equipment maintenance sup- 维修保障任务优先级分配模型 port resources 输出 1)消耗性资源 主要包括维修设备、备件和技术材料等。 装备在作战体系中的优先级 2)非消耗性资源 图3任务优先级评估流程 指人力资源，如执行维修的技工和组织管理 Fig.3 Task priority assessment process 方案的人员。本文主要考虑技工。维修人力资源 1.3维修调度模型 须有专业技能，如液压、机械等。且维修人力资 维修调度方案的合理性影响着维修的时效 源根据工作时长、学历等，可分为初、中、高级工。 性，如缩短时间、增大效益等。陆军维修形式有 3)复制性资源 自修、伴随修理、巡回修理、定点修理、战区后方 常指信息资源。维修产生的数据即为信息。 修理等。野战时伴随、巡回、定点修理起至关重 1.2优先级评估 要的作用。 根据故障装备属性（如重要度，资源需求）及 近年来，部分学者对维修任务调度进行了研 维修资源的有限性，需要为维修任务制定优先 究。模型方面，文献[8]研究了双目标排流车间
以解决由谁完成何种任务的指派问题。是装备保 障实施的直观表现。装备保障任务调度流程复 杂、约束众多，且涉及循环往复的不断优化，详情 如图 1 所示。 维修保障资源 维修作业时间 基于维修任务优 先级的调度模型 维修保障任务 调度决策结果 影响维修保障 任务实施计划 计划外的维 修保障任务 新维修保障任务 实施计划 输入 输出 减小 反馈调节 约束 图 1 装备维修任务调度基本流程及约束条件 Fig. 1 Basic process and constraints of equipment maintenance task scheduling 1.1 维修资源分类 维修资源分配需要分类资源以便实际管理与 后续研究。《军用装备维修基本术语》将维修保 障资源表述为“人力、设备、备件、花费、技术、信 息和工时的统一” [4]。维修资源分消耗性资源和 复制性资源，如图 2 所示。 装备维修保障资源分类 消耗性 复制性 消 耗 性 资 源 非 消 耗 性 资 源 可 复 制 资 源 不 可 复 制 资 源 备品备件 人员工具 技术资料 设备 图 2 装备维修保障资源分类图 Fig. 2 Classification chart of equipment maintenance support resources 1) 消耗性资源 主要包括维修设备、备件和技术材料等。 2) 非消耗性资源 指人力资源，如执行维修的技工和组织管理 方案的人员。本文主要考虑技工。维修人力资源 须有专业技能，如液压、机械等。且维修人力资 源根据工作时长、学历等，可分为初、中、高级工。 3) 复制性资源 常指信息资源。维修产生的数据即为信息。 1.2 优先级评估 根据故障装备属性（如重要度，资源需求）及 维修资源的有限性，需要为维修任务制定优先 级。综合考量中外军事经验，得以下结论：战时 装备作用大则先维修；故障装备易修复则先维 修；耗时少则先维修；可修性好则先维修。故维 修任务优先级评估指标如下[5] ： 1) 重要级别：根据作战功能大小得出； 2) 技术状态：采用技术状态系数评估； 3) 耗费工时：开始至完成维修的时间； 4) 所需设备：根据所需设备数及获取难度划 分级别； 5) 所需技术：根据维修水平将所需技术划分； 6) 可维修性：采用可维修性系数评估。 优先级评估流程如图 3 所示。 维修保障任务优先级分配模型 装备在作战体系中的优先级 装备重要度 维修保障任 务基本属性 装备 对作 战的 贡献 程度 维 修 资 源 需 求 维 修 时 间 待 维 修 位 置 输出 输入 图 3 任务优先级评估流程 Fig. 3 Task priority assessment process 1.3 维修调度模型 维修调度方案的合理性影响着维修的时效 性，如缩短时间、增大效益等。陆军维修形式有 自修、伴随修理、巡回修理、定点修理、战区后方 修理等。野战时伴随、巡回、定点修理起至关重 要的作用[6]。 近年来，部分学者对维修任务调度进行了研 究 [7]。模型方面，文献 [8] 研究了双目标排流车间 ·662· 智 能 系 统 学 报 第 17 卷
第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 problem, 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) 维修任务独立，任务间互不影响。 在最短时间内形成维修保障工序调度方案， 可提升保障效能。维修时人员分配不当、维修调 度不周等影响任务完工时间，资源受限工序调度 诣在合理的安排工序调度以缩短工时、减少成 本，可转化为资源受限项目调度问题 (resourceconstrained project scheduling problem, RCPSP)。 装备维修工序调度流程如图 4 所示。常见调 度问题如下： 准备 资源请求 开始 维修排故 结束 资源需求 工序调度 资源分配 工序调度 资源池 维修保障过程 工序调度过程 图 4 装备维修工序调度流程 Fig. 4 Equipment maintenance process scheduling process 第 4 期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·663·
·664· 智能系统学报 第17卷 2.1 RCPSP与PRCPSP sip,dp∈No,ieN;p=1,2,…,P4l (12) 目前，RCPSP充分应用于各场景。此外，非 其中：式(6)为目标函数；式(7)表示时刻0开始 抢占式RCPSP]以及抢占式PRCPSP(preemptive 维修：式(8)为时序约束，工序的完成后工序j开 resource-constrained project scheduling problem, 始；式(9)表示子工序的优先关系，子活动结束 PRCPSP)P的应用取决于：该工序可否暂停，占用 后开始；式(I0)表示工序工时等于子工序工时 的资源被另一工序使用。研究表明，抢占可高度 之和；式(11)表示工序资源限制；式(12)表示子 利用资源，减少闲置情况，从而减小工时。文献 工序开始时刻和工时为非负整数；拆分工序的子 [33]对离散PRCPSP问题，在整数时刻对工序进 工序p开始时间sp,工序工期dp 行抢占，并分为一次抢占和多次抢占。 2.2其他调度问题 1)RCPSP 1)目标函数 一个任务由n个工序i=1,2,…,n组成，给定任 经典的RCPSP数学模型是以工期最短为目 务维修时间范围[O,T],K种资源中资源k拥有量 标，但实际维修保障中，单一指标难以评价方案 R,工序需资源k数量r,工序对资源的需求不大 优劣，决策者常需考虑多个指标并进行权衡。 于该资源总量。工序i维修时间d:。虚拟工序 对于维修资源受限式维修工序调度问题，需 i=0和i=n+1表示任务的开始和结束，不占用维 要考虑的目标有以下几个： 修时间和资源。工序开始时间s,完成时间c,则 ①最小化项目工期： 3:+d,=c。假设工序不允许抢占。采用图G(WE) min s 表示任务网络，工序集合为V={0,1,…,n+1,弧集 该式最小化最后虚拟活动的开始时间，等价 合为E={,,jeVi→，表示工序是的紧前工 于最小化项目工期s。 序。工序i紧前工序集合pre()={j,)∈E,工序 ②最小化项目拖期： i的后继活动集合suc()={(i,)∈E}。RCPSP主要 min∑B,max0,f-D,l 约束有时序和资源约束，最小化任务完成时间 C=C}为优化目标B。 该式最小化活动加权拖期之和，其中活动拖 RCPSP概念性模型为 期严重程度B,活动实际完成时间f,计划交付时 mins (1) 间D。该目标适于有时间限制调度问题7。 S.t ③资源均衡： :+d,≤s,(i,)∈E (2) 之≤R,k=1,,K,t=l,T (3) ∑∑c} k=1=0 S0=0 (4) 该式最小化资源使用量平方加权和。时刻 siE int",i=1,…,n (5) t需资源k数量a=∑k,时刻t正在执行活动集合 其中：式(1)为目标函数；：式(2)为工序时序约束； V,={sp≤t≤sp+dp。资源均衡可确保资源利用 式(3)为资源约束；式(4)说明从时刻0开始维 稳定，是项目调度的重要目标。 修；式（⑤）限制工序开始时间为非负整数。 ④最小化资源可用量成本： 2)PRCPSP K 6 若允许抢占发生在整数时间点，则为离散抢 minc=∑ Ck·a+z k=1=0 占；若允许抢占发生在任意时间点，则称为连续 其中，活动中断成本z。该目标函数增加了活动抢 抢占。 占成本B PRCPSP概念性模型为 2)约束条件 s.t. mins (6) 对于工序调度，资源是非常重要的约束条件。 501=0 (7) 装备维修保障资源分为可更新资源、消耗性资源 S≥5P,+dP,(i,)∈A (8) 以及双重资源。 sp*1≥Sp+dp,i∈N;p=1,2,…,P (9) 1)可更新资源在每个时刻的供应链是有限 P d=dp,ieNP=l,2…,d (10) 的，并不随维修保障的进度而消耗，例如人力、设 =1 备等。可更新资源约束表示： ≤1=12Tk=12K (11) ∑ra≤R,k=1,2,,K,1=1,…,T
2.1 RCPSP 与 PRCPSP 目前，RCPSP 充分应用于各场景。此外，非 抢占式 RCPSP[33] 以及抢占式 PRCPSP(preemptive resource-constrained project scheduling problem, PRCPSP)[28] 的应用取决于：该工序可否暂停，占用 的资源被另一工序使用。研究表明，抢占可高度 利用资源，减少闲置情况，从而减小工时。文献 [33] 对离散 PRCPSP 问题，在整数时刻对工序进 行抢占，并分为一次抢占和多次抢占。 1) RCPSP n i = 1,2,··· ,n [0,T] K k Rk i k riki di i = 0 i = n+1 i si ci si +di = ci G(V,E) V = {0,1,··· ,n+1} E = {(i, j)|i, j ∈ V,i → j} i j i pre(i) = {j|(j,i) ∈ E} i suc(i) = {j|(i, j) ∈ E} Cmax = max i∈V {Ci} 一个任务由 个工序 组成，给定任 务维修时间范围 ， 种资源中资源 拥有量 ，工序 需资源 数量 ，工序对资源的需求不大 于该资源总量。工序 维修时间 。虚拟工序 和 表示任务的开始和结束，不占用维 修时间和资源。工序 开始时间 ，完成时间 ，则 。假设工序不允许抢占。采用图 表示任务网络，工序集合为 ，弧集 合为 ，表示工序 是 的紧前工 序。工序 紧前工序集合 ，工序 的后继活动集合 。RCPSP 主要 约束有时序和资源约束，最小化任务完成时间 为优化目标[34]。 RCPSP 概念性模型为 minsn (1) s.t. si +di ⩽ sj , ∀(i, j) ∈ E (2) ∑ i∈A(t) rik ⩽ Rk , k = 1,··· ,K,t = 1,··· ,T (3) s0 = 0 (4) si ∈ int+ ,i = 1,··· ,n (5) 其中：式 (1) 为目标函数；式 (2) 为工序时序约束； 式 (3) 为资源约束；式 (4) 说明从时刻 0 开始维 修；式 (5) 限制工序开始时间为非负整数。 2) PRCPSP 若允许抢占发生在整数时间点，则为离散抢 占；若允许抢占发生在任意时间点，则称为连续 抢占。 PRCPSP 概念性模型为 minsn (6) s.t. s0,1 = 0 (7) sj,1 ⩾ si,Pi+1 +di,Pi+1 ,∀(i, j) ∈ A (8) si,p+1 ⩾ si,p +di,p,∀i ∈ N;p = 1,2,···,Pi (9) di = ∑Pi p=1 di,p ，∀i ∈ N;Pi = 1,2,··· ,d1 (10) ∑ i∈At rik ⩽ Rk ,t = 1,2,··· ,T; k = 1,2,··· ,K (11) si,p,di,p ∈ N0,∀i ∈ N;p = 1,2,···,Pi+1 (12) i j iip ip+1 i i p sip dip 其中：式 (6) 为目标函数；式 (7) 表示时刻 0 开始 维修；式 (8) 为时序约束，工序 的完成后工序 开 始；式 (9) 表示子工序的优先关系，子活动 结束 后 开始；式 (10) 表示工序 工时等于子工序工时 之和；式 (11) 表示工序资源限制；式 (12) 表示子 工序开始时刻和工时为非负整数；拆分工序 的子 工序 开始时间 ，工序工期 。 2.2 其他调度问题 1) 目标函数 经典的 RCPSP 数学模型是以工期最短为目 标，但实际维修保障中，单一指标难以评价方案 优劣，决策者常需考虑多个指标并进行权衡。 对于维修资源受限式维修工序调度问题，需 要考虑的目标有以下几个： ① 最小化项目工期： min sn 该式最小化最后虚拟活动的开始时间，等价 于最小化项目工期[35-36]。 ② 最小化项目拖期： min∑ i∈N βi max{0, fi − Di} i βi i fi Di 该式最小化活动加权拖期之和，其中活动 拖 期严重程度 ，活动 实际完成时间 ，计划交付时 间 。该目标适于有时间限制调度问题[37]。 ③ 资源均衡： min∑K k=1 ∑δ t=0 ck ·(ukt) 2 t k ukt = ∑ i∈Vt rik t Vt = {i|si,p ⩽ t ⩽ si,p +di,p} 该式最小化资源使用量平方加权和。时刻 需资源 数量 ，时刻 正在执行活动集合 。资源均衡可确保资源利用 稳定，是项目调度的重要目标[38]。 ④ 最小化资源可用量成本： minC = ∑K k=1 ∑δ t=0 ck · ukt +z 其中，活动中断成本 z 。该目标函数增加了活动抢 占成本[39]。 2) 约束条件 对于工序调度，资源是非常重要的约束条件。 装备维修保障资源分为可更新资源、消耗性资源 以及双重资源。 1) 可更新资源在每个时刻的供应链是有限 的，并不随维修保障的进度而消耗，例如人力、设 备等。可更新资源约束表示： ∑ i∈A(t) rik ⩽ Rk , k = 1,2,··· ,K,t = 1,··· ,T ·664· 智 能 系 统 学 报 第 17 卷
第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·
·666· 智能系统学报 第17卷 阶段局部搜索对项目时间随机的资源约束调度问 LU Yuanchao,ZHANG Huaiqiang,FEI Liang.A study 题求解。 on maintenance resource allocation of warship based on 综上，在装备维修工序调度算法设计时，应当 maximum maintenance benefit[J.Journal of Naval Uni- 考虑以下两方面的因素： versity of Engineering (comprehensive edition),2016. 在实际维修中，人员进行下一工序维修时需 13(3:78-81. 要切换时间，故可考虑带有惩罚时间的多次随机 [2]吕学志，于永利.面向任务的装备作战单元维修决策 抢占方案在实际调度中的应用。 [M.北京：国防工业出版社，2014 现有调度问题多以最小工期为单目标优化， [3]王涛.基于混合进化算法的军用车辆维修保障资源调 但实际需考虑人员多技能、胜任力差异等问题， 度优化研究D1.北京：北京理工大学，2013 单一目标难以符合实际调度。 WANG Tao.Research on maintenance resource schedul- ing optimization for military vehicles based on hybrid 3结束语 evolutionary algorithm[D].Beijing:Beijing Institute of Technology,2013. 现阶段的一体化作战信息系统，对取得优秀 [4]徐文强.通用航空维修保障资源分配方法及应用研究 的装备维修效果具有重要意义。需要根据瞬息万 [D1.广汉：中国民用航空飞行学院，2019 变的战场情况及时更新信息，动态调度任务。目 XU Wengiang.Research on general aviation mainten- 前任务调度研究存在以下问题： ance support resource allocation method and applica- 1)多数研究建立的是静态模型，或将动态模 tion[D].Guanghan:China Civil Aviation Flight College, 型转化为静态模型，但实际需动态的任务调度。 2019. 2)多数研究针对定点维修调度问题，野战维 [5]张柳，聂成龙，张伟.装备作战单元维修保障建模与仿 修调度研究较少。 真M.北京：国防工业出版社，2015. 3)对于维修任务的优先级确定也需要进一步 [6]高克，李敏.设备管理与维修M.北京：机械工业出版 结合战时具体情况进行分析。考虑的优化目标相 社，1987. 对单一。 [7]VOLKANOVSKI A.MAVKO B.BOSEVSKI T,et al. 4)对带有惩罚函数的抢占式维修工序调度问 Genetic algorithm optimisation of the maintenance 题没有很好地应用于军用装备维修保障系统内。 scheduling of generating units in a power system[J].Reli- 具体的研究方法和解决方案如下： ability engineering system safety,2008,93(6): 1)实现平时、战时不同条件下的装备维修任 779-789 务调度。 [8]BOUFELLOUH R,BELKAID F.Multi-objective ap- 2)单任务内部的工序调度问题需考虑备件、 proach to optimize production and maintenance schedul- 人员等因素，使其更加符合实际的调度问题。 ing in flow shop environment under non-renewable re- sources constraints[C]//2019 International Conference on 3)在抢占式的工序调度问题中，抢占的次数 Advanced Electrical Engineering.Algiers:IEEE,2019: 往往是固定的，可以将抢占次数设计为随机的， 1-6. 求解出最佳的抢占次数，使得抢占机制更加灵 [9] DENG Hanqiang,HUANG Jian,HAO Jianguo,et al.Re- 活，结果更加准确。 search on optimal scheduling of battlefield maintenance 4)目前所提出的任务调度算法有一定的局限 tasks considering residual life[C]//2018 3rd International 性，不仅要考虑动态的调度算法，还需要将多种 Conference on Mechanical,Control and Computer Engin- 算法有效结合起来，使优化效果更加明显。 eering.Huhhot:IEEE,2018:578-583 新时代情况下，我军装备维修调度研究急需 [10]GOLPIRA H.TIRKOLAEE E B.Stable maintenance 符合实际情况。需不断探索对新型装备和技术， tasks scheduling:a bi-objective robust optimization 且根据平时、战时等情况分类研究。以合理资源 model[J].Computers industrial engineering,2019, 分配、合理任务调度，提高保障效能。 137:106007. 参考文献： [11]MIRA L.ANDRADE A R,GOMES M C.Maintenance scheduling within rolling stock planning in railway oper- [1]卢远超，张怀强，费良.基于维修效益最大化的舰艇维 ations under uncertain maintenance durations[J].Journal 修资源配置研究[】.海军工程大学学报（综合版）， of rail transport planning management,2020,14: 2016,13(3):78-81. 100177
阶段局部搜索对项目时间随机的资源约束调度问 题求解。 综上，在装备维修工序调度算法设计时，应当 考虑以下两方面的因素： 在实际维修中，人员进行下一工序维修时需 要切换时间，故可考虑带有惩罚时间的多次随机 抢占方案在实际调度中的应用。 现有调度问题多以最小工期为单目标优化， 但实际需考虑人员多技能、胜任力差异等问题， 单一目标难以符合实际调度。 3 结束语 现阶段的一体化作战信息系统，对取得优秀 的装备维修效果具有重要意义。需要根据瞬息万 变的战场情况及时更新信息，动态调度任务。目 前任务调度研究存在以下问题： 1) 多数研究建立的是静态模型，或将动态模 型转化为静态模型，但实际需动态的任务调度。 2) 多数研究针对定点维修调度问题，野战维 修调度研究较少。 3) 对于维修任务的优先级确定也需要进一步 结合战时具体情况进行分析。考虑的优化目标相 对单一。 4) 对带有惩罚函数的抢占式维修工序调度问 题没有很好地应用于军用装备维修保障系统内。 具体的研究方法和解决方案如下： 1) 实现平时、战时不同条件下的装备维修任 务调度。 2) 单任务内部的工序调度问题需考虑备件、 人员等因素，使其更加符合实际的调度问题。 3) 在抢占式的工序调度问题中，抢占的次数 往往是固定的，可以将抢占次数设计为随机的， 求解出最佳的抢占次数，使得抢占机制更加灵 活，结果更加准确。 4) 目前所提出的任务调度算法有一定的局限 性，不仅要考虑动态的调度算法，还需要将多种 算法有效结合起来，使优化效果更加明显。 新时代情况下，我军装备维修调度研究急需 符合实际情况。需不断探索对新型装备和技术， 且根据平时、战时等情况分类研究。以合理资源 分配、合理任务调度，提高保障效能。 参考文献： 卢远超, 张怀强, 费良. 基于维修效益最大化的舰艇维 修资源配置研究 [J]. 海军工程大学学报 (综合版), 2016, 13(3): 78−81. [1] LU Yuanchao, ZHANG Huaiqiang, FEI Liang. A study on maintenance resource allocation of warship based on maximum maintenance benefit[J]. Journal of Naval University of Engineering (comprehensive edition) , 2016, 13(3): 78−81. 吕学志, 于永利. 面向任务的装备作战单元维修决策 [M]. 北京: 国防工业出版社, 2014. [2] 王涛. 基于混合进化算法的军用车辆维修保障资源调 度优化研究 [D]. 北京: 北京理工大学, 2013. WANG Tao. Research on maintenance resource scheduling optimization for military vehicles based on hybrid evolutionary algorithm[D]. Beijing: Beijing Institute of Technology, 2013. [3] 徐文强. 通用航空维修保障资源分配方法及应用研究 [D]. 广汉: 中国民用航空飞行学院, 2019. XU Wenqiang. Research on general aviation maintenance support resource allocation method and application[D]. Guanghan: China Civil Aviation Flight College, 2019. [4] 张柳, 聂成龙, 张伟. 装备作战单元维修保障建模与仿 真 [M]. 北京: 国防工业出版社, 2015. [5] 高克, 李 敏. 设备管理与维修 [M]. 北京: 机械工业出版 社, 1987. [6] VOLKANOVSKI A, MAVKO B, BOŠEVSKI T, et al. Genetic algorithm optimisation of the maintenance scheduling of generating units in a power system[J]. Reliability engineering & system safety, 2008, 93(6): 779–789. [7] BOUFELLOUH R, BELKAID F. Multi-objective approach to optimize production and maintenance scheduling in flow shop environment under non-renewable resources constraints[C]//2019 International Conference on Advanced Electrical Engineering. Algiers: IEEE, 2019: 1−6. [8] DENG Hanqiang, HUANG Jian, HAO Jianguo, et al. Research on optimal scheduling of battlefield maintenance tasks considering residual life[C]//2018 3rd International Conference on Mechanical, Control and Computer Engineering. Huhhot: IEEE, 2018: 578−583. [9] GOLPÎRA H, TIRKOLAEE E B. Stable maintenance tasks scheduling: a bi-objective robust optimization model[J]. Computers & industrial engineering, 2019, 137: 106007. [10] MIRA L, ANDRADE A R, GOMES M C. Maintenance scheduling within rolling stock planning in railway operations under uncertain maintenance durations[J]. Journal of rail transport planning & management, 2020, 14: 100177. [11] ·666· 智 能 系 统 学 报 第 17 卷
第4期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·667· [12]XU Yijing,HAN Xueshan,YANG Ming,et al.Condi- lem[J].European journal of operational research,2008. tion-based midterm maintenance scheduling with res- 191(3):650-660. cheduling strategy[J].International journal of electrical [21]BEAUDRY A,LAPORTE G,MELO T,et al.Dynamic power energy systems,2020,118:105796. transportation of patients in hospitals[J].OR spectrum. [13]沈延安，叶霖.基于可视化HPSO的无人机装备维修 2010,32(1:77-107 任务调度).火力与指挥控制，2019,44(1)6-11. [22]THOMAS B W.Waiting strategies for anticipating ser- SHEN Yanan,YE Lin.Visual HPSO in application of vice requests from known customer locations[J].Trans- the maintenance task scheduling of UAV equipment[J]. portation science,2007,41(3):319-331 Fire control command control,2019,44(1):6-11. [23]LI Jingquan,MIRCHANDANI P B,BORENSTEIN D. [14]ZHANG Yongxiang,D'ARIANO A,HE Bisheng,et al. Real-time vehicle rerouting problems with time win- Microscopic optimization model and algorithm for integ- dows[J.European journal of operational research,2009, rating train timetabling and track maintenance task 194(3):711-727. scheduling[J].Transportation research part B:methodo- [24]张景玲，赵燕伟，王海燕，等.多车型动态需求车辆路 1 ogical,.2019.127:237-278. 径问题建模及优化[】.计算机集成制造系统，2010 [15]王雄伟，陈春良，曹艳华，等.基于改进TOPSIS法的装 16(3):543-550 备维修任务优先级确定方法).计算机测量与控制， ZHANG Jingling,ZHAO Yanwei,WANG Haiyan,et al. 2018,26(4):108-111,142 Modeling and algorithms for a dynamic multi-vehicle WANG Xiongwei,CHEN Chunliang,CAO Yanhua,et routing problem with customers'dynamic requests[J]. al.Priority determination method of armored equipment Computer integrated manufacturing systems,2010. maintenance task based on improved TOPSIS method[J]. 16(3):543-550. Computer measurement control,2018,26(4): [25] 陈立云，刘爱珍.战时维修保障力量的优化调度方法 108-111,142 研究[U.军事运筹与系统工程，2014,28(3)：43-47,52 [I6]刘彦，陈春良，陈伟龙，等.基于Pareto改进VNS CHEN Liyun,LIU Aizhen.Research on optimal MMAS的定点修理任务多目标动态调度].系统工 scheduling method of wartime maintenance support 程与电子技术，2020.42(2)：356-364. forces[J.Military operations research and systems en- LIU Yan,CHEN Chunliang,CHEN Weilong,et al. gineering.2014,28(3):43-47,52. Multi-objective dynamic scheduling of fixed-point re- [26]刁鸣，邹丽.模拟退火遗传禁忌搜索的多用户检测算 pairing tasks based on Pareto improved VNS-MMAS[J]. 法.哈尔滨工程大学学报，2014,35(3)：373-377 Systems engineering and electronics,2020,42(2): DIAO Ming,ZOU Li.Multi-user detection based on the 356-364 simulated annealing genetic tabu search[J].Journal of [17]YANG Jianyi,DING Ruifeng,ZHANG Yuan,et al.An Harbin Engineering University,2014,35(3):373-377. improved ant colony optimization (I-ACO)method for [27]陆汉东，何卫平，周旭，等.基于禁忌搜索的柔性作业 the quasi travelling salesman problem(Quasi-TSP)[J]. 车间分批调度[J].上海交通大学学报，2012,46(12)： International journal of geographical information sci- 2003-2008. ence,2015,299y1534-1551. LU Handong,HE Weiping,ZHOU Xu,et al.An integ- [18]DONG Ruyi,WANG Shengsheng,WANG Guangyao, rated tabu search algorithm for the lot streaming prob- et al.Hybrid optimization algorithm based on wolf pack lem in flexible job shops[J].Journal of Shanghai Jiao- search and local search for solving traveling salesman tong University,2012,46(12):2003-2008. problem[J.Journal of Shanghai Jiao tong university [28]刘明，张培勇.求解多旅行商问题的新混合遗传算法： (science edition),2019,24(1):41-47. 以应急物资配送为例】.系统管理学报，2014,23(2)： [19]吕学志，王宪文，范保新，等.定点修理中维修任务调 247-254 度策略的仿真评估刀.火力与指挥控制，2015,40(1)： LIU Ming,ZHANG Peiyong.New hybrid genetic al- 70-76. gorithm for solving the multiple traveling salesman LYU Xuezhi,WANG Xianwen,FAN Baoxin,et al. problem:an example of distribution of emergence mater- Simulation-based evaluation of maintenance task ials[J].Journal of systems management,2014,23(2) scheduling strategies in fixed point repairing[J].Fire 247-254. control command control,2015,40(1):70-76. [29]谢丽霞，王亚超，于巾博.基于神经网络的网络安全态 [20]GOEL A,GRUHN V.A general vehicle routing prob- 势感知.清华大学学报（自然科学版），2013,5312)：
XU Yijing, HAN Xueshan, YANG Ming, et al. Condition-based midterm maintenance scheduling with rescheduling strategy[J]. International journal of electrical power & energy systems, 2020, 118: 105796. [12] 沈延安, 叶霖. 基于可视化 HPSO 的无人机装备维修 任务调度 [J]. 火力与指挥控制, 2019, 44(1): 6−11. SHEN Yanan, YE Lin. Visual HPSO in application of the maintenance task scheduling of UAV equipment[J]. Fire control & command control, 2019, 44(1): 6−11. [13] ZHANG Yongxiang, D’ARIANO A, HE Bisheng, et al. Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling[J]. Transportation research part B:methodological, 2019, 127: 237–278. [14] 王雄伟, 陈春良, 曹艳华, 等. 基于改进 TOPSIS 法的装 备维修任务优先级确定方法 [J]. 计算机测量与控制, 2018, 26(4): 108−111, 142. WANG Xiongwei, CHEN Chunliang, CAO Yanhua, et al. Priority determination method of armored equipment maintenance task based on improved TOPSIS method[J]. Computer measurement & control, 2018, 26(4): 108−111, 142. [15] 刘彦, 陈春良, 陈伟龙, 等. 基于 Pareto 改进 VNSMMAS 的定点修理任务多目标动态调度 [J]. 系统工 程与电子技术, 2020, 42(2): 356−364. LIU Yan, CHEN Chunliang, CHEN Weilong, et al. Multi-objective dynamic scheduling of fixed-point repairing tasks based on Pareto improved VNS-MMAS[J]. Systems engineering and electronics, 2020, 42(2): 356−364. [16] YANG Jianyi, DING Ruifeng, ZHANG Yuan, et al. An improved ant colony optimization (I-ACO) method for the quasi travelling salesman problem (Quasi-TSP)[J]. International journal of geographical information science, 2015, 29(9): 1534–1551. [17] DONG Ruyi, WANG Shengsheng, WANG Guangyao, et al. Hybrid optimization algorithm based on wolf pack search and local search for solving traveling salesman problem[J]. Journal of Shanghai Jiao tong university (science edition), 2019, 24(1): 41−47. [18] 吕学志, 王宪文, 范保新, 等. 定点修理中维修任务调 度策略的仿真评估 [J]. 火力与指挥控制, 2015, 40(1): 70−76. LYU Xuezhi, WANG Xianwen, FAN Baoxin, et al. Simulation-based evaluation of maintenance task scheduling strategies in fixed point repairing[J]. Fire control & command control, 2015, 40(1): 70−76. [19] [20] GOEL A, GRUHN V. A general vehicle routing problem[J]. European journal of operational research, 2008, 191(3): 650–660. BEAUDRY A, LAPORTE G, MELO T, et al. Dynamic transportation of patients in hospitals[J]. OR spectrum, 2010, 32(1): 77–107. [21] THOMAS B W. Waiting strategies for anticipating service requests from known customer locations[J]. Transportation science, 2007, 41(3): 319–331. [22] LI Jingquan, MIRCHANDANI P B, BORENSTEIN D. Real-time vehicle rerouting problems with time windows[J]. European journal of operational research, 2009, 194(3): 711–727. [23] 张景玲, 赵燕伟, 王海燕, 等. 多车型动态需求车辆路 径问题建模及优化 [J]. 计算机集成制造系统, 2010, 16(3): 543−550. ZHANG Jingling, ZHAO Yanwei, WANG Haiyan, et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with customers’ dynamic requests[J]. Computer integrated manufacturing systems, 2010, 16(3): 543−550. [24] 陈立云, 刘爱珍. 战时维修保障力量的优化调度方法 研究 [J]. 军事运筹与系统工程, 2014, 28(3): 43−47, 52. CHEN Liyun, LIU Aizhen. Research on optimal scheduling method of wartime maintenance support forces[J]. Military operations research and systems engineering, 2014, 28(3): 43−47, 52. [25] 刁鸣, 邹丽. 模拟退火遗传禁忌搜索的多用户检测算 法 [J]. 哈尔滨工程大学学报, 2014, 35(3): 373−377. DIAO Ming, ZOU Li. Multi-user detection based on the simulated annealing genetic tabu search[J]. Journal of Harbin Engineering University, 2014, 35(3): 373−377. [26] 陆汉东, 何卫平, 周旭, 等. 基于禁忌搜索的柔性作业 车间分批调度 [J]. 上海交通大学学报, 2012, 46(12): 2003−2008. LU Handong, HE Weiping, ZHOU Xu, et al. An integrated tabu search algorithm for the lot streaming problem in flexible job shops[J]. Journal of Shanghai Jiaotong University, 2012, 46(12): 2003−2008. [27] 刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例 [J]. 系统管理学报, 2014, 23(2): 247−254. LIU Ming, ZHANG Peiyong. New hybrid genetic algorithm for solving the multiple traveling salesman problem: an example of distribution of emergence materials[J]. Journal of systems & management, 2014, 23(2): 247−254. [28] 谢丽霞, 王亚超, 于巾博. 基于神经网络的网络安全态 势感知 [J]. 清华大学学报 (自然科学版), 2013, 53(12): [29] 第 4 期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·667·
·668· 智能系统学报 第17卷 1750-1760 date setting,resource assignment,and job preemption XIE Lixia,WANG Yachao,YU Jinbo.Network secur- heuristics for the multiproject scheduling problem[J]. ity situation awareness based on neural networks[J]. Decision sciences,1990,21(2):387-402. Journal of Tsinghua university (science and technology [38]李洪波，熊励，刘寅斌.项目资源均衡研究综述.控 edition,2013,53(12:1750-1760. 制与决策，2015,30(5：769-779. [30]徐敏，陈全，张锦文，等.基于规则推理的继电保护动 LI Hongbo,XIONG Li,LIU Yinbin.A literature survey 作行为评价的新方法研究几.郑州大学学报（工学 of project resource leveling[J].Control and decision, 版)，2014.351)：116-119. 2015,30(5):769-779. XU Min,CHEN Quan,ZHANG Jinwen,et al.Research [39]HARIGA M,EL-SAYEGH S M.Cost optimization on a new method of relay protection action evaluation model for the multiresource leveling problem with al- based on rule based reasoning[].Journal of Zhengzhou lowed activity splitting[J].Journal of construction engin- University (engineering science edition),2014,35(1): eering and management,2011,137(1):56-64. 116-119 [40] BALLESTIN F,VALLS V,QUINTANILLA S. [31]文仁强，陈建国，袁宏永，等.基于蚁群优化算法的多 Scheduling projects with limited number of preemp- 级应急响应下灾后应急资源空间优化配置).清华大 tions[J].Computers operations research,2009,36(11): 学学报（自然科学版），2012,52(11)少：1591-1596 2913-2925. WEN Rengiang,CHEN Jianguo,YUAN Hongyong,et [41]ZHU Jie,LI Xiaoping,SHEN Weiming.Effective genet- al.Post-disaster emergency resource location and alloca- ic algorithm for resource-constrained project scheduling tion based on the ant colony optimal algorithm for multi- with limited preemptions[J].International journal of ma- level emergency responses[J].Journal of Tsinghua Uni- chine learning and cybernetics,2011,2(2):55-65. versity (science and technology edition),2012,52(11):1591- [42]CHENG Runwei,GEN M.Resource constrained project 1596. scheduling problem using genetic algorithms[J].Intelli- [32]刘衍民.一种求解约束优化问题的混合粒子群算法 gent automation&soft computing,1997,3(3):273-286. [J].清华大学学报（自然科学版），2013,53(2)： [43]KELLEY J E.The critical-path method:resources plan- 242-246. ning and scheduling[J].Industrial scheduling,1963, LIU Yanmin.Hybrid particle swarm optimizer for con- 347-365 strained optimization problems[J].Journal of Tsinghua [44]段鹏飞，余杰，聂慧，等.求解广义优先关系下多技能 University (science and technology edition),2013, 人员项目调度问题的改进布谷鸟搜索算法)计算机 53(2:242-246. 应用研究，2018,35(5)：1315-1319. [33]BALLESTIN F.VALLS V.OUINTANILLA S.Pre- DUAN Pengfei,YU Jie,NIE Hui,et al.Improved emption in resource-constrained project scheduling[J]. cuckoo search algorithm for multi-skilled resource con- European journal of operational research,2008,189(3): strained project scheduling problems with generalized 1136-1152. precedence relations[J].Application research of com- [34]寿涌毅.资源受限多项目调度的模型与方法[M.杭 puters,2018,35(5):1315-1319. 州：浙江大学出版社，2010 [45]LI Zhangtao,YUAN Xiaoxiao,TANG Xianglong,et al. [35]DEMEULEMEESTER E L.HERROELEN W S.An ef- A moving block sequence-based evolutionary algorithm ficient optimal solution procedure for the preemptive re- for resource-constrained project scheduling problems[J] source-constrained project scheduling problem[J]. International journal of bio-inspired computation,2019. European journal of operational research,1996,90(2): 142:85. 334-348. [46]MA Zhiqiang,HE Zhengwen,WANG Nengmin,et al.A [36]丁雪枫，尤建新.多模式资源受限项目调度问题的混 genetic algorithm for the proactive resource-constrained 合优化算法研究[J.中国管理科学，2012,20(S1): project scheduling problem with activity splitting[J]. 154-159. IEEE transactions on engineering management,2019, DING Xuefeng,YOU Jianxin.Studies on A hybrid op- 66(3):459-474 timal algorithm for multi-mode resource-constrained [47]DAI Huafeng,CHENG Wenming,GUO Peng.An im- project scheduling problem[J].Chinese journal of man- proved tabu search for multi-skill resource-constrained agement science,2012,20(S1):154-159. project scheduling problems under step-deterioration[J]. [37]BOCK D B,PATTERSON J H.A comparison of due Arabian journal for science and engineering,2018
1750−1760. XIE Lixia, WANG Yachao, YU Jinbo. Network security situation awareness based on neural networks[J]. Journal of Tsinghua university (science and technology edition), 2013, 53(12): 1750−1760. 徐敏, 陈全, 张锦文, 等. 基于规则推理的继电保护动 作行为评价的新方法研究 [J]. 郑州大学学报 (工学 版), 2014, 35(1): 116−119. XU Min, CHEN Quan, ZHANG Jinwen, et al. Research on a new method of relay protection action evaluation based on rule based reasoning[J]. Journal of Zhengzhou University (engineering science edition), 2014, 35(1): 116−119. [30] 文仁强, 陈建国, 袁宏永, 等. 基于蚁群优化算法的多 级应急响应下灾后应急资源空间优化配置 [J]. 清华大 学学报 (自然科学版), 2012, 52(11): 1591−1596. WEN Renqiang, CHEN Jianguo, YUAN Hongyong, et al. Post-disaster emergency resource location and allocation based on the ant colony optimal algorithm for multilevel emergency responses[J]. Journal of Tsinghua University (science and technology edition), 2012, 52(11): 1591− 1596. [31] 刘衍民. 一种求解约束优化问题的混合粒子群算法 [J]. 清华大学学报 (自然科学版), 2013, 53(2): 242−246. LIU Yanmin. Hybrid particle swarm optimizer for constrained optimization problems[J]. Journal of Tsinghua University (science and technology edition), 2013, 53(2): 242−246. [32] BALLESTÍN F, VALLS V, QUINTANILLA S. Preemption in resource-constrained project scheduling[J]. European journal of operational research, 2008, 189(3): 1136–1152. [33] 寿涌毅. 资源受限多项目调度的模型与方法 [M]. 杭 州: 浙江大学出版社, 2010. [34] DEMEULEMEESTER E L, HERROELEN W S. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem[J]. European journal of operational research, 1996, 90(2): 334–348. [35] 丁雪枫, 尤建新. 多模式资源受限项目调度问题的混 合优化算法研究 [J]. 中国管理科学, 2012, 20(S1): 154−159. DING Xuefeng, YOU Jianxin. Studies on A hybrid optimal algorithm for multi-mode resource-constrained project scheduling problem[J]. Chinese journal of management science, 2012, 20(S1): 154−159. [36] [37] BOCK D B, PATTERSON J H. A comparison of due date setting, resource assignment, and job preemption heuristics for the multiproject scheduling problem[J]. Decision sciences, 1990, 21(2): 387–402. 李洪波, 熊励, 刘寅斌. 项目资源均衡研究综述 [J]. 控 制与决策, 2015, 30(5): 769−779. LI Hongbo, XIONG Li, LIU Yinbin. A literature survey of project resource leveling[J]. Control and decision, 2015, 30(5): 769−779. [38] HARIGA M, EL-SAYEGH S M. Cost optimization model for the multiresource leveling problem with allowed activity splitting[J]. Journal of construction engineering and management, 2011, 137(1): 56–64. [39] BALLESTÍN F, VALLS V, QUINTANILLA S. Scheduling projects with limited number of preemptions[J]. Computers & operations research, 2009, 36(11): 2913–2925. [40] ZHU Jie, LI Xiaoping, SHEN Weiming. Effective genetic algorithm for resource-constrained project scheduling with limited preemptions[J]. International journal of machine learning and cybernetics, 2011, 2(2): 55–65. [41] CHENG Runwei, GEN M. Resource constrained project scheduling problem using genetic algorithms[J]. Intelligent automation & soft computing, 1997, 3(3): 273–286. [42] KELLEY J E. The critical-path method: resources planning and scheduling[J]. Industrial scheduling, 1963, 347−365. [43] 段鹏飞, 余杰, 聂慧, 等. 求解广义优先关系下多技能 人员项目调度问题的改进布谷鸟搜索算法 [J]. 计算机 应用研究, 2018, 35(5): 1315−1319. DUAN Pengfei, YU Jie, NIE Hui, et al. Improved cuckoo search algorithm for multi-skilled resource constrained project scheduling problems with generalized precedence relations[J]. Application research of computers, 2018, 35(5): 1315−1319. [44] LI Zhangtao, YUAN Xiaoxiao, TANG Xianglong, et al. A moving block sequence-based evolutionary algorithm for resource-constrained project scheduling problems[J]. International journal of bio-inspired computation, 2019, 14(2): 85. [45] MA Zhiqiang, HE Zhengwen, WANG Nengmin, et al. A genetic algorithm for the proactive resource-constrained project scheduling problem with activity splitting[J]. IEEE transactions on engineering management, 2019, 66(3): 459–474. [46] DAI Huafeng, CHENG Wenming, GUO Peng. An improved tabu search for multi-skill resource-constrained project scheduling problems under step-deterioration[J]. Arabian journal for science and engineering, 2018, [47] ·668· 智 能 系 统 学 报 第 17 卷
第4期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·669· 43(6):3279-3290 作者简介： [48]BERTHAUT F,PELLERIN R,HAJJI A,et al.A path 齐小刚.教授博士生导师.博士 relinking-based scatter search for the resource-con- 主要研究方向为复杂系统建模与数据 strained project scheduling problem[J].International 处理、联合资源分配与系统仿真。主 journal of project organisation and management,2018. 持完成国家自然科学基金项目、十三 101):1. 五预研项目、装备预研基金（重点项 [49]MAGHSOUDLOU H.AFSHAR-NADJAFI B.NIAKI S 目)、省自然科学基金重点项目等30 余项。申请专利80余件（授权41件）. T A.Preemptive multi-skilled resource constrained 登记软件著作权8件。获得军队和省部级科技进步二等奖 project scheduling problem with hard/soft interval due 1项、三等奖2项，省级教学成果奖一等奖2项。发表学术 dates[J].RAIRO-operations research,2019,53(5): 论文150余篇。 1877-1898. [50]陈俊杰，同淑荣，叶正梗，等.资源受限多项日调度问 陈玲琳，硕士研究生，主要研究方 题的两阶段算法[J].控制与决策，2020,35(8)： 向为保障大数据。参与和主持科研、 2013-2020. 装备维修改革等多项课题。 CHEN Junjie,TONG Shurong,YE Zhenggeng,et al. Two-stage algorithm for resource-constrained multi- project scheduling problem[J].Control and decision, 2020,35(8:2013-2020 [51]NABER A.Resource-constrained project scheduling 宋卫星，工程师，博土，主要研究 方向为装备维修保障优化和智能算法 with flexible resource profiles in continuous time[J]. 设计应用。主持和参与科研项目近 Computers operations research,2017,84:33-45. 10项，获军队科技进步三等奖3项。 [52]ROSTAMI S,CREEMERS S,LEUS R.New strategies 发表学术论文12篇。 for stochastic resource-constrained project scheduling[J]. Journal of scheduling,2018,21(3):349-365
43(6): 3279–3290. BERTHAUT F, PELLERIN R, HAJJI A, et al. A path relinking-based scatter search for the resource-constrained project scheduling problem[J]. International journal of project organisation and management, 2018, 10(1): 1. [48] MAGHSOUDLOU H, AFSHAR-NADJAFI B, NIAKI S T A. Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates[J]. RAIRO - operations research, 2019, 53(5): 1877–1898. [49] 陈俊杰, 同淑荣, 叶正梗, 等. 资源受限多项目调度问 题的两阶段算法 [J]. 控制与决策, 2020, 35(8): 2013−2020. CHEN Junjie, TONG Shurong, YE Zhenggeng, et al. Two-stage algorithm for resource-constrained multiproject scheduling problem[J]. Control and decision, 2020, 35(8): 2013−2020. [50] NABER A. Resource-constrained project scheduling with flexible resource profiles in continuous time[J]. Computers & operations research, 2017, 84: 33–45. [51] ROSTAMI S, CREEMERS S, LEUS R. New strategies for stochastic resource-constrained project scheduling[J]. Journal of scheduling, 2018, 21(3): 349–365. [52] 作者简介： 齐小刚，教授，博士生导师，博士， 主要研究方向为复杂系统建模与数据 处理、联合资源分配与系统仿真。主 持完成国家自然科学基金项目、十三 五预研项目、装备预研基金（重点项 目）、省自然科学基金重点项目等 30 余项。申请专利 80 余件（授权 41 件）， 登记软件著作权 8 件。获得军队和省部级科技进步二等奖 1 项、三等奖 2 项，省级教学成果奖一等奖 2 项。发表学术 论文 150 余篇。 陈玲琳，硕士研究生，主要研究方 向为保障大数据。参与和主持科研、 装备维修改革等多项课题。 宋卫星，工程师，博士，主要研究 方向为装备维修保障优化和智能算法 设计应用。主持和参与科研项目近 10 项，获军队科技进步三等奖 3 项。 发表学术论文 12 篇。 第 4 期 齐小刚，等：面向多维修中心的资源受限任务调度问题研究 ·669·
