正在加载图片...
第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·
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有