基于Petri网的舰载机出库调度建模方法*

刘亚杰，李忠猛，谢 君

（海军工程大学，武汉 430033）

基于Petri网的舰载机出库调度建模方法*

刘亚杰，李忠猛，谢 君

（海军工程大学，武汉 430033）

舰载机出库作业调度效率是完成舰船作战效能的重要保证。分析了舰载机出库作业调度建模方法问题。基于Petri网技术理论，建立舰载机出库逻辑关系Petri网模型。基于机库内舰载机出库作业决策过程，建立舰载机出库作业四阶段决策的数学模型。最后给出优化算法流程并进行验证。

舰载机，调度，决策模型

0 引言

航母的绝大多数作战使命都需要舰载机来承担和完成，因此，舰载机的调度效率，对于提高航母的作战效能具有极其重要的作用。机库舰载机的出库调度问题实际是在路径安全的前提下，以最小的成本将调度需求目标飞机从机库当前位置牵引至升降机并移到飞行甲板上。事实上，由于机库布满舰载机，安全路径可能并不存在。在安全路径不存在的情况下，需要不断将该批次目标飞机附近的舰载机移出机库（为了描述方便，本文将这种现象称之为倒机），这将触发了一个新的调度问题，直到机库有足够的空间使目标飞机能安全通行为止。因此，调度方案是一批次飞机出库顺序的编排；最优调度方案则是合理的编排飞机出库顺序，使目标舰载机在最短的时间内调出机库。

国外过去对于舰载机调度的做法一般是通过摆放模型，以指导调度舰载机的甲板活动，如在美军航母上使用的“占卜板”［1］。近年来，一些航母上设置了飞行甲板通信系统，加强了飞行甲板各战位之间的相互联系。随着计算机技术的发展，国外开始将计算机应用于舰载机调度方面的辅助决策。Jeffery［2］等人设计了一种航母舰载机甲板持续监控系统，该系统结合了舰载机GPS定位，碰撞事故检测等功能，为提高舰载机甲板作业效率和减少事故起到了一定的积极作用。

国内杨炳恒［3］等以俄航母舰载机机库内调运作业为研究原型，创建了舰载机调运作业交通网络，文章没有研究舰载机出库调度优化问题。冯强［4］等将Multi-Agent技术应用到舰载机各甲板作业之间的协调，对调度方案的优化作用不大。刘钦辉［5］等研究的是飞行甲板舰载机的舰面调度问题。

求解最优的舰载机调度方案，首先应该选择合理而有效的出库调度建模方法。舰载机出库调度建模的前提条件是机库舰载机调运作业环境建模［6］以及对舰载机在机库内的调运作业进行路径规划［7］。笔者在文献［6-7］中已对调运问题的环境建模和路径规划问题进行了详述，本文不再赘述。

在环境建模和路径规划的基础上，本文首先建立了舰载机出库逻辑关系模型，并利用Petri网对其关系进行表达；其次通过分析舰载机出库作业调度计划的制定过程，建立了舰载机出库调度计划数学模型；最后给出舰载机出库调度优化算法流程并对其进行验证。

1 舰载机出库逻辑关系建模

机库舰载机出库调度问题属于典型的离散事件动态系统，对于离散事件动态系统的建模，Petri网已经证明是一个较为理想的工具。Petri网能够准确快速地反映系统实时调度的离散性与随机性，与其他方法相结合在调度问题中得到了广泛的应用［8-9］。

1.1 舰载机出库逻辑关系确立

已知机库内舰载机的布列形式，按照图1所示的舰载机出库调度逻辑关系算法流程图，确定机库中舰载机出库时的逻辑先后关系，并建立舰载机出库的优先级。设立舰载机出库优先级的目的是快速安排一批次舰载机的出库顺序问题，提高算法的收敛速度。

1.2 舰载机出库逻辑关系表达

舰载机出库逻辑关系确定后，需要对其进行正确合理的建模表达。依据Petri网离散事件动态系统建模理论，建立舰载机出库逻辑关系Petri网模型。以图2所示的法国“戴高乐”航母机库内舰载机的调运顺序求解为例。舰载机分别用英文大写字母A、B、C、D等表示，两部升降机分别命名为升降机1和升降机2。考虑升降机资源利用的均衡性，以防火分隔门为界，将机库分为两部分，分别记作机库I部和机库II部。

本文将Petri网技术中的赋时、随机性结合起来，应用TSPN（赋时随机Petri网）技术建立机库舰载机出库关系的Petri网模型，如图3所示。

库所pi∈P代表舰载机的位置，25架舰载机A、B、C、D、E、…、X、Y与库所是一一对应关系。

位置pSi∈P，i=1,2代表舰载机被牵引至升降机事件。

位置f0、f1表示对调运任务的判断分配，它瞬时保留到来的任务，根据di所联系的实施谓词或随机开关来决定到来的任务放入哪一个队列。

变迁属性T包括时间变迁和瞬时变迁两种，时间变迁用ti表示，ti∈T描述了舰载机牵引至升降机等可控事件，瞬时变迁用di表示，di∈T表示调运决策的执行。d0表示调运任务的并行执行；机库I部和机库II部的调运任务可并行执行，一个并行网模型结构由两个变迁来模拟，这两个变迁在相同的标识中可独立实施，一个变迁的实施不影响另一个变迁的实施。

1.3 Petri网模型的性能分析

1.3.1 可达性分析

可达树和矩阵方程是对Petri网模型进行可达性分析的两种方法［7］。由于可达树分析具有一定的局限性，本文以矩阵方程为基础对其可达性分析。

利用关联矩阵，对Petri网的可达性分析如下：

①按照一定的轨迹运行，系统所能到达的状态。

设初始标识为M0=［1 0 0 0 0 0 0 0 0 0 0 0］，求ti变迁被激发的标识M'，即p1位置的舰载机被牵引至升降机后，哪些位置的舰载机可以迁移。

这里T'=［1 0 0 0，0 0 0］，则

矩阵M'表示当ti变迁被激发后，位置p2、p3、p4的舰载机状态可达（即可以被迁移）。

②从某一状态出发，是否能够到达某一既定状态。

设初始标识为M0=［1 0 0 0 0 0 0 0 0 0 0 0］，判断M''=［0 1 0 0 0 0 1 0 0 0 0］否可达，求如下方程：

解得T''=［1-1 1 0 0 0 0］

这里T''为非负整数，表示M''不可达，即位置p2，p7的舰载机状态不可达（即前面有舰载机阻挡，需要进行倒机才可以调运出库）。

1.3.2 冲突与等待

由前面的分析已知出库调运Petri网模型中，由于升降机的数量是有限的，并且舰载机出库时互相阻挡，会造成资源及路径的冲突。解决这些冲突的方法是排定响应它们发出请求的顺序，即当冲突发生时，让其中的一个过程享有此共享资源，而其他发出此请求的过程按照某种规则进行等待，当享有共享资源的过程完成之后，就释放此共享资源，以响应下一个发出请求的过程，以此类推，就能够解决冲突的问题。

如图3所示，当位置p1的舰载机被调运至升降机后，位置p2、p3、p4的舰载机可以进行出库调运作业，但因为升降机资源有限，只能有一个位置的变迁被激发，这时按照某种规则，其他两个位置的舰载机就需要进行等待。

利用Petri网模型，求解舰载机的可达性问题和调运过程中发生的冲突、等待等问题，作为调度方案优化过程中排序和倒机决策的依据。

2 舰载机出库调度数学模型

一般意义下，舰载机出库需求批量表Q可以定义如下：

机库中存放的每一种型号的舰载机数量会大于或等于实际的需求量。根据需求信息Q表中的需求信息，在机库中调度舰载机会有多种选择。因此，需要根据舰载机出库需求信息表，制定舰载机出库作业调度的具体方案。舰载机出库作业调度方案的制定过程可分为4个阶段：第1阶段是根据需求量及机库内舰载机的资源信息，制定舰载机在机库内部调运数量的分配方案；第2阶段根据第1阶段制定的分配方案，选择出库舰载机；第3阶段对第2阶段选出的舰载机进行排序；第4阶段对排序的舰载机制定倒机方案，最后输出舰载机出库顺序。舰载机出库作业调度问题是一个四层决策问题，下层决策以上层决策为前提进行规划。每一层决策又可以归结为一个组合优化问题，在当前条件下，从各种可行方案中选择一个最优方案。如何对舰载机出库作业从整体上进行考虑，降低倒机次数，提高作业效率，是制定出库调度方案的主要任务。

2.1 出库舰载机数量分配模型

已知机库内舰载机资源信息和具体的调运需求，假设机库内配置两部升降机，建立出库舰载机数量分配模型如下：

其中各参数定义如下：

ni指Si型舰载机的需求量，n1i、n2i分别指Si型舰载机分配到机库I部、II部的需求数量；

N指批量需求表Q中舰载机总需求量，N1、N2分别指分配到机库I部、II部的舰载机需求量。

2.2 出库舰载机选择模型

确定机库I部和II部各型舰载机的具体分配数量后，出库舰载机的选择过程分为两步：

2.2.1 确定候选舰载机出库作业集合

定义需求表Q中需求舰载机规格相符合的舰载机为候选舰载机，用U表示候选舰载机的集合，其中U1，U2分别表示机库I部、机库II部候选舰载机的集合，u1ij，u2ij分别指机库I部、II部中与需求舰载机规格Si相符的舰载机集合，定义S（uij）为舰载机uij的规格。

其中，m1i、m2i分别表示机库I部、II部中规格为Si的舰载机数量。

2.2.2 选择出库舰载机

根据需求舰载机的数量，分别从U1、U2中选择出库舰载机，用V表示出库舰载机集合，其V1,V2分别为机库I部、II部的出库舰载机集合，则：

2.3 舰载机出库排序模型

一批次舰载机调运出库作业的逻辑性强，机库内舰载机状态随着出库作业过程的进行，不断发生变化。符合需求的舰载机集合确定后，处于杂乱无序的状态，因此，需要制定合理的舰载机出库作业次序。

定义机库I部、II部排序后的舰载机集合为：

2.4 舰载机倒机决策模型

由于机库内舰载机布列紧凑，根据调度需求，从机库中调运舰载机x1ij出库，如果该架舰载机不能直接调出，则首先需对阻挡其出路的舰载机进行调运作业，即进行包含调度x1ij以及由此产生的倒机作业的决策过程。

倒机作业应遵循倒机架次最少的原则进行，即寻找舰载机最佳的出库序列。对于排序后的舰载机集合X1、X2，根据Petri网模型及可达矩阵，即可求出X1、X2中需要倒机的舰载机，从而得出满足调运需求的舰载机出库集合。

定义机库I部、II部出库舰载机集合为：

2.5 舰载机出库作业目标函数

对于舰载机牵引移动部门来说，减少作业过程中的倒机次数，缩短调运作业行程，力求作业时间最短，以节约作业成本是其首要目标。定义F（Z）为完成舰载机出库方案时的最短作业时间，其中F1（Z1）、F2（Z2）分别为机库I部、机库II部舰载机完成出库方案的作业时间，机库I部、II部中调运时间最长的时间就是舰载机出库调运作业时间，即舰载机出库作业计划的目标函数表示为：

3 出库作业调度方案求解算法

根据建立的出库调度关系模型和出库调度计划数学模型，舰载机出库优化算法设计可分两步进行优化。

步骤1：利用相关决策知识理论实现舰载机数量分配功能。即已知调运需求信息Q，机库每个部分的机型、数量及其之间的逻辑关系等信息，求舰载机机型及出库数量在机库I和机库II的优化分配方案。

步骤2：采用遗传算法等智能算法对调运方案进行求解。

①实现舰载机选择功能。确定机库中出库舰载机可行解空间，生成初始种群，每个基因对应一架舰载机，每条染色体即是一个舰载机出库方案集合V。

②实现排序决策功能。根据优先级规则对V中舰载机出库作业进行排序，从而得到最优出库方案的舰载机调度序列X。

③实现舰载机倒机决策功能。根据舰载机之间的逻辑关系及其机库基本作业规则，基于Petri网的可达性，找出需要倒机的舰载机并根据一定规则进行整理得到舰载机出库集合Z。通过遗传算法对解空间进行遍历，目标函数值为调运所用时间最短，从而得到最优出库组合方案Z。

具体求解算法流程如下页图4所示。

4 应用案例

设定舰载机在机库中的一种布列方式，对舰载机出库方案的优化算法进行验证。

4.1 问题描述

该机库配备两部升降机，一道防火分隔门将机库分为两部分，记作机库I部，机库II部，机库I部、机库II部分别与升降机1，升降机2对应，即机库I部的舰载机通过升降机1调运至甲板，机库II部的舰载机通过升降机II调运至甲板。机库内拥有舰载机的机型为4种，共计26架。试验过程中设计4张不同的舰载机需求批量表Q1～Q4，每张批量表中包含4种机型的需求舰载机，舰载机数量分别为6、8、11、12。批量表中舰载机需求情况和各机型舰载机的在库数量如表1所示。

4.2 遗传算法参数设定

算法中设最大遗传代数Gen max=200，种群空间Pop max=50，变异率Pm=0.02，交叉率Pc=0.06。算法执行过程中，往往会在没有达到最大遗传代数的情况下得到最优解。为降低算法的执行时间，GA算法中设置一个阈值flag，flag表示每代种群个体的平均适应度值与当前最优适应度值的比值，如式（1）所示。

设定flag=0.9，如果flag值超过0.9，就可以认为截止到当前己经取得问题的全局最优解。

4.3 试验结果及分析

在算法运行过程中，优化算法表现出较好的收敛性，需求Q1～Q4的求解时间分别为12 s、13 s、15 s和16 s，满足实时性要求。图5为需求Q1的求解结果。

5 结束语

本文主要研究舰载机出库调度方案建模方法问题。首先基于Petri网技术理论，建立了舰载机出库逻辑关系Petri网模型。利用Petri网模型，可以求解舰载机的可达性问题和调运过程中发生的冲突、等待等问题，作为调度方案优化过程中排序和倒机决策的依据。然后通过对机库内舰载机出库作业决策过程进行分析，将舰载机出库调度过程抽象为四阶段决策过程，并建立了相应的数学模型。从保障调度工作效率的角度出发，以出库作业时间最短为优化目标，建立了出库作业调度作业目标函数。最后给出了舰载机出库优化算法流程，并进行求解验证。

［1］渔翁.美国航母航空部门的组织管理［J］.舰船知识，2006，17（9）：36-37.

［2］Jerrrey S.Feasibility Study of Global-positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Monitoring System［C］//Journal of Aircraft，2010：5-6.

［3］杨炳恒，毕玉泉，徐伟勤.一种舰载机调运作业流程优化模型［J］.舰船科学技术，2011,24（1）：118-121.

［4］冯强，曾声奎，康锐.基于MAS的舰载机动态调度模型［J］.航空学报，2009,21（11）：2109-2125.

［5］刘钦辉，邱长华，王能健.考虑空间约束的舰载机作业调度模型研究［J］.哈尔滨工程大学学报，2012,23（11）：1435-1439.

［6］刘亚杰，翁辉，陈晓山.一种基于“矢栅结合”的机库舰载机调运作业环境建模方法［J］.装甲兵工程学院学报，2014，28（2）：75-78.

［7］刘亚杰，李忠猛，陈晓山.考虑空间约束的机库舰载机调运路径规划方法［J］.海军工程大学学报，2014，26（3）：100-103.

［8］谢楠.基于Petri网的可重组制造系统建模、调度及控制方法研究［D］.上海：同济大学，2006.

［9］袁崇义.Petri网原理与应用［M］.北京：电子工业出版社，2005.

Method of Carrier-borne Aircrafts Exporting Scheduling Modeling Based on Petri Net

LIU Ya-jie，LI Zhong-meng，XIE Jun
（Naval University of Engineering，Wuhan 430033，China）

The carrier-borne aircrafts exporting scheduling is important for guaranteeing the battle performances.The method of carrier-borne aircrafts exporting scheduling modeling is analyzed.Based on the theory of Petri net，the Petri net model of exporting scheduling logical relations is established. Based on the decision process of exporting scheduling,the four-process-decision mathematical models are established.The flow optimization algorithm is given and validated.

carrier-borne aircrafts，operation scheduling，decision models

TP208

A

1002-0640（2015）09-0152-05

2014-08-09

2014-09-17

军队科研计划项目

刘亚杰（1975- ），女，辽宁朝阳人，博士，讲师。研究方向：复杂系统建模与仿真。