基于遺傳算法的軍工電子柔性車間動態調度研究

肖玉曼 湯旭東

摘 ?要：文章對軍工電子柔性車間的動態調度問題進行了研究，運用改進遺傳算法求解軍工電子柔性車間的調度問題。結合軍工電子產品的特點，建立了基于項目權重的多目標數學模型，運用改進的遺傳算法進行模型求解。該改進算法運用了雙層染色體的編碼方式及POX的交叉方式，并采用基于事件驅動的重新調度策略。最后，運用實例證明了該研究方法的可行性及有效性。

關鍵詞：遺傳算法;FJSP;動態調度;軍工電子;項目權重評價

中圖分類號：TP181 ? ? ? 文獻標識碼：A文章編號：2096-4706（2022）05-0152-05

Research on Dynamic Scheduling of Military Electronic Flexible Job-Shop Based on Genetic Algorithm

XIAO Yuman， TANG Xudong

（The 26th Institute of China Electronics Technology Group Corporation， Chongqing ?400060， China）

Abstract： In this paper， the dynamic scheduling problem of military electronics flexible job-shop is studied， and the improved genetic algorithm is used to solve the scheduling problem of military electronics flexible job-shop. Combined with the characteristics of military electronic products， a multi-objective mathematical model based on project weight is established， and the improved genetic algorithm is used to carry out model solving. The improved algorithm uses double-layer chromosome coding mode and POX crossover mode， and adopts rescheduling strategy based on event-driven. Finally， the feasibility and effectiveness of the research method are proved by examples.

Keywords： genetic algorithm; FJSP; dynamic scheduling; military electronics; evaluation of project weight

0 ?引 ?言

在當前風云變幻的國際形勢下，我國軍用電子元器件、組件模塊國產化進程明顯加快，軍工電子領域普遍呈現訂貨數量激增的態勢。面對市場需求激增的情況，軍工企業除了需增加投入生產資源、擴大產能，還需通過科學的方法提升生產效率。生產排程優化就是其中一個突破點。

1 ?軍工電子項目生產排產現狀

目前軍工電子產品已呈現出集成化、模塊化的發展趨勢，其主要特點是多品種、小批量、柔性作業、不確定性較多，而軍工行業很多還是采用的傳統的生產計劃制定方式，如人工制定甘特圖、網絡計劃圖等。傳統的生產計劃方式很難達到多任務情況下的最佳的排產效果，同時費時費人力，這樣就會造成生產效率低下，浪費生產資源，增加生產成本等。如多個項目在計劃編制過程中，生產調度運用傳統的計劃編制模式，對資源兼顧不足，顧此失彼，會給資源調配增加難度，也會造成計劃編制的不合理及頻繁調整。

2 ?智能算法在FJSP問題方面的研究

近年來，通過智能算法解決柔性車間調度問題（FJSP問題）已得到廣泛研究，可以提高生產效率，提高企業的市場競爭力[1]。FJSP問題在求解時會同時考慮工件排序和機器選擇兩個子問題，從而使作業車間調度問題更加符合真實車間情況。解決FJSP問題的常用方法有禁忌搜索法（taboo search， TS），遺傳算法（genetic algorithm， GA）和粒子群優化（particle swarm optimization， PSO）等[2-4]。其中遺傳算法在車間調度問題的研究中應用最廣。本文借鑒前輩學者的理論研究經驗，結合軍工電子行業產品的特點，對項目進行評價確認項目權重，建立多目標FJSP動態調度問題的應用研究。

3 ?FJSP動態調度問題的數學模型

FJSP問題簡單地說可表述為n個工件在m臺機器上的加工，各工件工序加工順序和工序在各機器上的加工時間已知，求解各工件的加工順序和所使用的機器，使某些期望值達到最優。本文研究的優化目標是項目的總完工時間最小和總拖期時間最小。同時結合了緊急插單的動態事件發生后的重調度策略。

3.1 ?模型符號

數學模型涉及的符號意義如表1所示。

3.2 ?目標函數

最小化最大完工時間：

最小化總拖期時間：

3.3 ?約束條件

FJSP問題要滿足的約束條件分為兩大類：工件約束和機器約束。具體約束條件為：

（1）工件的當前工序必須在上一道工序結束后才能開始：

Cij≤Si（j+1）

（2）任何一個工件的一道工序在同一時刻只能夠被一臺可選機器加工：

（3）一臺機器只能同時加工一個工件的一道工序：

Cij×xijh≤Skl×xklh，Sij≤Skl，xijh=1，xklh=1

Ckl×xklh≤Sij×xijh，Sij≥Skl，xijh=1，xklh=1

（4）工件的工序一旦開始就不能被打斷：

Cij×xijh=Sij×xijh+Oijh

3.4 ?項目權重評價

軍工電子產品由于其行業背景的特點，在進行項目重要度評價時，評價因素與普通電子產品有所區別。主要會考慮項目的重要程度、風險程度以及成本效益因素。這三類評價影響因素又可以進一步細分，具體如圖1所示。

圖1 ?項目權重影響因素

（1）各影響因素的權重計算。各影響因素的權重計算可采用AHP層次分析法[5]，通過專家評分，由各項目所屬專業領域的專家及資深主管組成專家組，對各層級的影響因素進行兩兩比較，對各專家給出的標度取平均值，對影響因素進行權重計算，即可得出各影響因素的權重。

（2）評分標準。項目在進行評價打分時，參照的評分標準如表2所示。

每個評價因素評分從0～10分，由專家評分得出。將各影響因素平均評分與影響因素權重相乘后，即可得出項目的權重值。

4 ?遺傳算法求解FJSP動態調度問題

4.1 ?染色體編碼

運用遺傳算法解決問題的關鍵就是編碼和解碼。對于FJSP問題，工件要同時選擇較優的加工順序和較優的加工設備或人力資源（本文統一表示為機器），所以本文采用雙層編碼方式進行編碼[6]，一個調度方案由2層染色體組成，具體含義如圖2所示。

工序編碼：染色體長度等于所有工件的工序總數，直接用工件編號作為編碼基因，工件編號出現的次數為該工件的工序數，Pij表示第i個工件的第j道工序。機器編碼染色體如圖3所示。

機器編碼：染色體長度同工序總數，每一個基因用機器編號直接編碼，與第一層編碼相對應。每個基因位的機器編號應屬于第一層對應工件的工序可用機器集合。

本文采用兩階段的方式產生初始種群，首先隨機產生工序編碼染色體，其次根據各工件各工序可用機器集合隨機產生機器編碼染色體。

4.2 ?選擇交叉和變異

選擇的目的就是遵循適者生存的原則，將高質量的父代遺傳給子代[1]。本文是多目標函數，兩個目標函數都是求解最小值，故將兩個目標函數的加權求和的倒數作為原個體適應度值。選擇采用輪盤賭選擇法，即由各個適應度的值在總體適應度的比率確定。

由于染色體編碼采用包括工序編碼和機器編碼的雙層遺傳編碼方式，機器編碼是對應工序編碼生成的，故先針對工序編碼采用POX的交叉方式[6]，機器編碼對應的位置進行交叉互換，以避免非法解的產生。交叉的操作如圖4所示。

圖4 ?POX交叉操作

變異操作先是在工序編碼段的基因隨機選取兩點進行交換，而機器編碼段相應位置的基因也跟著一起交換，因工序基因的交換改變了工件的工序信息，故有可能會使得機器編碼段產生非法解，針對非法解則根據機器約束條件設置的罰函數使其淘汰。

4.3 ?動態優化策略

動態車間調度問題普遍的研究方向分為基于事件驅動和周期驅動的重新調度策略[7]，結合柔性車間發生動態事件的常見情況，本文采用基于事件驅動的策略，也就是在動態事件發生的時刻對還未開始的工序進行重調度。根據軍工項目的特點，動態事件主要包括項目交貨期調整、緊急插單、項目暫?；蛉∠?。

當動態事件發生時，存在以下兩種約束：

一是工件的初始時間：

T-Ji=max（Ci（ji-1），NewT）

Ji為工件i需要重新調度的第一道工序的原工序編號;Ci（ji-1）為工件i需重調度工序的上一道工序的完工時間;NewT則為動態事件發生的時間。

二是機器的初始時間：

T-Mh=max（Ch，NewT）

h為當前機器的編號，且1≤h≤m;Ch為機器h當前工序的結束時間;NewT為動態事件發生的時間。

當動態事件發生時，根據約束條件定位到需重調度的工件工序信息。然后初始化需重調度的工件數，初始化各工件剩余工序加工時間集合，初始化各工序可選機器集合，初始化各工件交貨期。即Oi1=OiJi，Oi2=Oi（Ji+1），…，Oi（gi-Ji+1）=Oigi，Mi1=MiJi，Mi2=Mi（Ji+1），…，Mi（gi-Ji+1）=Migi;d1=d1-NewT，d2=d2-NewT，…，di=di-NewT。然后對當前所有還未開始的工件工序進行重調度。當出現交貨期變更，則只需要調整目標函數中對應的交貨期變量。當出現項目暫?；蛉∠麜r，則將該項目的未開始工序從待排產工序中去除。

5 ?FJSP動態調度在軍工電子項目中的應用

下面以某軍工電子模塊、組件生產線為例，進行某時間段生產任務的動態調度優化。該生產線為典型的柔性作業方式，部分工序關鍵靠人工作業（如手工焊、調試等），部分工序則主要依靠設備（如自動貼片、平行封焊、激光封焊等）。且存在多能工情況，故將各工序關鍵資源設定為人員或設備。初始排產涉及的項目有5項，用編號1～5表示，如遇到項目產品數量較多時，可拆單，將其視為幾個單獨的項目。項目的工序數和可用資源集合信息如表3所示。項目各工序加工工時和交貨期如表4所示。

5.1 ?項目權重評估

在進行項目排產前，先請項目專業版塊的專家、設計師、工藝人員、項目主管、質量主管就圖1中的項目權重影響因素進行兩兩比較，通過AHP法得出各影響因素如表5所示。

然后由專家組對項目按3.4節所述評分標準進行評價打分，得出5個項目的各影響因素評價得分平均值如表6所示。

綜上，將各項目影響因素得分與影響因素權重相乘求和，得到各項目權重如表7所示。

5.2 ?MATLAB仿真運算

針對以上5個項目的情況，運用遺傳算法進行MATLAB仿真運算，軟件版本為MATLAB R2018a，運行參數為：種群大小nchr=100，最大迭代次數G=500，交叉概率Pc=0.8，變異概率Pm=0.1。目標函數F1的權重為0.3，目標函數F2的權重為0.7。

仿真運算結果得到的最優方案對應的甘特圖展示如圖5所示，最小總拖期時間值為5 596.67，最小總完工時間為2 015。

當出現插單情況時，觸發重調度機制，對截止到當前時間的未完項目工序及新增項目進行重調度。本案例插入訂單時間為500 min時，插入訂單權重得分為6.360 542 08，訂單其他信息如表8所示。

此時，根據前最優調度方案可得出需重調度的工件信息如表9所示。

重調度后得到的最優方案對應的甘特圖展示如圖6所示，最小總拖期時間值為8 793.92，最小總完工時間為2 395。

6 ?結 ?論

本文基于遺傳算法解決軍工電子柔性車間動態調度問題。該算法采用雙層編碼方式，并考慮緊急插單、交期變更、項目暫停等情況進行動態優化，使算法模型更貼近實際需求。同時，在項目權重評價時采用AHP法，得到定量的分析結果。基于遺傳算法求解柔性車間動態調度問題比傳統的生產計劃制定方式更高效，也是適應智能制造的發展趨勢。

后續的研究主要工作一方面可以進一步優化模型，考慮添加更多不確定性因素，如工藝流程的變更、設備或資源中斷情況等，考慮多個不確定性因素并存時對生產調度的影響。另一方面可以研究優化改進算法或其他的智能算法以求解此類問題。

參考文獻：

[1] 郭慶，張明路，孫立新，等.基于遺傳算法的柔性車間調度優化 [J].科學技術與工程，2020，20（29）：11931-11936.

[2] 肖華軍.考慮能效的雙資源柔性作業車間調度問題研究 [D].武漢：華中科技大學，2019.

[3] 劉勝，于海強.基于改進遺傳算法的多目標FJSP問題研究 [J].控制工程，2016，23（6）：816-822.

[4] 劉敏，張超勇，張國軍，等.基于混合粒子群優化算法的置換流水車間調度問題研究 [J].中國機械工程，2011，22（17）：2048-2053.

[5] 孫宏才，田平，王蓮芬.網絡層次分析法與決策科學 [M].北京：國防工業出版社.2011.

[6] 張超勇，饒運清，李培根，等.求解作業車間調度問題的一種改進遺傳算法 [J].計算機集成制造系統，2004（8）：966-970.

[7] 孫麗珍，畢利.多約束條件下的動態柔性作業車間調度研究 [J].控制工程，2020，27（11）：1921-1929.

作者簡介：肖玉曼（1989—），女，漢族，重慶人，工程師，碩士研究生，研究方向：項目管理。