装备维修任务调度研究综述

陈春良， 刘 彦， 王生凤， 陈伟龙， 昝 翔

(1. 陆军装甲兵学院装备保障与再制造系， 北京100072； 2. 陆军装甲兵学院教研保障中心， 北京100072)

信息化条件下的现代战争突发性强、地域广阔，作战节奏越来越快，作战进程不断缩短，对战时装备维修的时效性提出了更高的要求。如何在有限的维修时间、维修资源和维修能力约束下合理高效地安排维修任务，使待修装备尽快地修复并归建作战部队，已成为制约战时装备维修保障效果的重要因素。装备维修任务调度是战场抢救修理的研究重点和热点，其通过合理分配维修资源、科学规划维修任务顺序优化调度目标，进而提高维修效率，对战场抢救修理具有重要的理论意义和应用价值。笔者从调度理论、调度策略、调度模型及调度算法等方面对装备维修任务调度研究进行综述，以期为战时合理高效地开展装备维修工作提供理论与方法支撑。

1 装备维修任务调度理论

调度是指在适当的时刻运用适当的方法为适当的用户分配适当的资源，使系统高效地运行，以达到特定的目的。调度问题(Scheduling Problem)根据调度对象的不同可分为任务调度和作业调度。作业是指为完成生产或调度任务而执行的基本活动，任务是指一组共同提供相关功能的作业组合[1]。简言之，任务是由一系列作业组成，是一系列作业的统称，如：装备维修任务可分为行动部分修理、火力部分修理以及通信部分修理等修理作业。本文中，具体的修理作业是维修任务的细化，因此将修理作业的调度归为维修任务调度。

调度问题自提出以来就迅速得到了广泛运用和深入研究，解决了许多工程实际问题，如车间调度、列车调度和物流配送等，显著提高了生产效率，并节约了生产成本。调度问题在军事领域也得到了广泛运用，如无人机任务调度[2]、卫星侦察调度[3]和备件供应[4]等。随着组合优化思想在工程实践中的不断应用，调度问题在军事领域的研究也逐步得到重视。本文中，装备维修任务调度是指在战时装备维修保障过程中，根据现有的保障资源、维修任务需求以及战场态势合理地调度维修任务，实现维修任务优化调度的目的。

1.1 维修任务调度分类

1.1.1 抢占调度与非抢占调度

根据任务执行过程中是否允许任务中断，可将调度问题分为抢占调度与非抢占调度。抢占调度[5-6]是指在任务执行过程中，当前执行的任务可被更加重要或紧迫的任务中断，相应的资源被抢占，当抢占任务完成后继续执行被抢占任务。非抢占调度[7]是指在任务执行过程中，当任务开始执行后就不能被中断，无论其他任务有多重要或紧急，都必须等待当前执行的任务完成，资源释放后方可执行。

抢占调度的优点是调度灵活，能够较好地处理突发任务，但容易导致资源待机时间长，特别是对资源需要转场的任务，容易导致资源待机时间更长，不利于全局调度任务的最优化。与抢占调度比较，非抢占调度的优点是避免了任务转换的时间消耗，但调度不够灵活，缺乏对突发任务的考虑。

LEVI等[8]以最小化维修费用为目标，针对空军飞机模块化系统的维修任务调度问题，提出了非抢占调度模型及算法，实现了飞机模块化系统的维修任务合理化调度。姚双印等[9]将军械装备的维修任务调度问题转化为非抢占式调度车间任务调度问题，并引入细菌觅食优化算法(Bacteria Foraging Optimization Algorithm, BFOA)进行模型求解。崔嘉等[10]考虑了航空定检修理工作涉及多车间、多工种和多工序的问题，对BFOA进行了改进，提高了算法的全局寻优能力，对非抢占式维修任务工序进行了调度优化。

对于装备维修任务调度问题，目前国内外的研究大多数是将其视为非抢占调度，认为装备维修任务在执行过程中不能中断，但由于战时任务的突发性和紧急性，装备维修任务抢占调度更符合实际情况，也更具有研究意义，但目前对装备维修任务抢占调度问题仍缺乏深入的研究。

1.1.2 静态调度与动态调度

根据任务分配方式可将调度问题分为静态调度[11]和动态调度[12]。静态调度是指在任务调度时，所有任务队列中的任务执行顺序是确定的，不会随着任务需求或资源约束等外部条件的变化而变化。动态调度是指在任务执行过程中需根据任务需求及相关约束确定下一个任务的执行顺序，即在任务队列中不断地动态调整任务的执行顺序[13]。

静态调度的优点是可预测性强,调度过程简单，适用于任务需求确定的调度问题，但调度的灵活性相对较差，难以解决任务需求、任务执行过程以及调度过程中的不确定性问题，因此难以实现全局最优。动态调度较为灵活，能够根据不断出现的任务需求和不断变化的资源约束实时地调整调度任务的执行顺序，在工程实践中得到了广泛运用。

在静态装备维修任务调度中，可将每次维修任务执行前的决策看作任务分配，进而抽象为指派问题进行建模与求解。由于装备维修任务需求的动态性，目前装备维修任务调度的研究多以动态调度为主，但涉及的约束条件较为简单和理想化，有待根据战场情况合理抽象约束条件，对维修任务调度模型进行深入研究。

1.2 维修任务调度策略

维修任务调度策略是维修任务调度的关键，常见的维修任务调度策略包括时钟驱动调度策略[14]、优先级调度策略以及其他维修调度策略。

1) 时钟驱动调度策略与优先级调度策略

时钟驱动调度策略是指在维修任务开始执行后选择一个固定的时刻，当到达该时刻时对维修任务重新调度，并决定任务的执行顺序。优先级调度策略是指在调度前对每个维修任务赋予一个优先级，当需要对多个维修任务分配维修力量时，则根据维修任务的优先级高低执行任务，优先执行优先级高的任务。

优先级调度策略是事件驱动，而时钟驱动调度策略是时钟驱动，二者之间有本质区别。对于维修任务调度，时钟驱动调度策略易导致当前维修任务还未完成而时钟驱动触发，维修力量中断当前任务转而执行其他任务，这一方面与战时装备维修实际不符，另一方面也增加了维修力量的转场时间。相对而言，优先级调度策略在维修任务调度中运用更为广泛，并逐渐演化出固定优先级调度[15-16]和动态优先级调度[17-18]。

由战时装备维修任务及其维修任务调度的特点可知：战时装备维修任务调度采取优先级调度策略，或者以优先级调度策略为主进行调度更符合战场实际，而任务优先级的确定是进行优先级调度的基础。维修任务优先级反映了各维修任务的相对重要程度，其决定因素包括装备类型、装备损伤程度、装备对战斗的重要程度以及待修装备与维修力量之间的距离等。求解维修任务优先级的实质是对维修任务的重要程度进行排序，属于典型的多属性决策问题[19]。

2) 其他维修调度策略

其他维修调度策略主要有故障驱动策略、维修力量驱动策略和维修资源需求策略。其中：故障驱动策略包括先到先服务(First Come First Sever, FCFS)策略[20]、后到先服务(Last Come First Sever, LCFS)策略[21]、最短平均处理时间(Shortest Mean Process Time, SMPT)策略[22]、最长平均处理时间(Longest Mean Process Time, LMPT)策略[23]、预测最早完工时间(Estimated Earliest Time To Complete, EETTC)策略[24]、预测最迟完工时间(Estimated Latest Time To Complete, ELTTC)策略[24]和改进优先级联合策略[25]；维修力量驱动策略包括最近修理(Nearest Dispatch, ND)策略[26]和预测性修理(Anticipatory Dispatch, AD)策略[27]；维修资源需求策略包括最小累积资源需求(MINimum Cumulated Resource Demand，MINCRD)策略[28]、最大累积资源需求(MAXimum Cumulated Resource Demand，MAXCRD)策略[28]、先到先服务与最小累积资源需求混合(FCFS & MINCRD)策略[29]、后到先服务与最大累积资源需求混合(LCFS & MAXCRD)策略[29]。

总体来看，在装备维修任务调度策略中，优先级调度策略的应用最为广泛，多种调度策略的综合运用是装备维修任务调度策略的发展趋势。在明确装备维修任务调度分类及调度策略的基础上，如何构建和构造装备维修任务调度模型及算法是求解装备维修任务调度问题的关键。

2 装备维修任务调度模型研究现状

维修任务调度问题是调度问题在军事学领域的延伸。从装备维修保障的角度来看，若将修理组看作旅行商问题的旅行商，则维修任务调度问题可抽象为旅行商问题；若将修理组看作车辆路径问题的车辆，则维修任务调度问题可抽象为车辆路径问题；若将维修任务看作项目调度的项目，则维修任务调度问题可抽象为项目调度问题；若考虑维修任务中的各项修理作业，则维修任务调度问题可抽象为车间调度问题。因此，笔者重点对上述4种典型调度模型及其算法进行综述。

2.1 旅行商问题

旅行商问题(Traveling Salesman Problem, TSP)[30]又称为货郎担问题，最早可追溯到18世纪，是组合优化领域中的一个经典难题，被证明是NP-Hard (Non-deterministic Polynomial-Hard)问题。TSP可简单地描述为1个旅行商人要拜访N个城市，从初始城市出发，每个城市都必须拜访且只能拜访1次，最终回到起点，如何选择拜访路径使总路径最短[31]。

在传统TSP中，假设城市数量、距离固定不变的条件过于理想化，不能满足现实问题的研究需求。国内外学者对TSP进行了深入研究，使TSP逐渐演化出许多更符合实际的复杂TSP，最典型的包括以下3类：

1) 动态旅行商问题(Dynamic Traveling Salesman Problem, DTSP)。DTSP是根据传统TSP中城市数量及距离动态变化而演化出来的，可描述为TSP中城市之间的交通路线权重(距离)随时间等因素动态变化，且在调度过程中会有新城市加入[32]。DTSP问题大大增加了模型的复杂性，但更贴近实际，可用来描述货物配送、快递员取件等问题。

2) 多目标旅行商问题(Multi-Objective Traveling Salesman Problem, MOTSP)。MOTSP是传统TSP的扩展，其目标不仅包括TSP总距离最短，也包括时间最短、费用最小、风险最低、增加客户满意度等多种目标。MOTSP的求解方法一般包括2种：一是通过目标转换、决策偏好加权等方法将多目标问题转化为单目标问题进行求解[33]；二是求解多目标的Pareto优化解集[34]。

3) 多人旅行商问题(Multi-Person Traveling Salesman Problem, MPTSP)。MPTSP将TSP中单个旅行商扩展为多个旅行商[35]，根据旅行商出发城市及终点的不同又可细分为多类。MPTSP自提出以来，各国学者就不断地寻找求解方法，GAVISH等[36]通过改进分支界定法求解MPTSP，将TSP的求解空间规模扩大到100个城市；SINGH等[37]将遗传算法中染色体编码运用到MPTSP中；SONG等[38]运用改进的模拟退火算法解决了3个旅行商400个城市的MPTSP。总体来看，现有研究可较好地解决规模较小的MPTSP，但复杂的MPTSP仍然是人们关心的问题。

目前，虽然TSP得到广泛应用和研究，但几乎没有学者将装备维修任务调度问题抽象为旅行商问题进行研究。然而，对于装备维修任务调度，当考虑伴随修理以及巡回修理时，可将修理组看作旅行商，将待修装备看作城市，从而将装备维修任务调度问题转化为TSP，并可根据修理组数量、调度目标数量以及待修装备是否动态出现等特性进一步细化调度模型，确定约束条件，构造相应算法进行调度模型的求解。

2.2 车辆路径问题

车辆路径问题(Vehicle Routing Problem，VRP)可看作TSP与背包问题(Knapsack Problem，KP)的组合，其作为TSP的一个衍生问题最早由DANTZIG等[39]于1959年首次提出，VRP可描述为由1组车辆从1个或多个车场点出发对一系列顾客点进行服务，要求每个顾客点都必须被服务且只能由1辆车服务，所有车辆都从车场出发，最终回到车场，目标是总费用最小[40]。VRP自提出以来广泛运用于现实生活，如校车接送安排、城市垃圾收集、牛奶配送和快递配送等。对于维修任务调度，也可将其视为特殊的VRP。

随着各国学者对VRP研究的不断深入，引入了各种更贴近实际的限制条件，演化出一系列VRP扩展问题。VRP的构成要素包括车辆、车场点、顾客、道路与边约束[41]以及调度目标等。根据构成要素对VRP扩展问题进行分类梳理，如表1所示。

1) 带容量限制的车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)[42]。CVRP是指对于VRP中的每辆车辆，都有装载能力的限制。

2) 带时间窗限制的车辆路径问题(Vehicle Routing Problem with Time Windows，VRPTM)。VRPTM是对VRP中的每个顾客增加了服务窗口限制，即车辆对于每个顾客的服务必须在相应的时间窗内完成。根据时间窗的性质不同，VRPTM可进一步分为硬时间窗车辆路径问题(Vehicle Routing Problem with Hard Time Windows，VRPHTM)和软时间窗车辆路径问题(Vehicle Routing Problem with Soft Time Windows，VRPSTM)，其中：VRPHTM是指车辆对每个顾客的服务必须在相应的时间窗内完成，如果超出时间窗，则认为该次调度无效，即为非可行解[43]；VRPSTM是指车辆对每个顾客的服务可不在相应的时间窗内完成，若超出该时间窗则对目标函数进行惩罚[44]。

表1 车辆路径问题及其演化问题分类

3) 带分割的车辆路径问题(Vehicle Routing Problem with Split Deliveries，VRPSD)。VRPSD由DROR等[45]于1989年首次提出，与传统VRP中每个顾客的服务需求必须由1辆车来满足不同，VRPSD中顾客的服务需求可由多辆车分割服务[46]。VRPSD在现实生活中应用广泛，MULLASERIL等[47]将卡车配送牧场饲料的问题抽象为VRPSD；SIERKSMA等[48]将VRPSD引入直升机航班安排；LAI等[49]运用VRPSD解决了食物配送问题。除此之外，VRPSD还广泛运用于物资配送[50]、海上游轮调度[51]和抢险救灾问题[52]等。

4) 开放式车辆路径问题(Open Vehicle Routing Problem，OVRP)。OVRP由SCHRAGE[53]于1981年首次提出，与传统VRP中车辆必须返回出发车场不同，OVRP中的车辆完成顾客服务后不必返回车场。

5)异型车辆路径问题(Heterogeneous Fleet Vehicle Routing Problem，HFVRP)。HFVRP作为VRP的变异问题，更加贴近实际，其与传统VRP的区别是HFVRP中允许存在不同的车辆。

6)动态车辆路径问题(Dynamic Vehicle Routing Problem，DVRP)。DVRP由PSARAFITS[54]于1988年首次提出，与静态车辆路径问题不同，DVRP是指在调度前只知道部分顾客需求信息，其他信息将在调度过程中相继明确，且顾客需求在调度过程中会发生改变[40]。

根据服务需求信息可将VRP问题分成4类：静态确定问题、静态随机问题、动态确定问题和动态随机问题[55]。其中，前二类是传统意义上的VRP，后二类构成了DVRP。对于静态确定问题，模型中所有的输入在进行车辆调度前是已知的，不会随着调度的执行而改变[56]。对于静态随机问题，模型的部分输入是随机变量，并在调度过程中逐渐明确，通常包括随机顾客、随机时间和随机需求3种主要形式：1) 随机顾客，即所需服务的顾客是随机的；2) 随机时间，即服务的时间或旅行时间是随机的；3) 随机需求，即顾客的需求是随机的。对于动态确定问题，部分或全部输入是未知的，在制订调度计划或调度过程中会动态明确[57]。对于动态随机问题，部分或全部输入是未知的，在制订调度计划或调度过程中顾客、顾客需求以及服务时间会发生动态的变化[58]。

由于DVRP的研究对解决现实生活中的物流配送、交通运输和出租车载客等问题具有重大意义[59]，因此国内外研究者对DVRP进行了深入研究。在DVRP模型方面，BERTSIMAS等[60]在静态VRP模型的基础上，引入排队论模型较好地解决了修理员动态修理问题；MINKOFF[61]针对小规模DVRP提出了马尔可夫模型；TEODOROVIC等[62]通过用模糊数来表示信息的模糊性以及决策者的偏好，建立了模糊顾客需求的DVRP模型；PAVONE等[63]考虑顾客等待耐心的因素，通过引入惩罚函数建立了DVRP模型；谢秉磊等[64]考虑路网结构、容量限制以及负载均衡，建立了带临时补充点的融雪剂撒布车辆路径模型；葛显龙等[65]针对商业中心相对分散的问题，以运输距离、运输成本为目标，构建了城市物流联合配送DVRP模型；陈伟龙等[66]将进攻作战抢修任务调度问题抽象为开放式多车场车辆路径问题，以二次作战时间为目标函数，设计了变体遗传算法进行了模型求解，并验证了模型的可行性；陈伟龙等[67]还考虑了抢修时间、抢修能力以及修复状态的不确定性等因素，将进攻作战抢修任务调度问题抽象为动态车辆路径问题，针对多目标优化问题设计了遗传算法求解Pareto解。以上研究为车辆路径问题在装备维修任务调度方面的研究提供了良好的思路。

在装备维修任务调度中，可将修理组看作VRP中的车辆，各修理组携带的备品备件有携带能力限制，将各修理组携带的备品备件限制看作车辆的容量限制，则维修任务调度问题可转化为带容量限制的车辆路径问题(CVRP)；若考虑待修装备对修复时间的要求，则可将装备维修任务调度问题抽象为特殊的带时间窗限制的车辆路径问题(VRPTM)；若装备维修任务需要多个修理组协同完成，则可将装备维修任务调度问题抽象为特殊的带分割的车辆路径问题(VRPSD)；在伴随维修中，修理组在完成既定任务后还需要伴随保障部队进行后续作战任务，修理组不会返回原出发点，则可将装备维修任务调度问题看成是开放式车辆路径问题(OVRP)；各修理组的维修能力存在差异，各修理组携带的备品备件存在差异，则可将装备维修任务调度问题看成是异型车辆路径问题(HFVRP)；由于装备不断发生战损，调度方案随着待修装备的出现需要动态调整，则可将装备维修任务调度抽象为动态车辆路径问题(DVRP)。

2.3 项目调度问题

项目调度问题(Project Scheduling Problem，PSP)是指在时间和资源的限制下合理计划和安排项目进度以高效达到项目目标[68]。由于资源约束是项目调度的最常见约束，因此资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem，RCPSP)得到广泛研究。

RCPSP通常从资源、任务以及目标函数3方面进行分类[69]，三者之间随机组合构成了各种类型的RCPSP。资源可分为可更新资源、不可更新资源以及双重约束资源[70]，其中：可更新资源是指在调度的各个阶段可随时补充的、固定不变的资源，对于装备维修任务调度，若不考虑维修人员的伤亡及维修设备的损坏，则可将维修人员及维修设备看作可更新资源；不可更新资源是指在调度过程中随着使用而不断消耗的资源，对于装备维修任务调度，若认为修理组携带的备件数量有限，则可将备件看作不可更新资源；双重约束资源是指在调度的各个阶段都有约束，且在整个调度过程的总量也有限制的资源[71]，对于装备维修任务调度，若考虑整个维修时限及各阶段的维修时限，则可将时间视为双重约束资源。近年来，研究者提出了部分可更新资源概念[72]，其介于可更新资源与不可更新资源之间，对于装备维修任务调度，若考虑维修人员的休息时间及设备的维修保养时间，则可将维修人员及设备视为部分可更新资源。

RCPSP根据项目数量可分为单项目RCPSP和多项目RCPSP；根据执行模式可分为单模式RCPSP和多模式RCPSP[73]；根据任务是否可抢占可分为可抢占RCPSP和不可抢占RCPSP；根据资源的特性演化出柔性资源约束项目调度问题(Flexible Resource-Constrained Project Scheduling Problem，FRCPSP)。吕学志等[25]将任务间隔期装备维修任务调度问题抽象为FRCPSP，并将其称为柔性资源约束维修任务调度问题(Maintain Test-Flexible Resource Constrained Project Scheduling Problem，MT-FRCPSP)。

总体来说，项目调度模型是时间、资源约束调度问题的基本模型，许多实际问题都能抽象为带实际约束的项目调度问题，并可通过启发式算法或智能算法求解，为解决实际生活中的调度问题提供了模型基础，如作业车间调度问题、流水车间调度问题等。吕学志等[25]将维修人员、设备看作可更新的柔性资源，将任务间隔期内的装备维修任务调度问题抽象为RCPSP，分别考虑柔性资源约束、随机工期约束以及技能差异约束，构建了任务间隔期维修任务调度模型，具有一定的借鉴意义。但其研究的前提是任务间隔期内的维修任务调度问题，而战时装备维修特别是战术级装备维修通常采取伴随修理为主，巡回修理与定点修理相结合的方式。因此,将装备维修任务调度问题抽象为RCPSP，对定点修理具有一定指导意义，但对伴随修理和巡回修理并不是很合理。

对于定点修理或基地级修理的装备维修任务调度问题，可将维修人员、设备和备品备件等作为项目调度(PSP)中的资源。根据调度实际抽象出资源约束条件，结合修理工期等时间约束、修理技能等能力约束，抽象为资源受限的项目调度问题(RCPSP)，并采取启发式算法或智能算法进行求解。

2.4 车间调度问题

车间调度问题(Shop Scheduling Problem，SSP)是项目调度问题的进一步演化，是一种资源分配与调度问题，可简单地描述为n个工件在m台机器上加工，每个工件有多道工序，机器可执行多道工序，但各机器可执行的工序不完全相同，主要解决如何为各工件安排机器，为工件安排加工次序及加工起止时间，进而实现调度目标的最优化[74]。根据机器功能、工件工序以及工序顺序,可将车间调度问题分为以下3类[75]：

1) 作业车间调度问题(Job-shop Scheduling Problem，JSP)。系统中有多台功能不同的机器，各工件有多道工序，每道工序只能在1台机器上执行，各工件的加工路径不同，各工序间有顺序要求。

2) 流水车间调度问题(Flow Shop Scheduling Problem，FSSP)。与JSP的条件一样。

3) 开放车间调度问题(Open Shop Scheduling Problem，OSSP)。各工件加工路径没有约束，各工序的加工顺序没有约束。

随着车间调度问题研究的不断深入，在以上3类问题的基础上逐渐演化出柔性作业车间调度问题(Flexible Job-shop Scheduling Problem，FJSP)、多目标柔性作业车间调度问题(Multi-Objective Flexible Job-shop Scheduling Problem，MOFJSP)、混合流水车间调度问题(Hybrid Flow Shop Scheduling Problem，HFSSP)等多种新问题，实际车间加工过程一般是多种车间调度问题的混合问题。

在装备维修任务调度方面，孙志刚等[76]考虑了定点维修机构内维修专业的设置问题，将批量维修任务调度问题抽象为置换流水车间调度问题，并采用最长加工时间启发式算法进行了模型求解。朱昱等[77]针对装备维修厂(所)的维修任务调度问题，考虑到维修流程，将多单元维修任务调度问题抽象为置换流水车间调度问题，并设计了NEH(Nawaz,Enscore and Ham)迭代式算法用于模型求解。

总体来说，在装备维修任务调度方面，对于定点修理或基地级修理，在某种程度上可将装备维修任务进一步细化，考虑各修理工种及工序的相关约束，将装备维修任务调度问题转换为车间调度问题(SSP)，并考虑维修资源、维修专业和维修流程等现实问题，合理确定调度目标并抽象出约束条件，从而选择合适的调度算法进行模型求解。

3 维修任务调度算法研究现状

随着TSP、VRP、PSP和SSP等调度模型问题研究的不断完善和深入，调度模型求解问题已逐渐成为维修任务调度研究的重点，涌现出许多求解算法。总体来说，维修任务调度模型的求解算法可分为精确算法[78]与启发式算法[79]。精确算法通过搜索整个问题的解空间以求得最优解，当模型复杂、求解规模较大时，精确算法所需的求解时间急剧增加，容易发生指数爆炸问题，因此，在应用中具有一定的局限性。启发式算法不需要求出确切的最优解，仅以在合理时间内得出满意解为目标，因此，相对精确算法而言，其应用更为广泛。

各种算法在求解调度模型时都具有自身的局限性，所构造的调度模型类型、约束条件和调度目标等因素均会影响调度算法的选择，同时，算法的计算时间、收敛速度、鲁棒性和可靠性等也是衡量算法优劣的重要因素。笔者仅针对不同维修任务调度模型来综述相应模型求解算法的研究现状。

3.1 旅行商问题求解算法

随着TSP研究的不断深入，相应的求解算法已成为TSP研究的重点，主要有精确算法和启发式算法2个方向。求解TSP的精确算法主要包括分支界定法[80]、线性规划法和动态规划法等。由于精确算法需要精确求解，当TSP规模较大时，其计算复杂度呈指数增长，需要消耗巨大的时间代价[81]，因此在实践中的运用并不广泛。启发式算法能在合理时间内得到近似解甚至最优解，因此，得到了广泛应用和发展。启发式算法可进一步分为构造型算法与改进型算法[79]。构造型算法从非法解出发，通过某些策略不断迭代改进解的质量直到合法解，常见的构造型算法有最近邻域算法[82]和随机贪婪算法[83]等。改进型算法是在构造型算法的基础上运用智能算法进行改进，常见的改进型算法有模拟退火算法[84]、遗传算法[85]、禁忌搜索算法[86]、蚁群算法[87]、粒子群算法[88]、萤火虫算法[89]、狼群算法[90]、生物地理迁移算法[91]、帝国主义竞争算法[92]、离散状态转移算法[93]以及这些算法的混合运用及改进[94]。

3.2 车辆路径问题求解算法

在VRP算法方面，DVRP作为VRP中应用最广泛的类型，被证明是NP-Hard问题，其约束条件比传统TSP更多，而由于DVRP具有多时间维度、动态性、开放性、不确定性和信息更新机制等特点，对求解算法的要求更高，因此应用精确算法很难求解DVRP，一般采用启发式算法及其改进算法进行求解。CHEN等[95]提出了推—碰—掷3阶段改进的遗传算法来求解模糊服务时间的DVRP；LIAO等[96]将扫描法与禁忌搜索算法相结合，通过扫描法确定车辆数，再根据动态信息进行禁忌搜索来求得可行解，可在一定程度上弥补禁忌搜索收敛速度慢的不足；CHEUNG等[97]提出了基于抽样的启发算法求解需求点随机的DVRP；吴天羿等[98]针对模糊需求的DVRP，将扫描算法、遗传算法以及差分进化算法相结合，通过构造差分扫描变异算子提高遗传算法的求解性能，进而求解了模糊需求的DVRP；谢秉磊等[99]针对随机顾客和随机需求的DVRP，提出了多回路优化策略，改进了混合领域结构的模拟退火算法，提高了模拟退火算法的收敛速度。

3.3 项目调度问题求解算法

在RCPSP算法方面，由于精确算法求解时间长，一般在求解时采用启发式算法及智能算法。DAVIS等[100]提出了多路算法，用于生成可行调度解；LI等[101]提出了正向-逆向调度算法，通过交替进行正、逆向调度，有效地提高了解的质量；KLEIN[102]通过引入禁忌搜索算法将活动列表生成串行调度策略，较好地解决了时变资源约束的RCPSP;郑晓龙等[103]在果蝇算法中引入协作进化环节，提出了基于序的果蝇算法,用于解决随机工期的RCPSP；靳金涛等[104]将船舶分段建造问题抽象为空间资源受限的RCPSP，提出了一种人工蜂群算法，并通过不同规模的实例对比验证了算法的优越性；刘欣仪等[105]针对作业时间依赖资源分配决策的RCPSP，提出了1-opt和2-opt局部搜索改进遗传算法，并通过数据试验验证了算法的可行性。

3.4 车间调度问题求解算法

国内外研究者对不同类型的车间调度问题进行了深入研究，以作业车间调度问题(JSP)为代表的车间调度问题被证明是NP-Hard问题[106]，于是研究重点转向了启发式算法及智能算法。FATTAHI等[107]将禁忌搜索算法与模拟退火算法相结合，改善了模拟退火算法的收敛速度及局部收敛问题，用于解决柔性作业车间调度问题；SU等[108]针对混合流水车间调度问题(HFSSP)，将活动调度技术与遗传算法相结合，构造了EGTGA(Extend Giffler Thompson Genetic Algorithm)算法，并通过仿真实验验证了EGTGA算法的搜索效率得到了提高；徐华等[109]以最大完工时间、生产成本以及生产质量为调度目标构建了多目标柔性作业车间调度问题(MOFJSP)，设计了混合离散蝙蝠算法，较好地避免了算法早熟问题，并通过实例验证了算法的性能；李知聪等[110]在生物地理学算法的基础上引进了改进策略，增强了算法的搜索能力和收敛速度，并将其运用于混合流水车间调度问题(HFSSP)的求解；赵博选等[111]针对MOFJSP中作业分配与作业排序2阶段的特性，设计了2阶段的混合Pareto蚁群算法，并通过与其他文献的对比验证了该算法可提高解的质量。

4 研究展望

综上所述，已有的研究工作对维修任务调度问题进行了深入研究，但在装备维修任务调度的模型及算法方面还存在一定的不足，有待进一步开展研究，具体表现在以下4个方面：

1) 目前关于装备维修任务调度的研究大多将其视为非抢占调度，认为在维修任务执行过程中不能中断，然而战时战场态势瞬息万变，待修装备重要程度、任务紧急程度等因素交错复杂，仅考虑维修任务的非抢占调度缺乏对任务突发性及紧急性的考虑，容易导致维修任务调度不合理、维修资源利用不充分等问题。因此，针对装备维修任务调度问题，在贴近战场实际的基础上，根据调度目标对维修任务的抢占调度进行深入研究,是合理调度装备维修任务的有效途径。

2) 装备维修任务调度策略作为维修任务调度的核心，是开展装备维修任务调度的基础。目前装备维修任务调度多以静态优先级调度策略为主，忽略了待修装备维修优先级会随着战斗阶段的改变而动态变化的问题。应在定量分析维修任务动态优先级的基础上，根据修理方式及调度目标将维修任务动态优先级调度策略与其他调度策略相结合，以实现调度目标的最优化。

3) 装备维修任务调度问题作为复杂的组合优化问题，目前针对装备维修任务调度模型的研究多是宽泛地将其整个过程抽象为TSP等模型，忽略了不同维修方式及修理范围对模型构建的影响。事实上，对于不同的维修方式，应建立不同的维修任务调度模型，如：对于伴随修理及巡回修理，适合于抽象为旅行商问题或车辆路径问题；对于定点修理及基地级修理适合于抽象为项目调度问题或车间调度问题。在具体模型构建过程中,还应考虑调度目标、约束条件等因素。

4) 装备维修任务调度问题作为工程实际问题，涉及的约束条件及影响因素众多，因此在模型构建前要根据战场实际明确调度的目标函数和约束条件。不同的调度算法其适应性也不同，在求解调度模型时，应综合考虑模型算法的收敛速度、鲁棒性和可靠性等因素，针对其缺陷进行合理的改进，且多种算法互补结合是调度模型算法研究的趋势。

参考文献：

[1] 巴巍,实时系统动态优先级任务调度算法的研究[D].大连:大连理工大学,2010：4.

[2] 姚敏,王绪芝,赵敏.无人机群协同作战任务分配方法研究[J].电子科技大学学报,2013,42(5):723-727.

[3] 陈盈果.面向任务的快速响应空间微型部署优化设计方法研究[D].长沙:国防科学技术大学,2014：5-9.

[4] 宋业新,陈绵云,张曙红.多目标指派问题及其在军械物资供应中的应用[J].系统工程理论与实践,2001,21(11):141-144.

[5] 王沁,袁玲玲,张燕.固定优先级抢占任务调度算法下非周期任务实时性能研究[J].小型微型计算机系统,2011,32(6):1025-1029.

[6] 彭浩,韩江洪,陆阳,等.多处理器硬实时系统的抢占阈值调度研究[J].计算机研究与发展,2015,52(5):1177-1186.

[7] ZHAO W,RAMAMRITHAM K,STANKOVIC J.Preemptive scheduling under time and resource constraints[J].IEEE transactions on computers,1987,36(8):949-960.

[8] LEVI R,MAGNANTI T,MUCKSTADT J,et al.Maintenance scheduling for modular systems:modeling and algorithms[J].Naval research logistics,2014,61(6):472-488.

[9] 姚双印,韩庆田.BFOA在军械装备维修任务调度中的应用[J].海军航空工程学院学报,2011,26(5):558-560.

[10] 崔嘉,杨林,胡卫民.改进的细菌觅食算法在航空装备维修任务调度优化中的应用[J].海军航空工程学院学报,2011,26(2):189-194.

[11] 王建华,黄贤凤,梅强,等.离散可调度时段下多供应商敏捷供应链静态调度优化[J].计算机集成制造系统,2015,21(10):2739-2745.

[12] NELSON R T,HOLLOWAY C A,WANG R M L.Centralized scheduling and priority implementation heuristics for a dynamic job shop model[J].AIIE transactions,1977,9(1):95-102.

[13] 张国辉,王永成,张海军.多阶段人机协同求解动态柔性作业车间调度问题[J].控制与决策,2016,31(1):169-172.

[14] HAN C C,LIN K J,HOU C J.Distance-constrained scheduling and its applications to real-time systems[J].IEEE transactions on computers,1996,45(7):814-826.

[15] BUTTAZZO G C.Rate monotonic vs EDF:judgment days[J].Real time systems,2005(29):5-26.

[16] WANG Y,SAKSENA M.Scheduling fixed-priority tasks with preemption threshold[C]∥Proceedings of the 6th International Conference on Real Time Computing Systems and Applications.Hong Kong:IEEE Computer Society Press,1999:328-335.

[17] 夏家莉,陈辉,杨兵.一种动态优先级实时任务调度算法[J].计算机学报,2012,35(12):2685-2695.

[18] LEVCHUK G M,LEVCHK Y M,LUO J,et al.Normative design of organizations:part I:mission planning[J].IEEE transactions on systems,man,and cybernetics：part a system and humans,2002,32(3):346-359.

[19] 徐玖平,吴巍.多属性决策的理论与方法[M].北京:清华大学出版社,2006:78-81.

[20] 轩华.基于FCFS策略的带时间窗车队调度问题研究[J].交通运输系统工程与信息,2013,13(6):140-146,175.

[21] JOUINI O.Analysis of a last come first served queueing system with customer abandonment[J].Computers & operations research,2012(39):3040-3045.

[22] 吕学志,于永利,张柳,等.伴随修理中的维修任务调度策略[J].系统工程理论与实践,2013,33(1):209-214.

[23] 唐恒永,赵传立.排序引论[M].北京:科学出版社,2002:68-69.

[24] GLAD R F,PIERCE R T.A comparison of selected scheduling heuristics for TAC F-4E maintenance organization[R].Ohio:Air Force Institute of Technology,Wright-Patterson Air Force Base,1976.

[25] 吕学志,于永利.面向任务的装备作战单元维修决策[M].北京:国防工业出版社,2014:147-149.

[26] 任帆,吕学志,王宪文,等.巡回修理中的维修任务调度策略[J].火力与指挥控制,2013,38(12):171-175.

[27] MISHRA S,BATTA R,SZCZERBA R J.A rule based approach for aircraft dispatching to emerging targets[J].Military operations research,2004,9(3):17-30.

[28] LOVE A,TORMOS P.Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling[J].Annals of operations research,2001(102):263-286.

[29] 吕学志,王宪文,范保新,等.定点修理中维修任务调度策略的仿真评估[J].火力与指挥控制,2015,40(1):70-76.

[30] UGUR A,AYDIN D.An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms[J].Advances in engineering software,2009,40(5):341-349.

[31] 张鑫龙,陈秀万,肖汉,等.一种求解旅行商问题的新型帝国竞争算法[J].控制与决策,2016,31(4):586-592.

[32] 李锋,魏莹.基于仿真的遗传算法求解动态旅行商问题[J].系统管理学报,2009,18(5):591-595.

[33] ELAOUD S,TEGHEM J,LOUKIL T.Multiple crossover genetic algorithm for the multiobjective traveling salesman problem[J].Electronic notes in discrete mathematics,2010(36):939-946.

[34] 李锋.基于偏好信息的多目标旅行商问题Pareto优化求解[J].系统工程学报,2011,26(5):592-598.

[35] BEKTAS T.The multiple traveling salesman problem:an overview of formulations and solution procedures[J].Omega,2006(34):209-219.

[36] GAVISH B,SRIKANTH K.An optimal solution method for large-scale multiple traveling salesman problems[J].Operations research,1986,34(5):698-717.

[37] SINGH A,BAGHEL A S.A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J].Soft comput,2009(13):95-101.

[38] SONG C H,LEE K,LEE W D.Extended simulated annealing for augmented TSP and multi-salesmen TSP[C]∥ Proceeding of the International Joint Conference on Neural Networks.Oregon,USA:IEEE,2003,3:2340-2343.

[39] DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management science,1959,6(1):80-91.

[40] PILLAC V,GENDREAU M,CHRISTELLE G,et al.A review of dynamic vehicle routing problem[J].European journal of operational research,2013(225):1-11.

[41] 李相勇.车辆路径问题模型及算法研究[D].上海:上海交通大学,2007:11-13.

[42] TLILI T,FAIZ S,KRICHEN S.A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem[J].Procedia-social and behavioral sciences,2014(109):779-783.

[43] KALLEHAUGE B.Formulations and exact algorithms for the vehicle routing problem with time windows[J].Computers & operations research,2008(35):2307-2330.

[44] KOHL N,MADSEN O B G.An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J].Operations research,1997,45(3):395-406.

[45] DROR M,TRUDEAU P.Savings by split delivery routing[J].Transportation science,1989,23(2):141-145.

[46] DROR M,TRUDEAU P.Split delivery routing[J].Naval research logistics,1990,37(7):383-402.

[47] MULLASERIL P A,DROR M,LEUNG J.Split-delivery routing heuristics in livestock feed distribution[J].Journal of the operational research society,1997,48(2):107-166.

[48] SIERKSMA G,TIJSSEN G A.Routing helicopters for crew exchanger on off-shore location[J].Annals of operations research,1998,76(1):261-286.

[49] LAI M,BATTARRA M,FRANCESCO M D,et al.An adaptive guidance meta-heuristic for vehicle routing problem with splits and clustered backhauls[J].Journal of the operational research society,2015,66(7):1222-1236.

[50] YAN S Y,CHU J C,HSIAO F Y,et al.A planning mode and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows[J].Computers & industrial engineering,2015(87):383-393.

[51] LEE J S,KIM B I.Industrial ship routing problem with split delivery and two types of vessels[J].Expert systems with applications,2015(42):9012-9023.

[52] WANG H,DU L,MA S.Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake[J].Transportation research part E:logistics and transportation review,2014,69:160-179.

[53] SCHRAGE L.Formulation and structure of more complex realistic routing and scheduling problem[J].Networks,1981,11(2):229-232.

[54] PSARAFTIS H N.Dynamic vehicle routing problems[J].Vehicle routing methods & studies,1988,23(8):661-673.

[55] BERTSIMAS D J,SIMCHI L D.A new generation of vehicle routing research:robust algorithms,addressing uncertainty[J].Operation research,1996,44(2):286-304.

[56] LAPORTE G.Fifty years of vehicle routing[J].Transportation science,2009,43(4):408-416.

[57] JAILLET P,WAGNER M R.Generalized online routing:new competitive ratios,resource augmentation,and asymptotic analyses[J].Operations research,2008,56(3):745-757.

[58] BROTCORNE L,LAPORTE G,SEMET F.Ambulance location and relocation models[J].European journal of operational research,2003(147):451-463.

[59] 韩娟娟,李永先.动态车辆路径问题研究综述[J].绿色科技,2015(5):285-287.

[60] BERTSIMAS D J,RYZIN G.V.A stochastic and dynamic vehicle routing problems in the Euclidean plane[J].Operations research,1991,39(4):601-615.

[61] MINKOFF A S.A markov decision mode land decomposition heuristic for dynamics vehicle dispatching[J].Operations research,1993,41(1):77-90.

[62] TEODOROVIC D,PAVKOVIC G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy sets and systems,1996(82):307-317.

[63] PAVONE M,BISNIK N,FRAZZOLI E,et al.A stochastic and dynamic vehicle routing problem with time windows and customer impatience[J].Mobile networks & applications,2009(14):350-364.

[64] 谢秉磊,李颖,刘敏.带临时补充点的融雪剂撒布车辆路径问题[J].系统工程理论与实践,2014,34(6):1593-1598.

[65] 葛显龙,徐茂增,王伟鑫.基于联合配送的城市物流配送路径优化[J].控制与决策,2016,31(3):503-512.

[66] 陈伟龙,陈春良,史宪铭,等.基于变体GA的进攻作战抢修任务动态调度[J].系统工程与电子技术,2017,39(3):577-583.

[67] 陈伟龙,陈春良,陈康柱,等.考虑不确定性的进攻作战抢修任务动态调度[J].兵工学报,2017,38(5):1011-1019.

[68] 熊燕华,沈厚才,周晶,等.工程项目调度技术研究综述[J].数学的实践与认识,2013,43(21):1-14.

[69] HARTMANN S.Project scheduling under limited resources:Models,methods,and applications [M].Berlin:Springer,1999:21-22.

[70] 张松.资源受限项目调度若干问题研究[D].合肥:中国科学技术大学,2014:13-14.

[71] 方晨,王凌.资源约束项目调度研究综述[J].控制与决策,2010,25(5):641-650.

[73] ELMAGHRABY S.Activity networks:project planning and control by network models[M].New York:John Wiley& Sons,1977:33-34.

[74] 张国辉.柔性作业车间调度方法研究[D].武汉:华中科技大学,2009:5-6.

[75] 李峥峰.多时间因素作业车间调度问题的研究与工程应用[D].武汉:华中科技大学,2010:5.

[76] 孙志刚,朱小东,李锋.一种考虑权重的多专业流水式批量维修任务调度模型[J].装甲兵工程学院学报,2012,26(2):24-28.

[77] 朱昱,宋建社,曹继平,等.一种考虑装备维修流程的多维修任务调度[J].系统工程与电子技术,2008,30(7):1366-1369.

[78] 曾华.随机顾客和需求的配送优化模型与算法[D].山东:山东大学,2012:18-19.

[79] DORIGO M,BIRATTARI M,STUTZLE T.Ant colony optimization[J].IEEE computational intelligence magazine,2007,1(4):28-39.

[80] 曹平方,李灵,李诗珍.基于分支界定的VRP模型精确算法研究及应用[J].包装工程,2014,35(17):97-101.

[81] 饶卫振,金淳,黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践,2011,31(8):1419-1428.

[82] 王海鹏,熊伟,何友,等.集中式多传感器概率最近邻域算法[J].仪器仪表学报,2010,31(11):2500-2507.

[83] 陈荣光,李春升,陈杰,等.基于贪婪算法的近空间平台区域覆盖优化设计[J].北京航空航天大学学报,2009,35(5):547-550.

[84] KIRKPATRICK S,GELATT C D,VECCHI M P.Optimization by simulated annealing[J].Science,1983，220(4598):671-680.

[85] LIU C,KROLL A.On designing genetic algorithms for solving small and medium-scale traveling salesman problems[J].Lecture notes in computer science,2012(7269):283-291.

[86] 余丽,陆锋,杨林.交通网络旅行商路径优化的遗传禁忌搜索算法[J].测绘学报,2014,43(11):1197-12303.

[87] NECULA R,BREABAN M,RASCHIP M.Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem[J].Lecture notes in computer science,2015(9121):257-268.

[88] LIAO Y F,YAU D H,CHEN C L.Evolutionary algorithm to tra-veling salesman problems[J].Computers and mathematics with applications,2012(64):788-797.

[89] 于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法[J].华南理工大学学报(自然科学版),2015,43(1):126-131.

[90] 吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015,30(10):1861-1867.

[91] MO H W,XU L F.Biogeography migration algorithm for traveling salesman problem[J].International journal of intelligent computing and cybernetics,2010(6145):405-414.

[92] YOUSEFIKHOSHBAKHT M,SEDIGHPOUR M.New imperialist competitive algorithm to solve the travelling salesman problem[J].International journal of computer mathematics,2013,90(7):1495-1550.

[93] YANG C H,TANG X L,ZHOU X J,et al.A discrete state transition algorithm for traveling salesman problem[J].Control theory and applications,2013,30(8):1040-1046.

[94] ALBAYRAK M,ALLAHVERDI N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert systems with applications,2011(38):1313-1320.

[95] CHEN R,GEN M,TOZAWA T.Vehicle routing problem with fuzzy due-time using genetic and systems algorithms[J].Journal of Japan society for fuzzy theory and systems,1995,7(5):1050-1061.

[96] LIAO T Y,HU T Y.An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information[J].Expert systems with applications,2011(38):12548-12558.

[97] CHEUNG R K,XU D,GUAN Y.A solution method for a two-dispatch delivery problem with stochastic customers[J].Journal of mathematical modeling and algorithms,2007(6):87-107.

[98] 吴天羿,许继恒.基于混合遗传算法的模糊需求车辆路径问题[J].解放军理工大学学报(自然科学版),2014,15(5):475-483.

[99] 谢秉磊,安实,郭辉煌.随机车辆路径问题的多回路优化策略[J].系统工程理论与实践,2007,27(2):167-171.

[100] DAVIS E W,PATTERSON J H.A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J].Management science,1975,21(8):944-955.

[101] LI K Y,WILLIS R J.An iterative scheduling technique for resource-constrained project scheduling[J].European journal of operational research,1992(56):370-379.

[102] KLEIN R.Project scheduling with time-varying resource constraints[J].International journal of production research,2000,38(16):3937-3952.

[103] 郑晓龙,王凌.随机资源约束项目调度问题基于序的果蝇算法[J].控制理论与应用,2015,32(4):540-545.

[104] 靳金涛,聂兰顺,战德臣,等.基于人工蜂群的空间资源受限项目调度算法[J].计算机集成制造系统,2014,20(5):1088-1098.

[105] 刘欣仪,陆志强.作业时间依赖资源分配决策的项目调度问题建模与算法[J].上海交通大学学报,2017,51(1):82-89.

[106] MARICHELVAM M K,PRABAHARAN T,YANG X S.Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J].Applied soft computing,2014(19):93-101.

[107] FATTAHI P,MEHRABAD M S,JOLAI F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].Journal of intelligent manufacturing,2007(18):331-342.

[108] SU Z X,LI T.Genetic algorithm for minimizing the makespan in hybrid flow shop scheduling problem[C]∥Proceedings of the 3rd International Conference on Management and Service Sciences.Washington,USA:IEEE,2009:1-4.

[109] 徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.

[110] 李知聪,顾幸生.改进的生物地理学算法在混合流水车间调度中的应用[J].化工学报,2016,67(3):751-757.

[111] 赵博选,高建民,陈琨.求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法[J].2016,50(7):145-151.