艦載機模塊化彈藥調度方案優化設計

呂曉峰, 楊東澤, 馬 羚

(海軍航空大學岸防兵學院, 山東 煙臺 264001)

0 引 言

隨著軍事裝備的不斷發展,戰場形勢瞬息萬變,戰場的打擊目標與打擊方式也可能會隨之改變,原有固定的彈藥型號很有可能無法滿足實際的作戰任務需求。若將艦載機彈藥進行模塊化設計,每個模塊具備統一的對外接口但功能并不一致,在戰時便可根據實際情況進行組裝[1]。例如美軍的GBU-15(V)滑翔制導航空炸彈由導引頭、戰斗部和尾部組件3部分組成,可裝配通用爆破型、侵徹爆破型和集束型3種戰斗部,并且可裝配紅外制導型和電視制導型兩種導引頭,戰時可根據不同任務進行組合[2]。如今模塊化技術快速發展,已從部分組件的模塊化設計向全模塊化轉變,即從同一系列不同型號間導引頭和戰斗部的換裝到戰時根據實際戰場情況與作戰需求選擇相應的模塊進行組裝[3],不僅可以橫向互換,更能縱向組合[4]。隨著該技術的發展,艦載機彈藥對于模塊化的需求日益凸顯,基于作戰使用的考慮,使用模塊化彈藥時貯運,保障部門能夠依據任務靈活配置相應類型的艦載機彈藥,讓艦載機更好地應對作戰目標;基于貯存運輸的考慮,進行模塊化之后,彈藥存放更加靈活,在相同容積的艙室能夠容納更多的彈藥。

在艦載機的各項保障任務中,艦載機彈藥的保障耗時最長[5],目前對于艦載機彈藥調度研究大部分都是面向傳統整彈調度,對于模塊化彈藥調度研究很少。對于彈藥整體調度,馬登武等[6]和張洪亮等[7]建立了以調度結束時間最小化為優化目標的艦載機彈藥調度模型,但是其研究對象相較于模塊化調度流程并不相同:一是模塊化調度需將各模塊進行裝配,增加了裝配環節;二是一個彈藥分為多個模塊,調度對象呈倍數增加,原有的編碼方式已完全不適用;三是約束條件較傳統保障更加復雜,在調度時須保證裝配區不會發生囤積彈藥模塊的情況,對各模塊的調度次序提出了要求。

雖然目前對彈藥模塊調度問題研究很少,但其與多工序的配件調度問題有一定的相似之處,可將彈藥各個模塊看作配件,并且其多個調度流程可看作多個工序,將參與各個模塊調度的艙室、升降機和裝配線看作機器。對于模塊化彈藥調度問題,存在同一個工序有多個機器可以調度的情況,比如某個模塊在多個艙室內存儲,可以由多個艙室進行提供,所以需選擇艙室,并且需要計算各模塊的調度順序,是作業車間調度問題(job shop scheduling problem, JSP)的延伸,屬于柔性JSP(flexible JSP,FJSP)[8],JSP中每個工序只能由一個機器進行加工,不涉及選擇機器的問題。Wang等[9]建立了以最大模糊時間最小化為優化目標的模糊柔性作業車間調度模型,并通過遺傳算法求解。Xu等[10]和Yin等[11]等將任務完成時間最小化為目標函數,使用多層編碼遺傳算法對模型進行求解。Chou等[12]建立以最小化最大任務完成時間為優化目標的配件組裝調度模型,提出使用改進灰狼優化算法求解問題。通過對以上文獻分析,模塊化彈藥調度相較于工廠工件調度問題,情況有所差異,對于約束條件,不只是各個模塊機器選擇和調度順序的問題,同時還涉及最后各模塊裝配的情況,在裝配環節多個模塊需進行組裝,模塊數量發生變化造成變量變化,在裝配區不能堆積過多模塊。對于優化目標,結合本文研究對象,在建立任務完成時間最小化的優化目標之外,還需考慮各升降機和各艙室平均工作時間,若不考慮該目標函數,則可能致使某個升降機被頻繁使用,從而導致該升降機發生故障的概率增大,對于艦載機彈藥調度,若某個升降機發生故障,則會造成該升降機對應的通道發生癱瘓。

相較于傳統艦載機彈藥調度問題,本文對多層編碼進行優化以解決調度對象的數量和工序增加的問題,同時結合實際保障要求對模型進行約束。相較于工廠工件調度問題,增加艙室和升降機平均工作時間最小化為優化目標,避免出現調度工作分配不均衡的問題,同時通過改進編碼方式解決變量變化的問題。隨著智能算法的不斷發展,近年來眾多學者采用遺傳算法[13-16]、粒子群算法[17-19]、蟻群算法[20-22]、細菌覓食算法[23]、博弈算法[24-25]、鄰域搜索算法[26-27]、禁忌搜索算法[28-29]、啟發式算法[30]等求解FJSP。其中，遺傳算法優秀的全局尋優能力和較強的魯棒性使其成為處理全局問題的最佳算法之一[31]。

基于以上分析,本文以任務完成時間最小化和艙室與升降機平均工作時間最小化為優化目標,結合研究對象設立約束條件,根據所建立的模型優化多層編碼方式,每層代表含義不同,便可以用一個染色體表示復雜問題的解,運用遺傳算法求解問題,最后對實際問題進行驗證仿真,表明算法的可行性。

1 模塊化彈藥調度問題描述及數學模型

1.1 問題描述

根據相關文獻[2-3,32],美軍福特號航母上的模塊化彈藥調度流程如圖1所示,相較于傳統的整彈貯運模式增加了裝配環節,共有3個調度流程,并且可將庫內轉運、垂直轉運和裝配視作3個工序,調度流程如下:

(1) 庫內轉運:任務相關艙室工作人員收到下達的保障方案,按照任務指示要求準備彈藥相關模塊,送至升降機阱口;

(2) 垂直轉運:相關模塊由艙室工作人員送入升降機阱口后,由垂直轉運戰位的操作人員控制武器升降機,將其送至水平轉運裝配室;

(3) 轉運裝配室裝配:彈藥模塊由升降機送至轉運裝配室后,將各模塊暫存放于裝配準備區,裝配工作人員在此進行部件安裝及模塊對接。

圖1 模塊化彈藥調度流程圖Fig.1 Modular ammunition scheduling flow chart

1.2 模塊化彈藥調度模型建立

根據模塊化彈藥調度流程,其任務的完成主要包括模塊的轉運和裝配。假設有a個艙室,有b個升降機,裝配室中有m個裝配線,最終需要n枚完整的彈藥,一枚彈藥分為c個模塊。為了降低調度工作的復雜度,同時減少裝配區模塊的堆積,這里采用逐枚彈藥進行調度的方案。對于某枚彈藥各模塊的調度工作可描述為：首先，c個模塊在a個艙室完成庫內轉運,為第一道工序;其次，c個模塊通過運用b個升降機轉運至裝配室,為第二道工序;最后，c個模塊在m個裝配線中選擇其中一個進行裝配,為第三個工序。

問題的求解包括兩個方面,其一是為模塊選擇合適的艙室、升降機和裝配線,其二是確定高效的工序順序以及各個工序的起始時間,需要多枚模塊化彈藥的任務時使得整個調度工作最快完成,并且得到的調度方案合理,在模型中首先提出以下假設:

一個裝配線一次只能裝配一枚彈藥；在單枚彈藥的所有模塊調度至裝配區之后再進行裝配；不同模塊在進行同一個工序時沒有優先級；模塊選擇的升降機處于空閑狀態時,在該模塊完成庫內轉運之后立即進行升降機轉運。

(1)

(2)

(3)

在進行彈藥調度時,首先須提高任務完成的效率,即要求任務完成時間最短,根據式(2)得到彈藥調度的首要目標函數為

(4)

在保障任務完成速度的同時須使分配到各個站位的任務均衡,這樣既使得調度工作更加合理,同時不會使某個升降機相較其他升降機使用頻率過高,導致其故障率升高,因此建立次要目標函數為

(5)

在選擇方案時首先比較各個方案的首要目標函數值,優先選擇首要目標函數值低的方案,若首要目標函數值相同,則比較次要目標函數值,再選擇次要目標函數值低的方案。

結合實際情況,為使模型能夠得到合理的調度工作分配方案,對模型設置約束條件如下:

(6)

(7)

xekf≤aekf, ?e,k,f

(8)

(9)

(10)

其中，將3個工序的艙室、升降機和裝配線統稱為機器。

約束條件中的公式和對模塊的工序順序進行約束,使每個模塊按照正確的工序順序進行調度和裝配;公式和對模塊的工序機器進行約束,使得各個模塊的每個工序只能被分配到可選機器中的一臺;公式對工序的結束時間進行約束。

綜上,模塊化彈藥調度的目標函數與約束條件如下:

(11)

2 算法設計

2.1 編碼方案

根據本文模型,染色體的編碼方式采用整數編碼的方式,同時在編碼時需體現當前模塊所屬的彈藥序號、當前模塊的調運進程以及所選擇的機器。為解決保障對象數量變化帶來的變量變化的問題,并且需保證模塊工序選擇與機器選擇的編碼維度相同,將模塊組裝工序對應的編碼置零以表示多個模塊合為一個整體的過程,而以往常用的編碼方式并不能實現此結果。改進后的編碼方式將染色體的編碼分為3層,第1層為目前模塊所屬的彈藥序號,第2層為所有模塊在各個機器上的調度順序,第3層表示模塊每個工序選擇的機器。如染色體[1 2 1 2 3 1 3 0 2 3 6 1 7 5 9]所示,該染色體的第1位表示當前調度的是第1枚彈藥,第2位至第8位表示的是各個模塊的調度順序,依次是模塊2的庫內轉運→模塊1的庫內轉運→模塊2的垂直轉運→模塊3的庫內轉運→模塊1的垂直轉運→模塊3的垂直轉運→3個模塊的裝配,由于在裝配階段所有模塊都需參與,3個模塊合為一個整體,所以這里用0表示,第9位至第15位表示執行相應轉運工作的機器序列,依次是艙室2→艙室3→升降機6→艙室1→升降機7→升降機5→裝配線9。

具體實現過程如下:生成的染色體長度為2×(c×(d-1)+1)+1的整數串,其中c為模塊個數,d為調度的工序數量。第1層數值是根據當前彈藥序號生成,第2層模塊序列的生成是隨機生成的,每生成一個數值對應的模塊調運次數就減少一次,直至第2層的編碼完成,根據第2層的模塊序列,第3層隨機生成可轉運的機器序號。

2.2 適應度值

適應度函數是評價方案優劣的標準,一般情況下會將目標函數的值轉化為對應染色體的適應度值,結合本文建立的模塊化調度模型,基于彈藥調度任務完成時間與各機器平均工作時間得到適應度函數的計算公式如下:

fitness(i)=T1

(12)

fitness(F2)=T2

(13)

根據形成的染色體計算兩個適應度函數值,在進行最優解的更新時需判斷兩個適應度函數值,若第1個適應度值更小則該染色體對應的方案更優,在第1個適應度值相同的情況下比較第2個適應度值。

2.3 選擇操作

本文在選擇較好的染色體時采用輪盤賭選擇法,即適應度值比例法,其中個體選擇概率如下所示:

Fitness(i)=1/fitness(i)

(14)

式中:pi(i)表示染色體i在每次選擇中被選中的概率。由于第1個目標函數是本文模型的首要目標函數,被選中的概率依據第1個適應度函數。輪盤賭法在選擇個體時首先會參考上一代個體的適應度值,讓適應度值大的個體有更大概率能被選擇作為父代個體來生成新個體。

2.4 交叉操作

交叉操作是染色體進化的主要操作之一,通過父代染色體之間的交叉操作獲得下一代新的染色體。根據本文的編碼形式,采用整數交叉法,首先在種群中隨機選擇兩個染色體作為父代染色體,并將染色體的第2層和第3層抽取出來,對兩個染色體的第2層進行交叉,其次隨機選擇交叉位置進行交叉，如圖2所示。具體方法如下:若隨機生成的交叉位置為3,則將父代染色體從起始位置至交叉位置進行交叉。

圖2 染色體交叉示意圖Fig.2 Chromosome crossing diagram

染色體交叉之后會出現某些模塊的工序會發生變化,比如染色體1中的模塊2相較于交叉之前多了一道工序,而模塊3相較于交叉之前少了一道工序,由于染色體2是與染色體1發生的交叉,染色體2的變化情況正好與染色體1相反。針對交叉后發生的變化需要做出調整,同時根據變化后的工序將其機器調整為交叉前的機器,如圖3所示。

圖3 染色體調整示意圖Fig.3 Chromosome adjustment diagram

2.5 變異操作

種群通過變異操作對染色體的局部基因值做變動獲得新的個體,增加種群的多樣性,從而使得整個種群向前進化。在進行變異操作時,首先從種群中隨機選取一個變異個體;其次隨機生成兩個變異位置pos1和pos2;最后將染色體pos1和pos2位置的模塊及其對應的機器進行調換,產生新的染色體,假設生成的交叉位置為3和5,如圖4所示。

圖4 染色體變異示意圖Fig.4 Chromosome variation diagram

2.6 算法步驟

算法流程圖如圖5所示。

圖5 算法流程圖Fig.5 Algorithm flow chart

步驟 1設定遺傳算法基本參數,種群數目、最大遺傳代數、交叉率和變異率。

步驟 2根據調度模型產生初始種群。

步驟 3根據式(12)計算初代適應度值。

步驟 4運用輪盤賭法選擇染色體。

步驟 5按照交叉概率選擇染色體,并產生交叉片段進行兩兩交叉,同時對交叉后不符合實際的染色體進行補缺。

步驟 6進行變異操作。

步驟 7若達到最大遺傳代數轉步驟8,否則轉步驟4。

步驟 8輸出最優解。

3 案例分析

本文采用多層編碼遺傳算法求解模塊化彈藥調度問題,假設一枚彈藥分為3個模塊,庫內轉運與升降機調度分別有4臺機器,每個模塊都需經過庫內轉運與升降機調度兩個流程,最后3個模塊一起進行裝配,裝配時根據各個裝配線狀態選擇裝配線,最終需裝配3枚完整的彈藥。各個模塊在進行各階段調度工作時可選擇的機器如表1所示,其中庫內轉運的1～4號表示4個艙室,升降機調度的5～8號表示4個升降機。第1行第2列的數據為[1,3],表示模塊1的庫內轉運階段可選擇的艙室有1號艙室和3號艙室。第3行第3列的數據為[6,8],表示模塊3的升降機調度階段可選擇的升降機有6號升降機和8號升降機。

表1 工序可選機器表

模塊各個階段工作對應的機器調度時間如表2所示,第1行第2列的數據為[3,4],表示模塊1選擇1號艙室進行庫內轉運時轉運時間為3 min,模塊1選擇3號艙室進行庫內轉運時轉運時間為4 min。第2行第3列的數據為[7,8],表示模塊2選擇5號升降機進行升降機調度時需要時間為7 min,模塊2選擇6號升降機調度時需要時間為8 min。

表2 各機器調度時間

算法的基本參數設置如下:種群數目設為50;最大遺傳代數為50;交叉概率為0.8;變異概率為0.6,各彈藥調度完成時的種群適應度值變化如圖6～圖8所示,分別表示3枚彈藥的調度方案求解時適應度值的變化與種群均值的變化。經過50次迭代,計算第1枚彈藥調度方案的種群適應度值穩定在20 min,種群均值在23 min左右；計算第2枚彈藥調度方案的種群適應度值穩定在27 min,種群均值在30 min左右；計算第3枚彈藥調度方案的種群適應度值穩定在33 min,種群均值在37 min左右。

圖6 第1枚彈藥種群適應度值變化Fig.6 Changes in population fitness value of the first ammunition

圖7 第2枚彈藥種群適應度值變化Fig.7 Changes in population fitness value of the second ammunition

圖8 第3枚彈藥種群適應度值變化Fig.8 Changes in population fitness value of the third ammunition

圖9為模塊化彈藥在轉運和裝配時的甘特圖。通過對甘特圖中每個單元起點和終點的驗證,發現各單元之間不存在重疊的情況,并且次序正確,所得方案可行,表明改進的多層編碼遺傳算法解決模塊化彈藥調度問題具備可行性。

圖9 模塊化彈藥調度甘特圖Fig.9 Modular ammunition scheduling Gantt chart

圖9中的4位數字表示當前調度工作的具體信息,如1011編碼中第1位數字“1”表示當前進行的是第1枚彈藥的調度工作,第2位和第3位數字“01”表示1號模塊,第4位數字“1”表示當前進行的是第1道工序。因此，1011編碼代表的完整含義是當前正在進行第1枚彈藥中1號模塊的第1道工序,即庫內轉運工作,再結合甘特圖縱坐標,該工序在3號艙室進行。同理，2032編碼表示當前正在進行第2枚彈藥中3號模塊的第2道工序,即升降機調度工作,再結合甘特圖縱坐標,該工序在4號升降機進行。3003編碼表示當前正在進行第3枚彈藥的第3道工序,即3個模塊的裝配工作,由于裝配工作是3個模塊一起參與的,故編碼的第2位和第3位數字都用“0”表示,再結合甘特圖縱坐標,該工序是在9號裝配線進行的。

4 結 論

本文針對艦載機模塊化彈藥調度問題,建立了多模塊、多工序的艦載機模塊化彈藥調度模型,主要結論如下:

(1) 針對艦載機模塊化彈藥調度完成時間問題,提出了遞推法計算任務完成時間。

(2) 運用基于多層編碼的遺傳算法計算以任務完成時間最小化和各艙室與升降機平均工作時間最小化為優化目標的調度方案,并結合本文研究對象在裝配工作中數量的變化對多層編碼進行改進,用以完整地表達各階段模塊的狀態。

(3) 對建立的模型與改進后的算法進行Matlab仿真,驗證本文方法的可行性。