基于双层规划的装备保障优化预调度

doi:10.3969/j.issn.1009-086x.2024.05.016

摘要/Abstract

摘要：

装备保障影响作战任务完成质量甚至直接关系任务成败，装备保障优化调度是提升装备保障系统效益的关键。针对装备保障系统双层决策和组合优化的特点，提出一种基于双层规划的装备保障优化预调度模型。分析装备保障系统运行过程和建模框架；结合组合优化问题，建立双层规划模型，上层为粗粒度层，采用MTSP(multiple travelling salesman problem)方法，下层为细粒度层，采用JSP（job-shop scheduling problem）方法；通过改进MTSP算法设计和迁移JSP算法描述构建双层迭代算法进行模型求解。算例分析表明：该方法在大规模系统优化调度中具有结构开放性和参数适应性。

关键词: 装备保障, 双层规划, 预调度, 大规模优化调度, 改进MTSP

Abstract:

Equipment support affects the completion quality of combat missions and even directly affects the success or failure of missions. Optimized scheduling of equipment support is the key to improve the efficiency of equipment support system. Aiming at the characteristics of two-layer decision making and combinatorial optimization of equipment support system， an optimized pre-scheduling model for equipment support based on two-layer programming is proposed. The operation process and modeling framework of the equipment support system are analyzed. Combining with the combinatorial optimization problem， a two-layer programming model is established. The upper layer is a coarse-grained layer， using the MTSP method and the lower layer is a fine-grained layer， using the JSP method. An example analysis shows that the proposed method has open structure and adaptive parameters in large-scale system scheduling optimization.

Key words: equipment support, two-layer planning, pre-scheduling, Large scale optimization scheduling, improving multiple travelling salesman problem（MTSP）

中图分类号:

TJ02

胡志刚, 楼京俊, 史跃东. 基于双层规划的装备保障优化预调度[J]. 现代防御技术, 2024, 52(5): 147-155.

Zhigang HU, Jingjun LOU, Yuedong SHI. Optimal Prescheduling of Equipment Support Based on Two-Layer Programming[J]. Modern Defense Technology, 2024, 52(5): 147-155.

图/表 14

图1 装备保障系统运行过程

Fig. 1 Operation process of equipment support system

图2 基于双层规划的装备保障优化调度模型框架

Fig. 2 Equipment support optimization scheduling model framework based on two-layer programming

表1 基本数学符号

Table1 Basic mathematical symbol

符号	定义
$A i$	保障对象 $i$ ， $i ∈ 1,2, ⋯, N F$
$M i j$	保障对象 $i$ 的第 $j$ 项保障工作
$t s M i j$	保障对象 $i$ 的第 $j$ 项工作所需工作时间
$m i j$	保障对象 $i$ 的第 $j$ 项保障工作数量
$B k$	保障单元 $k$ ， $k ∈ 1,2, ⋯, N U$
$B k l$	保障单元 $k$ 的第 $l$ 种资源数量， $l ∈ 1,2, ⋯, N R$
$L B k$	$B k$ 上的资源种类个数
$v k$	保障单元 $k$ 的资源运输速度
$R i 1 l$	第 $i 1$ 个任务在第 $l$ 种资源上的完成时间
$L t i 1 l$	第 $i 1$ 个任务在第 $l$ 种资源上的保障时间
$D i 1 i 2$	保障对象 $i 1$ 到保障对象 $i 2$ 之间的距离
$x i k$	$x i k ∈ 0,1$ ，对 $A i$ 是否分配给 $B k$ ，0表示“否”，1表示“是”

表1 基本数学符号

Table1 Basic mathematical symbol

符号	定义
$A i$	保障对象 $i$ ， $i ∈ 1,2, ⋯, N F$
$M i j$	保障对象 $i$ 的第 $j$ 项保障工作
$t s M i j$	保障对象 $i$ 的第 $j$ 项工作所需工作时间
$m i j$	保障对象 $i$ 的第 $j$ 项保障工作数量
$B k$	保障单元 $k$ ， $k ∈ 1,2, ⋯, N U$
$B k l$	保障单元 $k$ 的第 $l$ 种资源数量， $l ∈ 1,2, ⋯, N R$
$L B k$	$B k$ 上的资源种类个数
$v k$	保障单元 $k$ 的资源运输速度
$R i 1 l$	第 $i 1$ 个任务在第 $l$ 种资源上的完成时间
$L t i 1 l$	第 $i 1$ 个任务在第 $l$ 种资源上的保障时间
$D i 1 i 2$	保障对象 $i 1$ 到保障对象 $i 2$ 之间的距离
$x i k$	$x i k ∈ 0,1$ ，对 $A i$ 是否分配给 $B k$ ，0表示“否”，1表示“是”

图3 组合优化问题中的遗传算法操作算子

Fig. 3 Genetic algorithm operators in combinatorial optimization problems

图4 MTSP中的遗传算法染色体编码

Fig. 4 Genetic algorithm chromosome coding in MTSP

图5 JSP中的遗传算法染色体编码

Fig. 5 Genetic algorithm chromosome coding in JSP

图6 保障对象分布

Fig. 6 Guarantee object distribution

表2 保障任务-任务步骤可选保障资源

Table 2 Safeguard task-task step optional security resources

	S1	S2	S3	S4	S5	S6
Ta1	3	［1，5，8］	［3，4］	［2，3，6］	［2，5］	7
Ta2	5	［2，3，8］	［6，8］	2	［4，5］	［1，7］
Ta3	［5，8］	［6，7］	［2，7］	［1，3，4］	4	［2，5］
Ta3	［2，4］	［2，5］	［4，6，7］	1	［5，8］	［3，6］

表3 保障任务-任务步骤相应资源所用时间

Table 3 Safeguard task-task step resource usage time

	S1	S2	S3	S4	S5	S6
Ta1	3	［1，5，3］	［3，4］	［2，3，6］	［2，5］	4
Ta2	4	［2，4］	［6，7，2］	2	［4，5］	［1，6］
Ta3	［5，6］	［6，7］	［2，7］	［1，3，4］	2	［2，5］
Ta3	［2，4］	［2，5］	［4，6，7］	3	［5，4］	［3，2］

图7 计算结果

Fig. 7 Calculation result

图8 保障资源预调度方案

Fig. 8 pre-scheduling scheme

图9 迭代次数为1 000时的计算结果

Fig. 9 Calculation result of 1 000 iterations

图10 任务影响单元个数变化时（6、9）

Fig. 10 Number of task affects units changing（6/9）

图11 保障规模增大时

Fig. 11 Increase of guarantee scale

参考文献 20

1	孙昱，毛少杰，周阳，等. 复杂任务关系约束下的作战资源调度方法［J］. 指挥信息系统与技术， 2021， 12（6）： 39-44， 72.
	SUN Yu， MAO Shaojie， ZHOU Yang， et al. Operational Resource Scheduling Method Under Complex Task Relation Constraint［J］. Command Information System and Technology， 2021， 12（6）： 39-44， 72.
2	吴靳，戴明强，王俊杰，等. 基于学徒制算法的航母舰载机保障作业调度［J］. 中国舰船研究， 2022， 17（4）： 145-154.
	WU Jin， DAI Mingqiang， WANG Junjie， et al. Carrier-Based Aircraft Operation Support Scheduling Based on Apprenticeship Learning Algorithm［J］. Chinese Journal of Ship Research， 2022， 17（4）： 145-154.
3	孙笑，宋卫星，班利明，等. 复杂人力资源约束下的抢占式维修工序调度［J］. 控制与决策， 2022， 37（2）： 393-400.
	SUN Xiao， SONG Weixing， BAN Liming， et al. Preemptive Maintenance Process Scheduling Under Complex Human Resource Constraints［J］. Control and Decision， 2022， 37（2）： 393-400.
4	杨帆，王铁宁，高晟. 面向任务的装备器材需求预测［J］. 火力与指挥控制， 2021， 46（4）： 48-53.
	YANG Fan， WANG Tiening， GAO Sheng. Demand Forecasting of Equipment Materials Oriented to Tasks［J］. Fire Control & Command Control， 2021， 46（4）： 48-53.
5	朱石坚. 舰船装备保障资源需求半结构化预测方法［J］. 海军工程大学学报， 2015， 27（4）： 54-59.
	ZHU Shijian. Semi-Structural Prediction Method Study on Support Resources Demand of Warship Equipment［J］. Journal of Naval University of Engineering， 2015， 27（4）： 54-59.
6	高龙，曹军海，宋太亮，等. 分布式装备保障体系任务分配模型［J］. 装甲兵工程学院学报， 2018， 32（6）： 13-21.
	GAO Long， CAO Junhai， SONG Tailiang， et al. Distributed Task Assignment Model for Equipment Support System［J］. Journal of Academy of Armored Force Engineering， 2018， 32（6）： 13-21.
7	马海英，金学科，刘力. 区域联合作战装备保障任务分配模型［J］. 火力与指挥控制， 2017， 42（8）： 72-75.
	MA Haiying， JIN Xueke， LIU Li. Research of Joint Equipment Support Task Assignment Model in Area Combat［J］. Fire Control & Command Control， 2017， 42（8）： 72-75.
8	包泽钰，柏林，曲寒炬. 考虑能力更新的航空备件供应系统任务分配模型［J］. 信息技术与信息化， 2019（11）： 88-91.
	BAO Zeyu， BAI Lin， QU Hanju. Task Assignment Model for Aviation Spare Parts Supply Systems to be Considered for Capacity Updates［J］. Information Technology and Informatization， 2019（11）： 88-91.
9	祝东攀，曹继平，毕杰. 基于多目标问题的装备维修保障资源调度研究［J］. 现代防御技术， 2023， 51（2）： 119-126.
	ZHU Dongpan， CAO Jiping， BI Jie. Scheduling of Equipment Maintenance and Support Resources Based on Multi-Objective Problem［J］. Modern Defence Technology， 2023， 51（2）： 119-126.
10	路程昭，龚建兴，朱雷，等. 资源约束条件下任务调度算法研究［J］. 系统工程与电子技术， 2021， 43（12）： 3586-3593.
	LU Chengzhao， GONG Jianxing， ZHU Lei， et al. Research on Task Scheduling Algorithm in Resource-Constrained Environments［J］. Systems Engineering and Electronics， 2021， 43（12）： 3586-3593.
11	曾斌，姚路，胡炜，等. 考虑不确定因素影响的保障任务调度算法［J］. 系统工程与电子技术， 2016， 38（3）： 595-601.
	ZENG Bin， YAO Lu， HU Wei， et al. Scheduling Algorithm for Maintenance Tasks Under Uncertainty［J］. Systems Engineering and Electronics， 2016， 38（3）： 595-601.
12	曹军海，张闯，李延通，等. 装备维修器材预储点选址与预置运输配送组合优化方法［J］. 兵工学报， 2022， 43（10）： 2668-2678.
	CAO Junhai， ZHANG Chuang， LI Yantong， et al. Combinatorial Optimization Methods for Determining the Pre-Storage Location and Pre-Setting the Distribution of Equipment Maintenance Materials［J］. Acta Armamentarii， 2022， 43（10）： 2668-2678.
13	李凯文，张涛，王锐，等. 基于深度强化学习的组合优化研究进展［J］. 自动化学报， 2021， 47（11）： 2521-2537.
	LI Kaiwen， ZHANG Tao， WANG Rui， et al. Research Reviews of Combinatorial Optimization Methods Based on Deep Reinforcement Learning［J］. Acta Automatica Sinica， 2021， 47（11）： 2521-2537.
14	周辉仁，唐万生，牛犇. 基于递阶遗传算法的一类多旅行商问题优化［J］. 系统工程与电子技术， 2009， 31（11）： 2630-2633.
	ZHOU Huiren， TANG Wansheng， NIU Ben. Optimization of Multiple Traveling Salesman Problem Based on Hierarchical Genetic Algorithm［J］. Systems Engineering and Electronics， 2009， 31（11）： 2630-2633.
15	师文喜，付艳云，赵学义，等. 基于多智能体的巡逻任务分配和路径优化方法研究［J］. 中国电子科学研究院学报， 2021， 16（7）： 633-638.
	SHI Wenxi， FU Yanyun， ZHAO Xueyi， et al. Research on Patrol Task Allocation and Path Optimization Based on Aulti-Agent［J］. Journal of China Academy of Electronics and Information Technology， 2021， 16（7）： 633-638.
16	赵良辉，邓飞其. 一种求解作业车间调度问题的混和遗传算法［J］. 系统工程与电子技术， 2007， 29（6）： 899-902.
	ZHAO Lianghui， DENG Feiqi. Heuristic Genetic Algorithm for Job Shop Scheduling Problem［J］. Systems Engineering and Electronics， 2007， 29（6）： 899-902.
17	于大腾，王华，孙福煜. 考虑潜在威胁区的航天器最优规避机动策略［J］. 航空学报， 2017， 38（1）： 281-289.
	YU Dateng， WANG Hua， SUN Fuyu. Optimal Evasive Maneuver Strategy with Potential Threatening Areabeing Considered［J］. Acta Aeronautica et Astronautica Sinica， 2017， 38（1）： 281-289.
18	赵星，吉康，申珂. 基于多旅行商问题的应急设施服务区划分模型［J］. 交通运输系统工程与信息， 2020， 20（5）： 205-211.
	ZHAO Xing， JI Kang， SHEN Ke. A Service Area Division Model for Emergency Facilities Based on Multiple Travelling Salesman Problem［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（5）： 205-211.
19	吴贝贝，李喆. 基于量子状态转移算法的作业车间调度问题［J］. 计算机应用与软件， 2021， 38（7）： 232-239.
	WU Beibei， LI Zhe. Job Shop Scheduling Problem Based on Quantum State Transition Algorithm［J］. Computer Applications and Software， 2021， 38（7）： 232-239.
20	马维宁，胡起伟，曹文斌，等. 考虑维修任务分配的装备选择性维修决策优化［J］. 系统工程与电子技术， 2023， 45（6）： 1902-1910.
	MA Weining， HU Qiwei， CAO Wenbin， et al. Equipment Selective Maintenance Decision Optimization Considering Maintenance Task Assignment［J］. Systems Engineering and Electronics， 2023， 45（6）： 1902-1910.

[1]	邱雄飞, 张桦, 赵润泽, 黄增端. 基于广义随机Petri网的装备战场抢修建模与分析[J]. 现代防御技术, 2024, 52(4): 130-136.
[2]	王帅, 王亚彬, 王金帼, 王茁, 赵建民. 陆军合成旅典型装备保障系统数字孪生模型[J]. 现代防御技术, 2023, 51(1): 96-106.
[3]	张耀龙, 阮拥军, 赵陆昊, 黄义松, 郭宇荣. 基于可拓云的合成旅装备保障能力评估方法研究[J]. 现代防御技术, 2023, 51(1): 86-95.
[4]	康警予, 刘晶, 陈忠, 郑振国, 王晖. 面向维和装备保障的模拟训练系统研究[J]. 现代防御技术, 2021, 49(1): 98-106.