肖玉曼 湯旭東

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

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

中圖分類號：TP181 ? ? ? 文獻(xiàn)標(biāo)識碼：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)化進(jìn)程明顯加快，軍工電子領(lǐng)域普遍呈現(xiàn)訂貨數(shù)量激增的態(tài)勢。面對市場需求激增的情況，軍工企業(yè)除了需增加投入生產(chǎn)資源、擴(kuò)大產(chǎn)能，還需通過科學(xué)的方法提升生產(chǎn)效率。生產(chǎn)排程優(yōu)化就是其中一個突破點(diǎn)。

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

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

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

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

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

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

3.1 ?模型符號

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

3.2 ?目標(biāo)函數(shù)

最小化最大完工時間：

最小化總拖期時間：

3.3 ?約束條件

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

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

Cij≤Si（j+1）

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

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

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

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

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

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

（2）評分標(biāo)準(zhǔn)。項(xiàng)目在進(jìn)行評價打分時，參照的評分標(biāo)準(zhǔn)如表2所示。

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

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

4.1 ?染色體編碼

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

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

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

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

4.2 ?選擇交叉和變異

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

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

圖4 ?POX交叉操作

變異操作先是在工序編碼段的基因隨機(jī)選取兩點(diǎn)進(jìn)行交換，而機(jī)器編碼段相應(yīng)位置的基因也跟著一起交換，因工序基因的交換改變了工件的工序信息，故有可能會使得機(jī)器編碼段產(chǎn)生非法解，針對非法解則根據(jù)機(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ā)生的時刻對還未開始的工序進(jìn)行重調(diào)度。根據(jù)軍工項(xiàng)目的特點(diǎn)，動態(tài)事件主要包括項(xiàng)目交貨期調(diào)整、緊急插單、項(xiàng)目暫?；蛉∠?。

當(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ā)生的時間。

二是機(jī)器的初始時間：

T-Mh=max（Ch，NewT）

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

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

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

下面以某軍工電子模塊、組件生產(chǎn)線為例，進(jì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)涉及的項(xiàng)目有5項(xiàng)，用編號1～5表示，如遇到項(xiàng)目產(chǎn)品數(shù)量較多時，可拆單，將其視為幾個單獨(dú)的項(xiàng)目。項(xiàng)目的工序數(shù)和可用資源集合信息如表3所示。項(xiàng)目各工序加工工時和交貨期如表4所示。

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

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

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

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

5.2 ?MATLAB仿真運(yùn)算

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

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

當(dāng)出現(xiàn)插單情況時，觸發(fā)重調(diào)度機(jī)制，對截止到當(dāng)前時間的未完項(xiàng)目工序及新增項(xiàng)目進(jìn)行重調(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)度問題。該算法采用雙層編碼方式，并考慮緊急插單、交期變更、項(xiàng)目暫停等情況進(jìn)行動態(tài)優(yōu)化，使算法模型更貼近實(shí)際需求。同時，在項(xiàng)目權(quán)重評價時采用AHP法，得到定量的分析結(jié)果。基于遺傳算法求解柔性車間動態(tài)調(diào)度問題比傳統(tǒng)的生產(chǎn)計劃制定方式更高效，也是適應(yīng)智能制造的發(fā)展趨勢。

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

參考文獻(xiàn)：

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

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

[3] 劉勝，于海強(qiáng).基于改進(jìn)遺傳算法的多目標(biāo)FJSP問題研究 [J].控制工程，2016，23（6）：816-822.

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

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

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

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

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