艦載機出動離場調(diào)度優(yōu)化算法

萬 兵, 韓 維, 梁 勇, 郭 放

(海軍航空大學, 山東 煙臺 264001)

0 引 言

航母是作為海上移動平臺遂行立體作戰(zhàn)任務的“巨無霸”,其制空、制海優(yōu)勢的發(fā)揮對艦載機空中力量的出動能力提出了高指標要求。這里的出動包含艦載機起降作業(yè)及空中任務等全作業(yè)周期,而從編隊攻防角度看,航母在艦載機放飛與回收時需調(diào)轉(zhuǎn)航向以提供飛機起降航向上所需的甲板風[1],此時段航母機動性及防御能力弱對起降時效性要求嚴苛,因此提高艦載機出動離場能力既可快速彌合此時防御盲點又同時增加飛機出動架次率進而增強空中作戰(zhàn)能力。而出動離場作業(yè)屬于任務規(guī)劃與資源調(diào)度優(yōu)化問題,且受到時間、空間、尾流間隔以及設備等復雜約束限制,如何快速生成不同任務驅(qū)動下離場調(diào)度優(yōu)化方案意義較大。

艦載機作業(yè)調(diào)度包括任務規(guī)劃、布列與調(diào)運(路徑規(guī)劃與跟蹤控制)、機-勤務保障(資源受限項目調(diào)度)、軍械轉(zhuǎn)運(供應鏈管理)、出動離場(車間調(diào)度問題)、回收排序(單機無緩存區(qū)調(diào)度問題)等階段優(yōu)化技術(shù)研究[2]。目前，單獨離場調(diào)度研究不多,但艦載機作業(yè)領(lǐng)域國內(nèi)外學者已開展大量工作。Ryan等[3-4]在無人機上艦背景下基于多智能體仿真技術(shù)開展艦載機甲板作業(yè)全周期仿真研究,采用混合整數(shù)規(guī)劃(mixed integer programming,MIP)模型抽象調(diào)度問題,并引入人-機交互將人工調(diào)度與MIP規(guī)劃算法進行融合完成艦載機作業(yè)調(diào)度與規(guī)劃,但對出動離場等單個環(huán)節(jié)的優(yōu)化顆粒度較粗。司維超等[5]基于粒子群優(yōu)化(particle swarm optimization,PSO)、遺傳算法(genetic algorithm,GA)等群體智能算法對甲板布列調(diào)度、出庫調(diào)度進行研究,基于多種群協(xié)作混沌智能算法進行出動調(diào)度研究。Liu等[6]開展路徑規(guī)劃與跟蹤控制研究。蘇析超等[7-8]基于人機匹配機務勤務保障及基于Memetic一體化保障調(diào)度,采用了遺傳算法的雙種群和局部鄰域改進策略進行優(yōu)化搜索。Wu等[9]基于任務分配與排序算法開展起降任務規(guī)劃方法研究。張智等[10]基于遺傳算法的艦載機甲板避碰規(guī)劃研究。上述學者對艦載機作業(yè)調(diào)度的研究多采用元啟發(fā)式智能搜索算法及改進算法,盡管算法有效,但群智能算法屬于黑箱變鄰域搜索技術(shù),對連續(xù)優(yōu)化問題效果顯著,而對混合整數(shù)規(guī)劃離散優(yōu)化問題,特別在其約束復雜情況下,此類算法缺點也較為突出,存在種群迭代過早收斂、優(yōu)化參數(shù)過于敏感導致適應性不強問題[11]。因此,針對傳統(tǒng)群體智能算法所存在不足,本文考慮采用約束規(guī)劃技術(shù)進行優(yōu)化研究。

約束規(guī)劃是源于人工智能社區(qū)的技術(shù),近年來,與運籌學優(yōu)化技術(shù)綜合運用來求解部分大規(guī)模離散優(yōu)化問題[12]。約束規(guī)劃是在實際優(yōu)化問題完成約束規(guī)劃建模后,將最小化目標函數(shù)進行約束化處理后,嵌入到約束滿足問題當中,爾后通過迭代求解該約束滿足問題,最終收斂到gap閾值內(nèi)的優(yōu)化迭代過程。目標約束化處理的初始值,需要啟發(fā)法來構(gòu)建,初始值的好壞將直接影響約束滿足問題的搜索求解效率,實際處理時初值主要由理論值來估算。該技術(shù)本質(zhì)上類似于分枝定界精確解法的樹搜索技術(shù),是對約束規(guī)劃模型的解空間的搜索,但有兩個重要的不同點:① 約束規(guī)劃模型基于數(shù)學約束、邏輯約束、集合約束等可直觀理解的復雜約束,有別于傳統(tǒng)的數(shù)學規(guī)劃模型;② 算法求解是目標約束化后的約束滿足問題的迭代優(yōu)化過程,約束傳播和領(lǐng)域縮減伴隨整個迭代過程和約束滿足的一致性檢查[13-14],最終使得約束規(guī)劃模型的解空間更緊,極大地裁剪掉無效搜索分枝。目前,針對大規(guī)模離散優(yōu)化問題特別是約束復雜條件下,約束規(guī)劃技術(shù)優(yōu)勢明顯,業(yè)內(nèi)已有不少成熟的約束規(guī)劃優(yōu)化器,比如IBM ILOG Cplex(商業(yè))、Google Ortools(開源)的優(yōu)化工具,比同型問題用數(shù)學規(guī)劃的求解效率提升非常多。國內(nèi)于2018年也推出了混合整數(shù)規(guī)劃優(yōu)化器,但針對是的數(shù)學規(guī)劃模型而非約束規(guī)劃問題。

本文在數(shù)學規(guī)劃模型基礎上開展約束規(guī)劃建模,借鑒現(xiàn)有約束規(guī)劃技術(shù)成果,提出約束規(guī)劃二分法迭代算法+單機約束引導啟發(fā)式搜索算法來求解出動離場調(diào)度優(yōu)化問題,最后進行實例仿真與算法分析,比較本算法與傳統(tǒng)啟發(fā)式算法性能,探求本算法的在線規(guī)劃調(diào)度能力,分析研究起飛位使用情況與出動效能的關(guān)系。

1 艦載機出動離場作業(yè)描述

艦載機起降作業(yè)過程包括出動與回收,從上次飛行活動結(jié)束或一個新的飛行周期開始。通常包括以下過程:① 出動任務規(guī)劃;② 戰(zhàn)斗布列與保障;③ 滑行調(diào)運;④ 起飛位選擇與出動離場;⑤ 回收排序與進近著艦;⑥ 回收系停。而出動作離場作業(yè)為本文研究內(nèi)容,是艦載機起降作業(yè)的關(guān)鍵一環(huán),其出動效能高低將直接影響航母整體作戰(zhàn)能力[15-17]。這里,出動效能主要由出動離場作業(yè)調(diào)度優(yōu)化來體現(xiàn),因此求解該調(diào)度優(yōu)化問題是核心。出動離場作業(yè)流程為:在已知布列并完成機務勤務保障情況下,先后進行起飛位分配、停機位滑行到起飛位準備位、排序等待、起飛前檢查、彈射出動離場,單機出動離場過程如圖1所示。而艦載機出動通常是完成多機編隊的起飛調(diào)度,單機符合圖1流程,但是對機隊出動而言,調(diào)度問題可由圖2所示的網(wǎng)絡圖來表述,屬于一個經(jīng)典的柔性作業(yè)車間調(diào)度問題(flexible jop-shop scheduling problem,FJSP)。當然由于甲板作業(yè)的復雜特性,出動調(diào)度優(yōu)化還應考慮空間約束、避碰、飛機尾流間隔等約束。

圖1 單機出動離場工序及作業(yè)環(huán)節(jié)Fig.1 Sortie departure process and operation link of single aircraft

圖2中FJSP描述:工序1,停機位出動準備(開始-虛工序);工序2,起飛位分配及滑行入位;工序3,偏流板冷卻(等待);工序4,起飛前檢查;工序5,起飛出動;工序6,飛機離場(結(jié)束-虛工序)。其中,工序1為虛工序,待出動飛機所處的停機位數(shù)量即為機器數(shù),共有pn1臺機器;工序2～4為串行工序,均有ptn2個機器;工序5雖有rtn2條起飛跑道,但考慮到起飛安全1次僅能起飛1架飛機,即為1臺機器;工序6同樣為虛工序,共1臺機器。例如,對于有3個起飛位彈射出動的某航母,離場調(diào)度問題則是解決n架飛機完成起飛位分配、出動排序、按序保障、離場。為研究方便,將起飛飛機間的安全尾流間隔納入到離場這個工序當中。

圖2 出動離場作業(yè)網(wǎng)絡圖Fig.2 Network diagram of sortie departure operation

2 出動離場模型

出動離場調(diào)度問題影響因素較多,為簡化抽象成FJSP模型方便相關(guān)研究,作如下合理假設:① 出動過程穩(wěn)定不中斷;② 出動飛機已完成保障并系泊于相應初始停機位;③ 甲板滑行選擇路徑庫中最優(yōu)路徑,忽略甲板滑行中避碰防止的等待時間(由于滑行避碰相讓時間極短,可以通過調(diào)整滑行速度來調(diào)節(jié)),時間相對較為固定;④ 起飛位的彈射準備的作業(yè)時間由飛機類型決定,同型飛機準備時間相同。

2.1 參數(shù)定義

i:飛機編號,i∈N={1,2,…,n};

j:飛機工序號,j∈Ti,Ti為飛機i工序集;

k:工序j加工機器號,k∈Mj,Mj為工序j的加工機器集,且有∪Mj=M;

TRp,2(t):飛機p在工序2(滑行段)的實時路線,避碰檢查;

(1)

式中：(im,in)∈Ejk表示第j工序時在機器k上的連續(xù)兩架作業(yè)飛機。

(2)

作業(yè)開始、完成時間與0～1變量關(guān)系如下:

(3)

(4)

式中:Sti, j、Cti, j分別為飛機i第j工序的具體作業(yè)開始時間、結(jié)束時間；NaN為非數(shù)。

2.2 混合整數(shù)規(guī)劃模型

(5)

s.t.

(6)

(7)

(8)

(9)

(10)

(11)

(12)

j=6,?k∈M6,(ip,iq)∈E6k

(13)

(14)

在MIP中,目標函數(shù)為離場作業(yè)時長最大值的最小化。式(6)表示為任意飛機和工序同時只能在一臺機器作業(yè);式(7)表示任意工序上每臺機器,每次只能至多加工1架飛機;式(8)為飛機在機器上加工時間約束;式(9)為同一飛機前后工序開始與完工時間要求;式(10)為同一機器前后飛機加工優(yōu)先約束,式中H為大正數(shù)確保約束始終成立;式(11)為起飛離場過程機器選擇約束,起飛位確定后相應操作工序機器也隨之被確定;式(12)表示離場升空工序的安全約束要求,同時只能放飛1架飛機;式(13)表示工序6中前后兩架起飛飛機的安全離艦間隔(尾流安全),其中ΛT表示相鄰起飛飛機的最小間隔時間；式(14)為甲板滑行段飛機在空間防碰撞安全約束要求,工序2中任意時刻兩機位置滿足飛機p的軌跡TRp,2(t)和飛機q之間的距離TRq,2(t)大于等于最小間隔距離Dsafe。

2.3 約束規(guī)劃模型

目前多數(shù)學者主要思路,是基于數(shù)學規(guī)劃創(chuàng)建艦載機出動離場調(diào)度的混合整數(shù)規(guī)劃模型,采用精確解法或智能算法等求解。實際出動離場的約束問題遠比傳統(tǒng)數(shù)學約束要復雜,除常規(guī)數(shù)學約束外,還有析取約束、合取約束、邏輯約束、一元約束等。當然數(shù)學規(guī)劃與約束規(guī)劃兩者是等價的,只是從模型建立與約束表達來講,約束規(guī)劃建模更為簡潔、精煉且更體現(xiàn)實際問題邏輯表達。約束規(guī)劃模型在上述整數(shù)規(guī)劃模型基礎上進行調(diào)整建立。

2.3.1 決策變量

(1) 間隔變量1(飛機作業(yè))

(2) 間隔變量2(機器作業(yè))

(3) 序列變量

Sequenc mchs(k,t,o): mps(k,t,o)|k,表示對第k臺機器,其序列變量mchs(k,t,o)是對間隔變量mps(k,t,o)的一個排序。其他符號見第2.1節(jié)。

2.3.2 目標函數(shù)

(15)

式中：endOf(ops(i,j,o))為間隔變量完工時間。

2.3.3 約束條件

(1) 同一架飛機作業(yè)工序的前后時序約束

當元組o1=、o2=為相同飛機i的相關(guān)數(shù)據(jù),且滿足o1的下一個工序是o2的工序時,那么時間間隔變量ops[o1]完工后方可啟動ops[o2],約束表示為

endBeforeStart(ops[o1],ops[o2])

(16)

(2) 可選機器約束

出動作業(yè)時,飛機某一工序可由不同機器完成,飛機作業(yè)的間隔變量可從可選機器作業(yè)變量中任選其一進行調(diào)度設計。元組O=表示飛機作業(yè)數(shù)據(jù),元組m=表示機器作業(yè)數(shù)據(jù),約束表示為

alternative(ops[O]|IFm.o==O.o)←mps[m],
?O∈{Ops},?m∈{Mps}

(17)

式中：條件m.o==O.o,表示飛機作業(yè)數(shù)據(jù)中與機器作業(yè)數(shù)據(jù)中任務數(shù)相同情況;alternative為從mps[m]可選集中選定值賦予ops[O]。

(3) 關(guān)聯(lián)機器約束

出動時,飛機i滑行、等待位、起飛前檢查、出動等工序在滑行工序確定起飛位(某機器)后,該飛機后續(xù)工序機器要求也確定,約束表示為

?i∈N,?c∈{Continuities},?m01,m02,m03∈{Mps}

(18)

式中:元組c={Continuities},表示某飛機i執(zhí)行滑行、等待位、起飛前檢查等工序所選擇的機器具有連續(xù)關(guān)聯(lián)性，如圖3示,機器連續(xù)關(guān)聯(lián)的元組集{Continuities}可表示為{, , }。該約束表示機器作業(yè)元組m01,m02,m03如果滿足作業(yè)任務連續(xù)且作業(yè)機器連續(xù)時,那么以上三元組所對應的機器作業(yè)間隔變量(presenceOf)將同時出現(xiàn)。

圖3 出動各工序間機器關(guān)聯(lián)關(guān)系圖Fig.3 Association diagram of machines among each processduring sortieing

(4) 交疊約束

同一機器作業(yè)任務前后時序無交疊,約束表示為

noOverlap(mchs[k]),?k∈M

(19)

式中：mchs[k]為第k臺機器作業(yè)的排序,是對該機器作業(yè)間隔變量mps(k′,t′,o′)|IFk′==k的編排,最后要確保各間隔相互無交疊。

(5) 甲板滑行防碰撞約束

調(diào)度設計過程中,飛機滑行、等待、出動等過程中安全間隔的檢查,滿足最小間隔距離Dsafe,同式(14)。

綜合式(15)～式(19),便是對第2.2節(jié)中數(shù)學規(guī)劃模型的調(diào)整為約束規(guī)劃模型。建模過程更加注重對實際調(diào)度問題的描述,貼合人們思維習慣。

3 求解算法的給出

本文將出動離場調(diào)度問題抽象為一個FJSP模型,但同時應考慮滑行階段各飛機的路徑設計與碰撞防止問題。因此,出動離場這個FJSP問題涉及到不同生產(chǎn)線的空間干涉約束,使得求解變得更加困難。而現(xiàn)實調(diào)度中既要考慮解的最優(yōu)性又要兼顧求解的時效性,必須設計出快速有效的算法。對于FJSP問題,多采用群體智能算法，如PSO算法、雙種群GA(double population GA, DPGA)、差分進化(differential evolution, DE)算法、蜂群算法等，也有基于MIP的分枝定界等精確求解算法，本文采用約束規(guī)劃算法進行求解。

為方便問題研究,該約束規(guī)劃模型簡寫為

minimizez=g(ops(i,j.o))

(20)

(21)

決策變量:間隔變量ops,mps及各機器作業(yè)序列變量mchs。

3.1 約束引導啟發(fā)式算法(算法1)

混合車間調(diào)度問題通過階段任務分配、單機調(diào)度設計兩個階段迭代優(yōu)化完成,任務分配結(jié)合第3.2節(jié)算法作以說明,單機調(diào)度設計則由約束引導啟發(fā)式搜索算法完成。單機調(diào)度是調(diào)度領(lǐng)域中經(jīng)典、基礎的作業(yè)方式。單機調(diào)度利用約束滿足算法[13],求解最大完工時間(makespanCmax)使得滿足小于或等于給定截止時間要求。該算法要求每臺機器對其分配任務進行操作排列,使得調(diào)度方案滿足時間窗約束及模型其他約束。

3.1.1 進行初始化操作

對每個作業(yè)進行編排以確定其在每臺機器上的最早可能開始時間和最晚可能完成時間。在所有的時間窗已經(jīng)編排好后,在每臺機器上所有操作的時間窗互相之間進行比較。當任意給定機器的兩個作業(yè)時間窗沒有交疊時(滿足一臺機器同時只能進行一種作業(yè)任務的約束),這兩個作業(yè)時間窗的先后關(guān)系可以增加到約束規(guī)模型中,即:在任何可行調(diào)度方案中,具有更早時間窗的作業(yè)任務必須早于這個后續(xù)時間窗的作業(yè)。實際上,優(yōu)先關(guān)系在時間窗有交疊時也可以推理出來。在當前先后優(yōu)化約束集合中,由S′ki(S″ki)表示作業(yè)(k,i)最早(最晚)可能的開始時間,C′ki(C″ki)表示作業(yè)(k,i)最早(最晚)可能的完成時間。這里,作業(yè)(k,i)最早可能開始時間S′ki視為該作業(yè)在實際開始時間,記為rki;而作業(yè)最晚可能完成時間C″ki視為該作業(yè)在實際交貨時間,記為dki。那么,在機器k上作業(yè)(k,i)與(k,j)之間的作業(yè)間隔松弛間隙可以表示為

(22)

式中:作業(yè)(k,i), (k,j)表示機器k上加工任務i,j,k∈{Machines},i,j∈{Operations};rki表示作業(yè)(k,i)的現(xiàn)場開始時間;dki表示作業(yè)(k,j)的現(xiàn)場的交貨時間。

圖4詳細說明了以上幾個表達式時間含義,其中作業(yè)(k,i) 先于(k,j),圖中情況i)任務作業(yè)時間窗則表示前兩式,情況ii)則表示最后一式。如果δ(k, i)→(k, j)<0,那么在圖4中的任務優(yōu)先約束情況下不存在可行的調(diào)度方案,說明此時作業(yè)(k,j)先于(k,i)。在程序初始化階段,所有作業(yè)時間窗(也稱為間隔變量)兩兩之間相互比較,所有隱含的作業(yè)優(yōu)先級關(guān)系將插入到析取圖中。因為這些新增的優(yōu)先級約束,每個作業(yè)的時間窗將會再次調(diào)整,或者說更加緊湊(即δ(k, i)→(k, j)將進一步壓縮),這里將包含對每個任務作業(yè)的開始與交貨時間進行重新編排。

圖4 同一機器前后任務作業(yè)間隔松弛間隙示意圖Fig.4 Schematic diagram of slack clearance between task operation inteval before and after the same machine

約束規(guī)劃采用的是約束滿足技術(shù),主要依靠約束傳播算法[18]。做法是插入新的優(yōu)先級約束(析取弧),而這個優(yōu)先級約束隱含在之前插入的優(yōu)先約束和調(diào)度問題的原始約束中。由于新優(yōu)先級的插入,約束滿足算法重新計算各作業(yè)的時間窗。而對于每對在同一機器上處理作業(yè)任務,編排中可能存在以下4種情況。

情形 1δ(k,i)→(k, j)≥0&&δ(k, j)→(k,i)<0,優(yōu)先級約束為任務(k,i)→(k,j),表先后關(guān)系;

情形 2δ(k,j)→(k, i)≥0&&δ(k, i)→(k,j)<0,優(yōu)先級約束為任務(k,j)→(k,i);

情形 3δ(k,i)→(k, j)<0&&δ(k, j)→(k,i)<0,排列中不存在這種調(diào)度方案;

情形 4δ(k,i)→(k, j)≥0&&δ(k, j)→(k,i)≥0,任務(k,i)→(k,j)或(k,j)→(k,i)均可,即二者無先后優(yōu)先級要求。

3.1.2 調(diào)度設計編排規(guī)則

(1) 對于滿足情形4的一對作業(yè)(任意排列均可)編排。如果出現(xiàn)多于1對滿足情形4的任務對,那么需要采用搜索啟發(fā)法進行編排。直接推理啟發(fā)策略為:任務對的選擇是基于該任務對所提供的排列靈活度進行的,具有最低靈活度的任務對則被選中。如果具有低靈活度的任務之前未調(diào)度好,那么在后面的編排中可能出現(xiàn)該任務對無法完成調(diào)度,所以低靈活度的任務對要比高靈活度的任務對優(yōu)先編排。這里,靈活度依賴任務對(k,i)→(k,j)或(k,j)→(k,i)排列方案的松弛間隙大小。綜上考慮,一種較為有效的任務對排序靈活度的評估策略可以是任務對排列的松弛間隙的均衡化處理:

(23)

式中：P((k,i),(k,j))為該任務對排序靈活度。

由式(23)知,如果任務對的松弛間隙最大值較大,則會拉高其排序靈活度,總體調(diào)度方案的編排優(yōu)先級會延后。在P((k,i),(k,j))最低排序靈活度的任務對選中后,那么具有更大的松弛間隙的任務優(yōu)先級則確定該任務對前后優(yōu)先順序,即δ(k, i)→(k, j)≥δ(k, j)→(k, i)?任務(k,i)優(yōu)先于(k,j)。

(2) 對于滿足情形3的一對作業(yè)的編排。當發(fā)生該情形時,調(diào)度方案將不能完成構(gòu)建,算法需要回溯，即之前完成迭代計算的一個或多個排序決策將被取消;或者說,當前采用這種方式提出和構(gòu)建的調(diào)度問題的解不存在,而且原問題部分約束還需要做進一步的松弛。

3.1.3 約束引導啟發(fā)式(算法1)過程

步驟 1搜索初始化。

步驟 2計算每個未排序(調(diào)度編排)的任務對的松弛間隙,δ(k, i)→(k, j)和δ(k, j)→(k, i)。

步驟 3檢查優(yōu)先級約束條件,對需要排序(調(diào)度編排)的決策變量(任務對及其松弛間隙)進行分類。如果任意決策變量滿足情形1或情形2,則進入步驟 4;如果任意決策變量滿足情形3,則進行回溯;否則進入步驟 5。

步驟 4插入新的優(yōu)先級約束,并進入步驟 2。

步驟 5如果沒有決策變量屬于情形4,則已找到調(diào)度可行解,算法1停止;否則進入步驟 6。

步驟 6對尚未排序(調(diào)度編排)的每個任務對進行排序靈活度P((k,i),(k,j))計算。選擇minimumP((k,i),(k,j))的任務對,如果δ(k, i)→(k, j)≤δ(k, j)→(k, i),則任務(k,i)優(yōu)先于(k,j);否則,任務(k,j)先于(k,i)。結(jié)束后返回步驟 4。

3.2 二分法算法迭代優(yōu)化約束規(guī)劃

約束規(guī)劃問題的求解,是基于約束滿足問題進行的。將目標函數(shù)最優(yōu)值設定上界后,轉(zhuǎn)化為約束條件并增加到模型約束當中,該FJSP問題的算法流程如下。

由圖3及式(17)和式(20)可知,任務分配集有衍生約束，即工序、機器任務分配關(guān)系：

(24)

工序任務集Nj分配給該工序下可選機器完成，即機器任務分配一致性關(guān)聯(lián)：

(25)

機器所分配任務具有前后關(guān)聯(lián)關(guān)系,如分配機器1的任務與后續(xù)分配給機器4、機器7有前后約束關(guān)系。

設置目標函數(shù)下界L=z*=Cmakespan,Cmakespan為已知的一個目標下界(可以估計,其值的好壞直接影響算法效率),設置目標值上界U=Cmax(一個大常數(shù)),目標函數(shù)上下界中點值M=(L+U)/2。

步驟 2啟動二分法搜索優(yōu)化。取k=1,新增約束g(ops(i,j.o))=g(mps(k,t.o))

步驟 3機器任務集分配。如果k≤3,采用Monte Carlo模擬從機器k的可選任務集N1中生成任務集nk(見式(24))。此時,設置N1=N1-nk;如果3

步驟 4單機任務調(diào)度優(yōu)化設計。對機器k所分配的任務集,生成一個操作序列,進行約束一致性檢查(進行約束傳播和領(lǐng)域縮減),使得調(diào)度方案滿足約束式(21)要求。單機任務調(diào)度由約束引導啟發(fā)算法完成,見算法1。完成該機器的任務分配與調(diào)度設計。

步驟 4.1如有可行解,機器k執(zhí)行最后一個任務,zk=g(ops(i,j.o))=endOf(mps(k,t,o))(完成時間)。如果z*≤zk,則z*←zk;否則,z*←z*。

設置k=k+1,如果k≤10,返回步驟 3;否則,將新的上界設置為M,新上界記為U*=M,下界保持不變,新的中點M*=(L+U*)/2,二分法搜索進入步驟 5。

步驟 4.2如果無可行解,同新的下界設置為L*=M,上界保持不變,那么新的中點M*=(L*+U)/2,二分法搜索進入步驟 5。

步驟 5算法結(jié)束判定。當U*-L*>gap時,將M*值返回步驟 2,重新進行任務分配和調(diào)度設計;當U*-L*≤gap,算法停止。gap值為迭代計算時,目標函數(shù)的上下界值差。

說明二分法搜索在下界較優(yōu)時效率很高,因為證明約束滿足問題無可行解所需要的計算時間比較長,而找到約束滿足問題的可行解相對簡單。

4 仿真分析

4.1 仿真初始條件

圖5 某型航母甲板概況圖Fig.5 Overview of an aircraft carrier deck

本文仿真采用Matlab2018a+ILOG Cplex混合編程求解,運行環(huán)境Win10操作系統(tǒng),Intel(R) i7-4790U CPU@3.6 GHZ處理器,內(nèi)存8 GB。

4.2 算例實現(xiàn)與結(jié)果分析

圖6為某一甲板態(tài)勢下,選擇8、12、18架飛機進行出動離場調(diào)度的算法仿真,左側(cè)部分為飛機作業(yè)甘特圖,如圖6(a)所示，8架飛機中縱軸為各飛機編號,不同顏色塊標定不同作業(yè)階段(或工序),色塊中編號代表機器號進行相應作業(yè)階段加工,如M2-1對應縱軸第2架飛機表示該飛機第1階段在機器2上處理,而其色塊位置及跨度為起止時間,其他類推。右側(cè)部分為機器作業(yè)甘特圖,如圖6(b)所示縱軸為加工機器號,不同顏色塊由暗到亮依次表示不同飛機編號,色塊編號則代表飛機的不同作業(yè)階段,如J8-2對應縱軸機器6表示第8架飛機的第2個階段在該機器上加工,同樣色塊位置及跨度代表起止時間和加工時間,其他類推。從圖6中可以看出，各子圖中的作業(yè)調(diào)度完成滿足模型約束條件,各階段及機器作業(yè)之間互斥兼容,不存在沖突情況,即給出方案完全可行,算法可以較好地解決離場調(diào)度設計。

圖7是約束規(guī)劃算法對不同出動規(guī)模的迭代計算過程,算法終止是結(jié)合gap值和約束滿足檢查次數(shù)進行的。橫坐標是對迭代次數(shù)的抽樣,縱軸為目標值,迭代目標值的更新策略是迭代中找到更好的滿足解時進行,圖7中各標星點為不同規(guī)模出動調(diào)度的約束滿足解,并在標星點處記錄其計算時刻,標識了算法收斂時間,及算法終止時間,計算中相關(guān)仿真結(jié)果如表1所示。從圖7可以看出,算法對不同出動規(guī)模的最終收斂時間隨著規(guī)模的增加而增大,依次為0.1 s、0.33 s、0.44 s,并呈現(xiàn)線性變化趨勢。此外,不同規(guī)模算例的迭代結(jié)束時間也基本相當且小于1 s,即便不考慮其收斂點時間,算法的實時性較好。通過對初始數(shù)據(jù)各進行30次仿真，其結(jié)果均相同,說明算法較為穩(wěn)定且較好地適應不同規(guī)模的調(diào)度計算。但如果不從最終收斂時間看,而調(diào)高gap閾值,僅關(guān)注目標值逼近到近似最優(yōu)點,即圖7中3條曲線0.05～0.06 s處“肘部”大轉(zhuǎn)彎處結(jié)果。也就是說此時,算法對不同出動規(guī)模的調(diào)度計算在該“肘部”時間基本同時找到了近似最優(yōu)解,而這個時間約為0.06 s。因此,如果退而求其次,當實際問題調(diào)度實時性要求高而僅需近似解,可以看出本文算法效率可滿足要求,更重要的是對不同規(guī)模離場調(diào)度所需時間基本相同,而第4.3節(jié)將分析本文算法與其他經(jīng)典方法的比較。

圖7 不同出動規(guī)模下算法迭代收斂曲線Fig.7 Algorithm iteration convergence curves under different sortie scales

表1 不同規(guī)模飛機的出動調(diào)度仿真結(jié)果

而表1則列出算法對不同規(guī)模飛機的出動調(diào)度有關(guān)指標,算法性能在圖7中作了闡述,其目標值分別為348 s、463 s及638 s,平均出動時間隨出動規(guī)模的增加而減少,平均出動效率為35～44 s/架之間,這也基本符合實際出動情況,10.5 min內(nèi)可將18架飛機在機務勤務保障完畢情況下完成放飛(而美國“尼米茲”級航母使用4個彈射位出動架次率約為28～30 s/架)。

實驗數(shù)據(jù)是經(jīng)合理化假定的,實際作業(yè)調(diào)度則可根據(jù)經(jīng)驗值進行修正,泛化到一般場景應用實現(xiàn)實時調(diào)度規(guī)劃。仿真實驗是基于作業(yè)時間確定、機器無故障且在給定離場數(shù)據(jù)進行任務規(guī)劃,然而實際情況是作業(yè)時間具有隨機性,機器可能故障,甲板滑行時可能因避碰檢查帶來的沖突隱患導致作業(yè)等待延遲。但是本文所設計算法依然有效,原因如下:一是針對實際作業(yè)不確定性問題,通過經(jīng)驗數(shù)據(jù)得到保守的期望作業(yè)時間,以此作為算法處理數(shù)據(jù),并提供不同作業(yè)策略以適應不確定性[19],比如：① 調(diào)高期望作業(yè)時間來適應由海況環(huán)境變化導致甲板作業(yè)效率降低；② 在可能發(fā)生延遲時增加作業(yè)人力及配套設備給機器加工提速，進而彌補調(diào)度計劃的作業(yè)偏差；③ 不可避免狀況時整體向后偏移作業(yè)進程。二是針對機器故障發(fā)生時,若短時無法恢復,可捕獲待調(diào)度信息啟動算法的實時間重調(diào)度。

艦載機保障、出動、回收作業(yè)等各環(huán)節(jié)通常有明顯分段特性,全周期作業(yè)優(yōu)化可由各環(huán)節(jié)優(yōu)化之累加,因此孤立分析出動離場的優(yōu)化調(diào)度對現(xiàn)實意義明顯。

4.3 約束規(guī)劃算法與經(jīng)典算法的比較

針對調(diào)度問題,文獻[5，7]給出了PSO、DLGA、DE等群體智能搜索算法,本文采樣這些方法開展第4.1節(jié)算例條件下的仿真實驗,初始化設置采取完全隨機化與輪盤賭結(jié)合方式進行,種群規(guī)模為50,代數(shù)為500、100、500,參數(shù)設置:PSO中慣性權(quán)重0.9,加速因子(2,2);DPGA與DE算法中交叉與變異率均為0.1,仿真實驗各做了30次,隨機抽取各算法中的一次迭代收斂結(jié)果如圖8所示。上述實驗與本文算法結(jié)果性能比較如表2所示。圖8給出的是出動規(guī)模為8架飛機時最優(yōu)調(diào)度的迭代收斂曲線(其他情況類似),圖8(a)中PSO算法經(jīng)過較少迭代后便收斂,但算法隨機性較大,最佳解獲取為隨機得到,該解相關(guān)信息并不能影響后續(xù)種群搜索,其最佳解獲取之后的后續(xù)解質(zhì)量較差;DPGA是種群整體演進優(yōu)化,圖8(b)中經(jīng)過較少迭代后算法收斂,且算法后續(xù)種群總體上呈現(xiàn)收緊趨勢,但是遺傳機制無法解釋該收斂值為全局最優(yōu),其實也是引言中談到的算法早熟性(收斂快)，容易限入局部最優(yōu);DE算法是GA的變種,圖8(c)中算法經(jīng)過較多的迭代后方才收斂,總體趨勢是一個較為穩(wěn)定的目標值收緊過程。顯然上述智能算法同樣也能較好解決調(diào)度優(yōu)化問題,但實驗中發(fā)現(xiàn),上述方法在不同仿真實驗結(jié)果往往會有差異、最佳目標值出現(xiàn)攝動,即算法的穩(wěn)定性方面不夠,或者說“最優(yōu)”解的質(zhì)量不足。

算法出動規(guī)模/架最小收斂時間/s算法平均時間/s最佳目標/s平均最佳目標/s本文80.100.88348348.00120.240.89463465.46180.360.93638639.74PSO85.8214.22348349.241210.0223.09463464.181812.9836.74646647.92DE810.9426.93348349.941210.2739.38468468.431812.1856.37644647.59DPGA810.4559.86348350.121213.5680.56473474.621824.68120.26649650.38

而表2中則給出了多次實驗后上述方法與本文算法的區(qū)別比較,主要從收斂時間、算法平均時間、目標值波動等指標分析。單獨從收斂時間看,本文算法遠遠優(yōu)于智能算法,比DPGA或DE算法約提高近2個量級;而從算法平均時間看,本文算法同樣也遠好于上述智能搜索算法。各算法目標結(jié)果均具有一定的抖動,在小規(guī)模出動時目標值相對穩(wěn)定,但隨規(guī)模增大,智能算法的最佳目標值攝動更顯著。盡管DPGA收斂的迭代次數(shù)比較少,但是最小收斂時間相比其他算法時間要多,各算法綜合性能排序為本文fPSOfDEfDPGA。但是假如實際優(yōu)化問題實時性計算要求較高時,要求在短時提供最佳解,即減少最大搜索迭代次數(shù),那么此時PSO算法未必能好于DE算法,原因是算法穩(wěn)定性方面不夠好、隨機性大。而DPGA效果因為雙種群規(guī)模增大了搜索復雜度,降低了算法效率。

4.4 模型靈敏度分析

艦載機起降作業(yè)受航母甲板有限空間約束,所裝配的彈射器和起飛位數(shù)量對于機群出動離場效率具有較大影響[20]。在本文規(guī)劃模型和約束規(guī)劃算法分析和仿真基礎上,研究不同可用起飛位對不同規(guī)模飛機出動效率的影響規(guī)律。下面將對1～3個起飛位可用的情況下,不同規(guī)模飛機的平均出動時間進行計算(出動效率)。

(1) 1個起飛位可用的情況分析

航母有3個起飛位,分別假設只有C1或C2或C3起飛位可用情況下,計算不同規(guī)模飛機出動的平均時間。為確保計算結(jié)果的準確性,相同規(guī)模飛機出動時間計算,取不少于10種不同停機位飛機的出動組合方案求其均值作為該出動規(guī)模下的出動時間。那么可得到只有1個起飛位可用的情況下,出動1～12架飛機的平均出動時間變化情況如圖9示。

圖9 一個起飛位可用時平均出動時間與出動規(guī)模關(guān)系Fig.9 Relationship between average sortie time and sortie scale when one takeoff position is available

可以看出,相對而言C1和C3起飛位可用時,平均出動時間在4架處為最小,往后稍有增多;C2起飛位則隨出動規(guī)模的增大而減少。因此,只有一個起飛位可用時,需要盡可能確保C2可用,然后是C1和C3。

(2) 2個及3個起飛位可用的情況分析

2個、3個起飛位可用時分析同上。當2個可用時,有C1與C2,C1與C3,C2與C3 3種組合,同上方法,那么1～12架飛機的平均出動時間變化情況如圖10示?？梢钥闯?出動規(guī)模超過4架以上時,其平均出動時間基本保持在50～65 s之間,C1、C2及C2、C3這兩組均與C2的組合出動效率相當,優(yōu)于C1、C3的組合。因此,C2起飛位非常關(guān)鍵,起到拉低平均出動時間作用,保持其功能完好對提高出動效能意義重大。而3個起飛位均可用時,第4.2節(jié)中已給出仿真分析,這里不贅述。

圖10 兩個起飛位可用時平均出動時間與出動規(guī)模關(guān)系Fig.10 Relationship betwween average sortie time and sortie scale when two takeoff positions are available

綜上分析,基于彈射起飛的出動離場調(diào)度優(yōu)化問題,在起飛位不能同時使用情況下,合理使用C2起飛位并確保其性能完好對出動效率的提升意義重大。僅使用一個起飛位時,C1、C3起飛位對出動效率貢獻性能相當,但是C2起飛位效果理想;有兩個起飛位時,出動效率隨出動規(guī)模增加到6架以上時將穩(wěn)定在60 s/架左右。本文研究的是彈射起飛模式,相較于俄“庫茲涅佐夫”的滑躍起飛,出動效率在相同出動情況下可以提升約20 s/架。

5 結(jié) 論

本文對艦載機出動離場問題抽象成FJSP模型來進行調(diào)度優(yōu)化研究。一是模型建立。在傳統(tǒng)數(shù)學規(guī)劃模型的基礎上進行適當調(diào)整,引入易于直觀理解的調(diào)度邏輯約束和時間間隔決策變量,建立了對應的約束規(guī)劃模型。二是約束規(guī)劃模型算法。運用調(diào)度分解技術(shù)將調(diào)度問題劃分為多個單機調(diào)度的組合優(yōu)化問題,最終通過約束規(guī)劃的二分法迭代算法完成優(yōu)化問題收斂,而將其單機調(diào)度為任務分配和調(diào)度設計兩個階段完成,任務分配由Monte Carlo模擬生成,調(diào)度設計則由約束引導啟發(fā)式搜索算法完成。三是對比實例仿真分析。將約束規(guī)劃算法與傳統(tǒng)群體智能算法比較分析發(fā)現(xiàn),在本文所研究的中小規(guī)模調(diào)度優(yōu)化問題中,前者算法效率比后者提升約2個數(shù)量級。當然，由于約束規(guī)劃其實也利用類似分枝定界的樹搜索算法,最大的改進是利用約束傳播和領(lǐng)域縮減技術(shù)極大減少搜索空間,通過對不同出動規(guī)模的仿真發(fā)現(xiàn),算法效率非常高且隨著規(guī)模的增加算法時間呈線性增長趨勢,當然規(guī)模的增加成超大型規(guī)模后算法時間將會出現(xiàn)爆炸式增長,而這不屬于本文研究范圍。因現(xiàn)實的出動離場問題均屬于中小型復雜約束問題,要求的就是實效性及在線規(guī)劃性能,那么從這點來講,約束規(guī)劃便能很好地解決此類問題。四是對3個起飛位可用情況進行對比分析。起飛位使用越多出動效率越高,僅1個起飛位可用時,C2效能最高,C1、C3相當,出動時間約100 s/架;僅2個起飛位可用時,含C2組合的效能較高,C1和C3組合效能較差,出動時間約60 s/架;當3個起飛位均使用時,平均出動效率約為40 s/架。因此,C2起飛位對出動效能的貢獻度最大,實際使用時應盡可能最大程度確保其可用性、可靠性。此外,出動效率隨出動規(guī)模的增多而增大,但一定規(guī)模后趨緩或少量降低。