基于多目標(biāo)多約束條件下排產(chǎn)算法設(shè)計(jì)與應(yīng)用＊

羅小峰 胡 瑩 余 翔

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

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

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

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

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

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

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

表1 機(jī)加排程問(wèn)題信息

1.2 約束條件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中：C(T)為工序結(jié)束時(shí)間，Ma(T)為工序結(jié)束最晚時(shí)間，Mi(T)為工序結(jié)束最早時(shí)間。C(Q)為按時(shí)交貨數(shù)量，Ma(Q)為按時(shí)交貨的最大數(shù)量，Mi(Q)為按時(shí)交貨的最小數(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ù)量，以上時(shí)間都按分鐘計(jì)算，F(xiàn)為是否完成比率，I為是否按時(shí)完成比率，A為是否達(dá)成比率。

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

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

2.1 算法設(shè)計(jì)

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

2.1.1 編碼

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

通過(guò)分析，采用三段式排程編碼方案，第一段為工序分配，即確定工序的總時(shí)長(zhǎng)、開(kāi)始時(shí)間和結(jié)束時(shí)間，計(jì)算公式如下：

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

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

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

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

其中：Gie為操作人員結(jié)束時(shí)間；GiS為操作人員開(kāi)始時(shí)間；G總為所有操作人員總加工時(shí)長(zhǎng)；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ù)法生成初始種群。對(duì)于插單的情況需采用前向排程,給突發(fā)情況留更多的緩沖空間，保證交貨期之前完成任務(wù)。對(duì)于委外工序，即該工序外包生產(chǎn)，采用前、后混合排程，在委外工序完成之前采用后向排程,在委外工序完成之后采用前向排程，有利于前后工序的緊密銜接。而對(duì)于以按時(shí)交貨為目標(biāo)的任務(wù)，采用后向排程，保證按時(shí)交貨的同時(shí)降低庫(kù)存成本。

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

2.1.3 選擇、交叉和變異

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

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

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

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

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

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

2.2 算法優(yōu)化

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

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

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

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

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

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

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

3 結(jié)果分析

3.1 實(shí)例描述

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

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

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

3.2 排程展示

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

最短完工時(shí)間權(quán)重W1=0.3，按時(shí)交貨權(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 所示。

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

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

表4 結(jié)果對(duì)比

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

4 結(jié)語(yǔ)

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