肖玉曼 湯旭東

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

關(guān)鍵詞：遺傳算法;FJSP;動態(tài)調(diào)度;軍工電子;項目權(quán)重評價

中圖分類號：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 ?引 ?言

在當(dāng)前風(fēng)云變幻的國際形勢下，我國軍用電子元器件、組件模塊國產(chǎn)化進程明顯加快，軍工電子領(lǐng)域普遍呈現(xiàn)訂貨數(shù)量激增的態(tài)勢。面對市場需求激增的情況，軍工企業(yè)除了需增加投入生產(chǎn)資源、擴大產(chǎn)能，還需通過科學(xué)的方法提升生產(chǎn)效率。生產(chǎn)排程優(yōu)化就是其中一個突破點。

1 ?軍工電子項目生產(chǎn)排產(chǎn)現(xiàn)狀

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

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

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

3 ?FJSP動態(tài)調(diào)度問題的數(shù)學(xué)模型

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

3.1 ?模型符號

數(shù)學(xué)模型涉及的符號意義如表1所示。

3.2 ?目標函數(shù)

最小化最大完工時間：

最小化總拖期時間：

3.3 ?約束條件

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

（1）工件的當(dāng)前工序必須在上一道工序結(jié)束后才能開始：

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 ?項目權(quán)重評價

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

圖1 ?項目權(quán)重影響因素

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

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

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

4 ?遺傳算法求解FJSP動態(tài)調(diào)度問題

4.1 ?染色體編碼

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

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

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

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

4.2 ?選擇交叉和變異

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

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

圖4 ?POX交叉操作

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

4.3 ?動態(tài)優(yōu)化策略

動態(tài)車間調(diào)度問題普遍的研究方向分為基于事件驅(qū)動和周期驅(qū)動的重新調(diào)度策略[7]，結(jié)合柔性車間發(fā)生動態(tài)事件的常見情況，本文采用基于事件驅(qū)動的策略，也就是在動態(tài)事件發(fā)生的時刻對還未開始的工序進行重調(diào)度。根據(jù)軍工項目的特點，動態(tài)事件主要包括項目交貨期調(diào)整、緊急插單、項目暫停或取消等。

當(dāng)動態(tài)事件發(fā)生時，存在以下兩種約束：

一是工件的初始時間：

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

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

二是機器的初始時間：

T-Mh=max（Ch，NewT）

h為當(dāng)前機器的編號，且1≤h≤m;Ch為機器h當(dāng)前工序的結(jié)束時間;NewT為動態(tài)事件發(fā)生的時間。

當(dāng)動態(tài)事件發(fā)生時，根據(jù)約束條件定位到需重調(diào)度的工件工序信息。然后初始化需重調(diào)度的工件數(shù)，初始化各工件剩余工序加工時間集合，初始化各工序可選機器集合，初始化各工件交貨期。即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。然后對當(dāng)前所有還未開始的工件工序進行重調(diào)度。當(dāng)出現(xiàn)交貨期變更，則只需要調(diào)整目標函數(shù)中對應(yīng)的交貨期變量。當(dāng)出現(xiàn)項目暫?；蛉∠麜r，則將該項目的未開始工序從待排產(chǎn)工序中去除。

5 ?FJSP動態(tài)調(diào)度在軍工電子項目中的應(yīng)用

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

5.1 ?項目權(quán)重評估

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

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

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

5.2 ?MATLAB仿真運算

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

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

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

此時，根據(jù)前最優(yōu)調(diào)度方案可得出需重調(diào)度的工件信息如表9所示。

重調(diào)度后得到的最優(yōu)方案對應(yīng)的甘特圖展示如圖6所示，最小總拖期時間值為8 793.92，最小總完工時間為2 395。

6 ?結(jié) ?論

本文基于遺傳算法解決軍工電子柔性車間動態(tài)調(diào)度問題。該算法采用雙層編碼方式，并考慮緊急插單、交期變更、項目暫停等情況進行動態(tài)優(yōu)化，使算法模型更貼近實際需求。同時，在項目權(quán)重評價時采用AHP法，得到定量的分析結(jié)果?；谶z傳算法求解柔性車間動態(tài)調(diào)度問題比傳統(tǒng)的生產(chǎn)計劃制定方式更高效，也是適應(yīng)智能制造的發(fā)展趨勢。

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

參考文獻：

[1] 郭慶，張明路，孫立新，等.基于遺傳算法的柔性車間調(diào)度優(yōu)化 [J].科學(xué)技術(shù)與工程，2020，20（29）：11931-11936.

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

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

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

[5] 孫宏才，田平，王蓮芬.網(wǎng)絡(luò)層次分析法與決策科學(xué) [M].北京：國防工業(yè)出版社.2011.

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

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

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