羅小峰 胡 瑩 余 翔

（①南昌大學(xué)機電工程學(xué)院，江西 南昌 330031；②中國聯(lián)合網(wǎng)絡(luò)通信有限公司江西省分公司，江西 南昌 330006）

隨著網(wǎng)絡(luò)信息化的發(fā)展，MES 系統(tǒng)逐步進(jìn)入生產(chǎn)車間。生產(chǎn)規(guī)模擴大，對實際生產(chǎn)適應(yīng)度要求變高。離散型的車間調(diào)度[1]問題，多品種小批量的生產(chǎn)需求，多目標(biāo)、多約束[2]條件的實際場景，讓求解過程愈加復(fù)雜。

國內(nèi)外學(xué)者對排程問題進(jìn)行了深入研究與分析。目前用于解決該類問題的方法有量子遺傳算法、粒子群優(yōu)化算法和人工蜂群算法等[3-5]。LI S Y 等[4]提出了一種粒子群優(yōu)化算法，專注于收斂性的速度和質(zhì)量；Kamal A M 等[6]總結(jié)前人研究成果，為后人的研究提供了參數(shù)指導(dǎo)和研究方向；針對收斂速度慢問題，Mohit A 等[7]在粒子群算法的基礎(chǔ)上結(jié)合遺傳算法提出了新穎的元啟發(fā)式技術(shù)；王玉芳等[8]將遺傳算法與模擬退火算法結(jié)合，提升算法尋優(yōu)能力；為保留父代優(yōu)良特征，張超勇等[9]提出新的POX 交叉算子，荊巍巍等[10]對于多目標(biāo)調(diào)度問題提出自適應(yīng)NSGA-II 算法，并通過實例證明了算法有效性。以上研究提出了許多算法模型，算法之間的結(jié)合方便了問題的求解。由于APS 本身適用性不強，目前在實際生產(chǎn)中的應(yīng)用并不理想，因此本文基于某機加車間的實際生產(chǎn)情況，提出了基于傳統(tǒng)遺傳算法，解決多目標(biāo)、多約束條件生產(chǎn)排程問題的改進(jìn)遺傳算法，建立相關(guān)排產(chǎn)模型并求解，提高生產(chǎn)排程效率。

1 問題描述與建模

1.1 問題描述

APS(advanced scheduling)排程是一種基于有限產(chǎn)能的特殊排序方式，即在某一段時間將工序、設(shè)備和人員分配到對應(yīng)時間節(jié)點上，最終達(dá)到高效有序生產(chǎn)的目的。

訂單是整個生產(chǎn)車間的核心，根據(jù)生產(chǎn)需求分析后可以得出生產(chǎn)任務(wù)。設(shè)備之間存在產(chǎn)能差異，產(chǎn)品可能存在多工藝路線，還存在雙工位情況，即一臺機床，可以同時加工兩道工序。

企業(yè)生產(chǎn)效率要提高，關(guān)鍵在于降成本、降廢品率，提高設(shè)備利用率，減少設(shè)備空閑時間。排程中所涉及的要素如表1 所示。

表1 機加排程問題信息

1.2 約束條件

（1）設(shè)備存在雙工位交替的情況，即同一設(shè)備、兩個工位，同時作業(yè)。

（2）單個零件加工時間只受設(shè)備生產(chǎn)節(jié)拍影響，即設(shè)備的產(chǎn)能一定。

（3）如設(shè)備中途出現(xiàn)故障，更換設(shè)備的時間忽略不計。

（4）相鄰設(shè)備優(yōu)先派工，根據(jù)設(shè)備的派工優(yōu)先級進(jìn)行派工。

（5）同一種零件優(yōu)先安排在同一臺設(shè)備上進(jìn)行加工。

（6）工序委外需等該工序完成后才能開始下一道序。

（7）交期靠前的訂單優(yōu)先安排生產(chǎn)。

約束條件的多元性，決定了算法設(shè)計的復(fù)雜度，其中雙工位需考慮交替加工情況，保證工序不發(fā)生混亂。相鄰設(shè)備在空閑時考慮優(yōu)先派工，縮短物料運送時間，設(shè)備的派工優(yōu)先級還需根據(jù)使用頻次動態(tài)調(diào)整，提升設(shè)備使用率。

1.3 目標(biāo)函數(shù)

（1）按時交貨因子，保證在交貨期之前完成訂單。

（2）48 h 達(dá)成率因子，即相鄰兩序之間加工間隔時長不超過48 h。

（3）設(shè)備連續(xù)性影響因子，盡可能縮短設(shè)備待機時間，提高設(shè)備使用的連續(xù)性。

（4）最短完工時間影響因子，即盡早完成生產(chǎn)任務(wù)。

以上的生產(chǎn)排程目標(biāo)，涉及到眾多影響因素，彼此間存在矛盾關(guān)系，往往難以兼顧所有，需均衡各方面要素。

1.4 數(shù)學(xué)模型

根據(jù)以上問題的描述與分析，本文采用加權(quán)組合優(yōu)化法，建立如下目標(biāo)函數(shù)模型：

其中：C(T)為工序結(jié)束時間，Ma(T)為工序結(jié)束最晚時間，Mi(T)為工序結(jié)束最早時間。C(Q)為按時交貨數(shù)量，Ma(Q)為按時交貨的最大數(shù)量，Mi(Q)為按時交貨的最小數(shù)量。C(E)為連續(xù)設(shè)備數(shù)量，Ma(E)為連續(xù)設(shè)備的最大數(shù)量，Mi(E)為連續(xù)設(shè)備的最小數(shù)量。C(R)為48 h 達(dá)成率數(shù)量，Ma(R)為48 h 達(dá)成率最大數(shù)量，Mi(R)為48 h 達(dá)成率最小數(shù)量，以上時間都按分鐘計算，F(xiàn)為是否完成比率，I為是否按時完成比率，A為是否達(dá)成比率。

式中：S1為最短完工時間影響因子；S2為按時交貨影響因子；S3為48 h 達(dá)成率影響因子；S4為設(shè)備連續(xù)性影響因子；W1為最短完工時間影響因子權(quán)重；W2為按時交貨影響因子權(quán)重；W3為48 h 達(dá)成率影響因子權(quán)重；W4為設(shè)備連續(xù)性影響因子權(quán)重。

2 算法設(shè)計與優(yōu)化

2.1 算法設(shè)計

運用遺傳算法的思想，將實際生產(chǎn)與理論相結(jié)合，更好地解決實際問題。將眾多排產(chǎn)方案看作一個種群，一個排產(chǎn)方案對應(yīng)一條染色體，工序?qū)?yīng)基因，考慮到實際生產(chǎn)中還有設(shè)備元素和雙工位的情況，引入分子和裂變分子的概念，一臺設(shè)備對應(yīng)一個分子，如果是雙工位，則存在裂變分子。

2.1.1 編碼

合適的編碼方式使得算法求解變?nèi)菀住C加生產(chǎn)中的排程問題，首先確定加工路線，之后是設(shè)備分配，最后是人員排班。

通過分析，采用三段式排程編碼方案，第一段為工序分配，即確定工序的總時長、開始時間和結(jié)束時間，計算公式如下：

其中：Ri為第i道序的節(jié)拍，Li為加工的數(shù)量，Si為加工時長，Tie為結(jié)束時間，Tis為開始時間。T總為總時長，S為工序集合{S1,S2,···,Sn}。

第二段為設(shè)備分配，確定加工零件的設(shè)備工作時段，計算公式如下所示：

其中：Mie為設(shè)備結(jié)束時間，MiS為設(shè)備開始時間，M總為所有設(shè)備總加工時長，M為設(shè)備集合{M1,M2,···,Mn}。

第三段為人員分配，確定相關(guān)操作人員工作時段，計算公式如下：

其中：Gie為操作人員結(jié)束時間；GiS為操作人員開始時間；G總為所有操作人員總加工時長；G為人員的集合{G1,G2,···,Gn}。

例如F1(S1,M2,G1)為任務(wù)F1的第一道工序由G1人員在M2設(shè)備上進(jìn)行加工。

2.1.2 初始染色體種群

種群規(guī)模大小的選擇關(guān)系到排程結(jié)果的好壞，一般選擇種群大小在[50,200]。

采用加權(quán)系數(shù)法生成初始種群。對于插單的情況需采用前向排程,給突發(fā)情況留更多的緩沖空間，保證交貨期之前完成任務(wù)。對于委外工序，即該工序外包生產(chǎn)，采用前、后混合排程，在委外工序完成之前采用后向排程,在委外工序完成之后采用前向排程，有利于前后工序的緊密銜接。而對于以按時交貨為目標(biāo)的任務(wù)，采用后向排程，保證按時交貨的同時降低庫存成本。

按照一定的權(quán)重隨機生成初始種群，面對不同的排程任務(wù)，動態(tài)調(diào)整權(quán)重大小。

2.1.3 選擇、交叉和變異

個體適應(yīng)度越大，排程結(jié)果越優(yōu)，根據(jù)個體的好壞程度決定個體選擇的概率，極大程度避免優(yōu)良個體交叉變異之后成為較差個體，一定程度上保證了算法的收斂速度，也被稱為保優(yōu)策略。一般選擇概率在[5%,10%]，本文選取8%，這部分個體直接進(jìn)入子代種群中。

交叉是遺傳算法中的關(guān)鍵步驟，通過染色體交叉操作，可產(chǎn)生優(yōu)良品種，增加種群多樣性。由于工序交叉無法保證產(chǎn)品的正常生產(chǎn)，所以采用設(shè)備兩點交叉的方式，即隨機設(shè)置兩個交叉點，再進(jìn)行部分基因交換的方法。一般交叉概率在[50%,90%]。本文采用動態(tài)交叉概率，在交叉過程中，不斷改變交叉因子的大小，具體計算如下：

其中：Xi為交叉因子；G為總迭代次數(shù)；g為當(dāng)前迭代次數(shù)。

采用均勻變異的方式，在符合某一范圍內(nèi)取隨機數(shù)，這一變異方式適合于種群的初始運算。變異因子隨迭代次數(shù)動態(tài)變化。具體計算如下：

其中：Qi為變異因子；G為總迭代次數(shù)；g為當(dāng)前迭代次數(shù)。

通過非固定交叉因子和變異因子，避免陷入局部最優(yōu)解的同時，加快收斂速度，一定程度上提升了計算效率。

2.2 算法優(yōu)化

基于遺傳算法的思想，在以下幾方面優(yōu)化排產(chǎn)結(jié)果：

（1）基于產(chǎn)能失衡，或工序阻塞問題，在初始化種群時，根據(jù)派工級別按動態(tài)概率選擇設(shè)備。首先隨機產(chǎn)生索引數(shù)組（一個個數(shù)小于最大數(shù)的索引數(shù)組），索引數(shù)字大的概率高。

比如：index=4 產(chǎn)生的概率分布輸入：1-1/10,2-2/10,3-3/10,4-4/10。計算平均最優(yōu)時間，將生產(chǎn)任務(wù)分派到設(shè)備上，保證設(shè)備分派的優(yōu)先性和均衡性，計算公式如下：

其中：P總為計劃生產(chǎn)總數(shù)；T為平均時間；R為節(jié)拍；H為已占用時間。

（2）針對雙工位的設(shè)備，提出裂變分子的概念，算法設(shè)計偽代碼如下：

在排程結(jié)果涉及雙工位設(shè)備時進(jìn)行染色體偏移，調(diào)整工序之間的空隙，提高排程的緊湊性，算法設(shè)計偽代碼如下：

（3）針對排程任務(wù)多造成速度慢，效率低問題，采用工序合并降低訂單數(shù)量，算法設(shè)計偽代碼如下：

3 結(jié)果分析

3.1 實例描述

本文以某機械制造公司的實際生產(chǎn)排程為例，利用所設(shè)計的算法求解，算例中涉及8 種零件，共1 255 個產(chǎn)品，50 臺相關(guān)設(shè)備，其中2 臺雙工位設(shè)備，9 條加工路線，1 個零件是雙工藝路線，表2為各工序可選設(shè)備，表3 為每臺設(shè)備單位生產(chǎn)節(jié)拍。

表2 工序可選設(shè)備

表3 設(shè)備單位生產(chǎn)節(jié)拍

3.2 排程展示

本文算法基于.NET 平臺，采用B/S 架構(gòu)實現(xiàn)客戶端開發(fā)。排產(chǎn)過程運行在Window10 專業(yè)版64 位操作系統(tǒng)的PC 端，12.0 GB 運行內(nèi)存，i7-5500U 雙核四線程處理器，最后經(jīng)過6.3 s 得出結(jié)果。各參數(shù)詳細(xì)說明如下：

最短完工時間權(quán)重W1=0.3，按時交貨權(quán)重W2=0.4，48 h 達(dá)成率權(quán)W3=0.2，設(shè)備連續(xù)性權(quán)重W4=0.1，初始種群大小200，最大迭代次數(shù)150，選擇概率0.08，初始交叉概率0.8，變異概率0.05。

排程結(jié)果如圖1 所示。

對比之下，改進(jìn)后的遺傳算法效率大大提高，產(chǎn)能充分利用，穩(wěn)定性有保證，排程結(jié)果更加緊湊，設(shè)備使用率變高，加工時間縮短，人員安排更加靈活。

以傳統(tǒng)遺傳算法排程為1，兩種排程方式性能對比結(jié)果如表4 所示。

表4 結(jié)果對比

從表4 中數(shù)據(jù)可看出，改進(jìn)排程在排產(chǎn)速度方面大大提高，經(jīng)過多次排程性能均相差無幾，穩(wěn)定性好，在處理多目標(biāo)、訂單種類多和動態(tài)排程的情況，改進(jìn)后的排程系統(tǒng)優(yōu)勢更加顯著。

4 結(jié)語

本文基于多約束，多目標(biāo)條件下的機加生產(chǎn)排程問題，設(shè)計多目標(biāo)優(yōu)化模型，利用加權(quán)系數(shù)組合優(yōu)化法均衡各目標(biāo)，采用三段式排程編碼方案進(jìn)行編碼，在傳統(tǒng)遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)，設(shè)計了分子和裂變分子模型，針對裂變分子提出染色體偏移求解方法，保證了初始解質(zhì)量。通過動態(tài)調(diào)整交叉和變異因子大小，彌補傳統(tǒng)算法收斂速度慢的缺陷，相較于傳統(tǒng)遺傳算法排程優(yōu)勢明顯，為多約束多目標(biāo)條件下的離散型機加生產(chǎn)制造提供理論指導(dǎo)。由于本文在算法設(shè)計上不夠簡潔，且未將成本因素考慮在內(nèi)，這將作為今后進(jìn)一步研究的方向。