变邻域搜索分布估计算法求解舰载机保障作业调度问题  

On the Carrier-Based Aircraft Deck Operation Scheduling Problem Solved by Variable Neighborhood Search-Based Estimation of Distribution Algorithm

作　　者：刘翱[1,2] LIU Ao(School of Management,Wuhan University of Science and Technology,Wuhan 430065;Center for Service Science and Engineering,Wuhan University of Science and Technology,Wuhan 430065)

机构地区：[1]武汉科技大学管理学院,武汉430065 [2]武汉科技大学服务科学与工程研究中心,武汉430065

出　　处：《系统科学与数学》2024年第2期391-407,共17页Journal of Systems Science and Mathematical Sciences

基　　金：教育部人文社会科学研究规划基金项目(21YJAZH050)资助课题。

摘　　要：针对多资源、多约束的资源受限舰载机保障作业调度问题,提出了一种求解该问题的基于变邻域搜索的分布估计算法.首先,建立了考虑站位、设备、作业的优先级和安全性等约束的调度模型,该模型以舰载机保障作业的总完成时间和舰载机移动次数的加权和最小化为目标;其次,结合问题特征分析,提出了最早可用设备规则,对偶站位交换规则等两类启发式规则,定义了基于序置换排列的解的编码方式;再次,提出了分布估计算法(EDA)的概率分布更新模型,以及基于工序插入、交换、反转等邻域操作的变邻域搜索策略,设计了基于变邻域搜索的分布估计算法(EDAVNS);最后,基于单波次8架舰载机保障的仿真结果,验证了所提模型对舰载机保障作业调度问题具有较好的实用性.同时,基于5个不同规模的问题集的分析结果表明:与分布估计算法、变邻域搜索、遗传算法、以及只使用插入、交换、反转等单一邻域操作的EDA算法相比,EDAVNS均取得了最优的结果,验证了EDAVNS能有效地求解该问题,并较好地平衡全局探索与局部搜索.In this paper,a variable neighborhood search-based estimation of distribution algorithm is proposed to solve the carrier-based aircraft deck operation scheduling problem,which is a kind of resource constrained scheduling problem involving both multi resources and multi constraints.Firstly,a scheduling model is established by considering the constraints of station,equipment,operation priority and safety,and the objective of the model is to minimize the weighted sum of the deck operation’s makespan and the carrier-based aircraft’s moving numbers.Secondly,according to the analysis of problem characteristics,two kinds of heuristic rules,namely the earliest available device rule and the dual station exchange rule,are proposed,and the permutation sequence-based solution encoding scheme is defined.Thirdly,a novel probability distribution update model of the estimation of distribution algorithm(EDA)is designed by combining with the solution encoding scheme,and the variable neighborhood search strategy is designed based on the neighborhood operations such as insert,swap and inverse of the deck operations,and then the variable neighborhood search-based estimation of distribution algorithm(EDAVNS)is proposed.Finally,the simulation results based on a single wave turn of eight carrierbased aircrafts show that the proposed model has good practicability for carrier-based aircraft deck operation scheduling problem.Meanwhile,the analysis results based on five different scale problem sets indicate that EDAVNS achieves the optimal results compared with the estimation of distribution algorithm,variable neighborhood search and genetic algorithm,the EDA variants with single insert,swap and inverse neighborhood operation,which demonstrates that EDAVNS can not only solve this problem effectively,but also can well balance global exploration and local exploitation.

关 键 词：调度问题 保障作业 分布估计算法 变邻域搜索 

分 类 号：E926.392[军事—军事装备学] TP18[兵器科学与技术—武器系统与运用工程]