李海龍，陳發(fā)源，計效園+，李建斌，周建新

(1.華中科技大學(xué) 材料成形與模具技術(shù)國家重點實驗室，湖北 武漢 430074;2.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430074)

0 引言

隨著全球制造業(yè)數(shù)字化、信息化、網(wǎng)絡(luò)化的不斷發(fā)展，鑄造作為一種傳統(tǒng)的高污染、高能耗制造行業(yè)面臨巨大的挑戰(zhàn)和機遇[1]。提升企業(yè)生產(chǎn)管理水平，快速響應(yīng)市場需求，合理制定生產(chǎn)計劃成為鑄造企業(yè)可持續(xù)發(fā)展的關(guān)鍵。主生產(chǎn)計劃是鑄造生產(chǎn)計劃管理的核心，當(dāng)前國內(nèi)鑄造企業(yè)依靠人工方式制定主生產(chǎn)計劃，完成鑄造訂單在多個相互獨立的生產(chǎn)車間上的排產(chǎn)決策。然而現(xiàn)有人工主生產(chǎn)計劃，難以在現(xiàn)實不確定生產(chǎn)環(huán)境下，綜合考慮訂單交貨期、企業(yè)生產(chǎn)效率和生產(chǎn)車間負(fù)載均衡等多方面因素，解決具有同種生產(chǎn)工藝不同生產(chǎn)效益的鑄造并行車間最優(yōu)主生產(chǎn)計劃問題。同時，人工主生產(chǎn)計劃排產(chǎn)效率低下，排產(chǎn)結(jié)果缺乏科學(xué)性、合理性，嚴(yán)重制約著鑄造企業(yè)主生產(chǎn)計劃管理水平。對鑄造企業(yè)而言，在保證訂單按時交貨的條件下合理安排各車間生產(chǎn)計劃，既能提高企業(yè)生產(chǎn)效率，又能保證各車間生產(chǎn)任務(wù)分配的公平性，具有重要的現(xiàn)實意義。

鑄造及相關(guān)行業(yè)的生產(chǎn)計劃問題受到學(xué)術(shù)界和產(chǎn)業(yè)界的長期關(guān)注，國內(nèi)外針對該問題已經(jīng)做了廣泛研究。葉虎等[2]研究了鑄造熱處爐次計劃模型，提出了分類與遺傳算法相結(jié)合的求解方案，有效提高了鑄造熱處理批計劃效率;袁帥鵬等[3]針對煉鋼—連鑄生產(chǎn)調(diào)度問題提出了基于自適應(yīng)網(wǎng)格擇優(yōu)的非支配排序遺傳算法，有效降低了爐次間等待時間。當(dāng)前鑄造生產(chǎn)調(diào)度有關(guān)問題的研究以具體的鑄造生產(chǎn)工序為主，如熱處理爐次計劃、造型熔煉計劃等，而鑄造主生產(chǎn)計劃從宏觀角度制定企業(yè)生產(chǎn)排產(chǎn)決策，因此本文考慮以鑄造車間整體構(gòu)建并行機調(diào)度模型，求解最優(yōu)并行車間訂單排產(chǎn)方案。毛永年等[4]建立了具有并行制造特征的自動化混流生產(chǎn)線混合整數(shù)規(guī)劃模型，并通過大量隨機案例驗證了模型的性能;Karimi等[5]研究了多工廠批量供應(yīng)鏈調(diào)度問題，并提出分支定界法優(yōu)化排產(chǎn)運輸成本和任務(wù)延遲成本;Lin等[6]采用線性規(guī)劃和多級編碼的遺傳算法求解多工廠下的再生產(chǎn)制造系統(tǒng)的排產(chǎn)問題，并給出了相應(yīng)的管理指導(dǎo)意見;Jia等[7]研究了以最小化完工時間和電力消耗為目標(biāo)的并行批處理機調(diào)度問題，并采用多目標(biāo)蟻群算法進(jìn)行求解;Geyik等[8]提出一套專家規(guī)則來準(zhǔn)確評價焊工焊接能力，采用啟發(fā)式方法獲得焊工工作負(fù)載均衡的焊接計劃;孟磊磊等[9]研究了帶有阻塞限制的混合流水車間調(diào)度問題，通過引入領(lǐng)域搜索改進(jìn)回溯算法，求解最小完工時間的無關(guān)并行機調(diào)度?，F(xiàn)有并行機調(diào)度問題的研究在面對多目標(biāo)函數(shù)求解要求時，往往通過加權(quán)法或?qū)⑵溆嗄繕?biāo)函數(shù)轉(zhuǎn)換成約束條件的方式，把多目標(biāo)函數(shù)問題轉(zhuǎn)換成單個目標(biāo)進(jìn)行求解。這種方式在實際應(yīng)用中難以保證確定加權(quán)系數(shù)或約束條件邊界的科學(xué)性與合理性。采用經(jīng)典多目標(biāo)優(yōu)化算法解決該問題時，存在對較大規(guī)模問題求解效果不理想的問題，同時求得的最終結(jié)果為若干Pareto最優(yōu)解構(gòu)成的解集，不滿足應(yīng)用條件下希望直接給出最終推薦調(diào)度方案的需要。Abido[10]在采用多目標(biāo)進(jìn)化算法解決電力調(diào)度問題時，使用模糊優(yōu)選法從求得的Pareto最優(yōu)解集中挑選出了各目標(biāo)函數(shù)取值折中的方案，這為解決該類問題提供了新的思路?；谶@種思路，田啟華等[11]采用改進(jìn)的NSGA-Ⅱ算法(fast elitist non-dominated sorting genetic algorithm)求解產(chǎn)品開發(fā)任務(wù)調(diào)度問題，結(jié)合模糊優(yōu)選法給出了開發(fā)成本和執(zhí)行時間折中的執(zhí)行方案。由此可見，多目標(biāo)智能優(yōu)化算法和模糊優(yōu)選法相結(jié)合，是解決現(xiàn)實鑄造復(fù)雜約束條件下多目標(biāo)并行車間調(diào)度問題的一種新的途徑。

考慮到實際鑄造生產(chǎn)過程中的不確定性，往往不能準(zhǔn)確給出完成一項訂單所需的生產(chǎn)時間，這給主生產(chǎn)計劃帶來了新的難度。Rostami等[12]研究了模糊環(huán)境下帶有工作惡化和學(xué)習(xí)效應(yīng)的并行機調(diào)度問題，并提出了采用多目標(biāo)分支定界方法進(jìn)行求解;Liao等[13]研究了基于梯形模糊數(shù)的不確定環(huán)境下并行機調(diào)度問題，并對比了模糊大小對模糊數(shù)比較方法的影響;李尚函等[14]研究了基于三角模糊數(shù)的柔性作業(yè)車間調(diào)度問題，在深入分析Sakawa方法的基礎(chǔ)上設(shè)計了新的排序準(zhǔn)則。鑄造訂單在各車間完工所需的生產(chǎn)時間對主生產(chǎn)計劃排產(chǎn)結(jié)果具有重要影響，其準(zhǔn)確性不可忽略。為此，本文將訂單生產(chǎn)時間用三角模糊數(shù)表示，以減少模糊生產(chǎn)環(huán)境對排產(chǎn)結(jié)果的影響，然后建立以訂單提前/拖期懲罰成本、車間完工時間和工作負(fù)載均衡為指標(biāo)的多目標(biāo)整數(shù)規(guī)劃模型，引入模擬退火機制優(yōu)化強度Pareto進(jìn)化算法(Strength Pareto Evolutionary Algorithm 2, SPEA2)外部集的環(huán)境選擇操作和種群的更新方式，以提升其在較大規(guī)?？臻g搜索時的深度和廣度，然后通過模糊優(yōu)選法，從改進(jìn)的強度Pareto進(jìn)化算法(Improved Strength Pareto Evolutionary Algorithm 2, ISPEA2)求得的Pareto最優(yōu)解集中確定出在各目標(biāo)函數(shù)上折中的推薦排產(chǎn)方案，使所提出的模型和算法能夠滿足實際生產(chǎn)調(diào)度的需要。

1 鑄造并行車間排產(chǎn)模型

1.1 問題描述

鑄造并行車間主生產(chǎn)計劃排產(chǎn)是鑄造企業(yè)在多個生產(chǎn)工藝相同但生產(chǎn)效益不同的鑄造車間之間進(jìn)行訂單生產(chǎn)任務(wù)分配的一種決策活動。車間的生產(chǎn)工藝一般固定，具有同種生產(chǎn)工藝的鑄造車間構(gòu)成并行車間組。并行車間組內(nèi)的訂單排產(chǎn)問題可以抽象為無關(guān)并行機調(diào)度問題，屬于NP-hard問題。同時現(xiàn)實條件下的排產(chǎn)問題影響更為復(fù)雜。為此，本文在研究過程中對該問題模型進(jìn)行了相應(yīng)簡化。

(1)

三角模糊數(shù)之間加減運算可轉(zhuǎn)換為其內(nèi)部確定值之間的加減運算，同時可以根據(jù)其隸屬度函數(shù)完成如式(2)所示的去模糊化過程。

(2)

為進(jìn)一步簡化鑄造并行車間排產(chǎn)模型，作如下問題假設(shè)：

(1)車間生產(chǎn)工藝固定，一個車間只能滿足一種工藝類型的產(chǎn)品的生產(chǎn)要求；

(2)訂單生產(chǎn)工藝固定，且不可拆分；

(3)所有訂單必須分配給車間生產(chǎn)，但允許某些車間沒有生產(chǎn)任務(wù)；

(4)車間生產(chǎn)過程連續(xù)且不可被搶占。

基于上述假設(shè)條件，可以將鑄造生產(chǎn)車間按照工藝劃分到不同的并行車間組，一個車間只能屬于一個并行車間組。如圖1所示為確定并行車間組的流程圖。

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

(1)索引和參數(shù)

(2)決策變量

(3)

(4)

(3)目標(biāo)函數(shù)與約束條件

(5)

minF2=max(C1,C2,…,CM);

(6)

(7)

(8)

(9)

(10)

j=1,2,…,N;i≠j;

(11)

i=1,2,…,N;i≠j;k=1,2,…,M;

(12)

(13)

(14)

式(5)～式(7)為目標(biāo)函數(shù)，其中：式(5)為最小化訂單提前/拖期懲罰成本，式(6)為最小化所有車間中最大的總完工時間，式(7)為最小化各車間完成本次分配的訂單所需的時間的方差;式(8)和式(9)分別為計算訂單提前或拖期完成時，提前或延誤的天數(shù)；式(10)保證一個訂單只被分配到一個車間中，并由該車間單獨完成；式(11)用來決定分配給相同車間完成的訂單之間的先后次序關(guān)系；式(12)表示訂單i在車間k上的完工時間等于訂單i之前的訂單所需加工時間之和，加上訂單i的加工時間和完成車間原有剩余工作所需時間;式(13)表示車間k的總完工時間等于分配給車間k所有訂單加工時間之和加上完成車間原有剩余工作所需時間;式(14)為計算各車間完成本次排產(chǎn)所分配的訂單需要的時間。

2 基于ISPEA2與模糊優(yōu)選法的求解方案

SPEA2算法作為一種基于Pareto的元啟發(fā)式算法，在求解多目標(biāo)優(yōu)化問題時具有良好的性能[15]。本文基于所提出的數(shù)學(xué)模型，設(shè)計了離散編碼形式的ISPEA2算法，為提高其在離散解空間搜索的深度和廣度，通過引入模擬退火機制改進(jìn)算法外部集的環(huán)境選擇操作和種群的更新方式，以一定概率接受適應(yīng)度較差的解，控制外部集和種群的收斂速度，避免算法過早陷入局部最優(yōu)，求解出并行車間訂單排產(chǎn)的Pareto最優(yōu)解集。Pareto最優(yōu)解集中的任意一個解都不能在所有目標(biāo)函數(shù)上完全支配其他解，在實際應(yīng)用條件下，從中挑選合適排產(chǎn)方案的決策過程較為復(fù)雜。為此，本文采用模糊優(yōu)選法，以Pareto最優(yōu)解在各目標(biāo)函數(shù)上的均衡優(yōu)化程度為指標(biāo)，計算并從改進(jìn)后算法所求得的Pareto最優(yōu)解集中選出一個在各目標(biāo)函數(shù)上折中的解作為最終推薦排產(chǎn)方案，從而更好滿足實際生產(chǎn)排產(chǎn)的需要。如圖2所示為求解方案流程示意圖。

2.1 離散編碼

ISPEA2算法中種群個體采用離散整數(shù)的形式進(jìn)行編碼，儲存在一條由整數(shù)1～N和1～M-1個0組成的染色體向量中，其中1～N表示待分配的訂單編號，0表示將左右兩邊的訂單分配到不同的車間中。在解碼過程中，分配給相同車間的訂單的先后順序由編碼向量中從左到右的訂單編號順序決定。如圖3所示為將10個訂單分配給3個車間的排產(chǎn)方案編碼和解碼示意圖。車間A依次完成訂單6、3、8，車間B依次完成訂單2、7、9、5，車間C依次完成訂單10、4、1。

2.2 交叉變異操作

為保證ISPEA2算法在離散解空間的搜索性能，設(shè)計了如圖4和圖5所示的變異和交叉操作。在進(jìn)行變異操作時，首先在原染色體向量中隨機選取兩個位置，然后通過交換這兩個位置上的基因產(chǎn)生變異后的新個體。交叉操作首先在父本基因向量上隨機選擇兩個交叉點，交叉點兩端的基因?qū)⒅苯訌?fù)制到孩子個體染色體向量中，剩余的基因?qū)凑赵谀副救旧w向量中的排列順序依次繼承到孩子個體染色體向量中。

2.3 模擬退火選擇

在外部集中添加和刪除個體、生成交配池以及交叉操作產(chǎn)生新種群過程中，需要在兩個候選個體之間進(jìn)行一次模擬退火選擇。模擬退火選擇步驟如下：

步驟1計算個體a和b的適應(yīng)度值Fa、Fb。

步驟2判斷Fa是否大于Fb。若否，則選擇個體a。若是，則隨機生成(0,1]上某個概率值p，轉(zhuǎn)步驟3。

步驟3判斷公式隨機概率p是否滿足式(15)和式(16)所示條件。若是，則選擇個體a;否則選擇個體b。其中:t和T分別為當(dāng)前溫度和初始退火溫度，μ為退火速率，i為算法當(dāng)前迭代次數(shù)。

p

(15)

t=μi×T。

(16)

2.4 模糊優(yōu)選法

ISPEA2算法求解結(jié)果為一個由若干互不支配的Pareto最優(yōu)解構(gòu)成的解集，為進(jìn)一步從該解集中挑選出在各個目標(biāo)函數(shù)上表現(xiàn)均衡的折中推薦排產(chǎn)方案，本文選用模糊優(yōu)選法，通過計算Pareto最優(yōu)解各目標(biāo)函數(shù)值與Pareto最優(yōu)解集中該優(yōu)化目標(biāo)上最優(yōu)解和最差解的函數(shù)值的接近程度，作為各Pareto最優(yōu)解的評價指標(biāo)，從而判定其在各目標(biāo)函數(shù)上的均衡優(yōu)化性能，保證從Pareto最優(yōu)解集中選出的推薦排產(chǎn)方案的科學(xué)性與合理性。具體計算方法如下：如式(17)所示，首先分別求出Pareto最優(yōu)解集Ω中的解i在各個目標(biāo)函數(shù)j上的比重δij，其中FjMIN和FjMAX分別為Pareto最優(yōu)解集Ω在目標(biāo)函數(shù)j上最優(yōu)解和最差解的目標(biāo)函數(shù)值。當(dāng)解i在目標(biāo)函數(shù)j上的函數(shù)值等于FjMIN時比重δij為1，等于FjMAX時比重δij為0。

(17)

然后,經(jīng)過式(18)所示的標(biāo)準(zhǔn)化操作，計算得出Pareto最優(yōu)解i的評價指標(biāo)δi。評價指標(biāo)δi越高，說明該解在各目標(biāo)函數(shù)上的綜合表現(xiàn)越好。因此，本文將Pareto最優(yōu)解集中評價指標(biāo)最高的解確定為最終推薦排產(chǎn)方案。

(18)

3 仿真實驗

3.1 實驗設(shè)計

為驗證所提出模型和算法的有效性，設(shè)計了10組不同規(guī)模的仿真實驗，其中并行車間數(shù)和待分配的訂單數(shù)分別為：3，10；3，20；3，30；3，40；3，50；5，60；5，70；5，80；5，90；5，100。仿真實驗數(shù)據(jù)采用如表1所示的方法隨機生成。將改進(jìn)后的ISPEA2算法與改進(jìn)前的SPEA2算法、加權(quán)法進(jìn)行對比，算法的運行參數(shù)如表2所示。其中加權(quán)法采用遺傳算法(Genetic Algorithm, GA)進(jìn)行求解，3個目標(biāo)函數(shù)分別與對應(yīng)的權(quán)重λ1、λ2、λ3相乘，然后相加轉(zhuǎn)化為單目標(biāo)函數(shù)進(jìn)行求解。其中，λ1、λ2分別取[1,8]、[1,9-λ1]內(nèi)的整數(shù)，且λ1+λ2+λ3=10，組成較為全面覆蓋目標(biāo)函數(shù)權(quán)重可能分布的36個加權(quán)法解。

表1 仿真實驗數(shù)據(jù)

表2 算法運行參數(shù)

3.2 實驗結(jié)果與分析

為直觀展示算法對比結(jié)果，選取規(guī)模為3-30、3-50、5-70和5-90的4組仿真實驗數(shù)據(jù)繪制ISPEA2、SPEA2和加權(quán)法求解結(jié)果對比圖，如圖6～圖9所示。

從三維空間和二維平面上解的分布可以看出，改進(jìn)后的ISPEA2算法求得的Pareto最優(yōu)解的分布更靠近坐標(biāo)軸和原點，解的支配性明顯優(yōu)于SPEA2和加權(quán)法。隨著求解問題的規(guī)模增大，這一趨勢也更加明顯。3種算法在10組仿真數(shù)據(jù)上運算結(jié)果對比如表3和表4所示。其中，表3對比了3種算法所求得的解集中的解在3個目標(biāo)函數(shù)F1、F2和F3上所能取到的最小值，表4分析了SPEA2算法改進(jìn)前后求得的推薦解在各目標(biāo)函數(shù)值上的優(yōu)化率。優(yōu)化率ε根據(jù)公式(19)計算：

ε=|FSPEA2-FISPEA2|÷FSPEA2×100%。

(19)

式中FSPEA2和FISPEA2分別表示SPEA2算法和ISPEA2算法推薦解的各目標(biāo)函數(shù)值。

從表3可以看出，除了3-20、5-60和5-70實驗中在部分目標(biāo)函數(shù)上的最小值略高于3種算法所能求得的最小值以外，ISPEA2算法在其他實驗規(guī)模的對比中均能取到最低值，進(jìn)一步說明了其所求得的解相對于另外兩種算法的支配性。從表4可以看出，改進(jìn)后的算法求得的推薦解和改進(jìn)前的算法相比，各目標(biāo)函數(shù)值均得到有效優(yōu)化，其中目標(biāo)函數(shù)F2得到有效降低，目標(biāo)函數(shù)F1、F3優(yōu)化效果顯著，最高減少了改進(jìn)前算法的57.84%。

結(jié)合表3和表4可以看出，ISPEA2算法在較大規(guī)模問題上的求解效果與小規(guī)模問題相比更加明顯。實驗3-10、3-20中，由于問題搜索空間規(guī)模較小，3種算法均能有效的求得3個目標(biāo)函數(shù)上的最小值，改進(jìn)后的ISPEA2算法求得的推薦解優(yōu)化效果不明顯；隨著問題規(guī)模增加，所提出的模擬退火改進(jìn)策略有效避免了ISPEA2算法在搜索過程陷入局部最優(yōu)，使求出的3個目標(biāo)函數(shù)最小值明顯小于另外兩種算法，推薦解的優(yōu)化效果也隨之更加顯著。從總體來看，改進(jìn)后的算法所求得的解在完工時間目標(biāo)上有所降低，而生產(chǎn)懲罰成本明顯下降、車間負(fù)載均衡程度得到顯著提升。

表3 三種算法在各目標(biāo)函數(shù)上的最小值對比

表4 SPEA2算法改進(jìn)前后推薦解目標(biāo)函數(shù)值優(yōu)化率

4 結(jié)束語

為合理制定模糊生產(chǎn)環(huán)境下的鑄造企業(yè)并行車間主生產(chǎn)計劃，將訂單生產(chǎn)時間用三角模糊數(shù)表示，從訂單交期準(zhǔn)確率、車間工時利用率和負(fù)載均衡性3個方面綜合考慮，建立了鑄造并行車間訂單排產(chǎn)多目標(biāo)整數(shù)規(guī)劃模型，提出了離散編碼形式的ISPEA2算法，通過引入模擬退火策略改進(jìn)算法外部集的環(huán)境選擇操作和種群的更新過程，求解出并行車間訂單排產(chǎn)的Pareto最優(yōu)解集，然后通過模糊優(yōu)選法計算，從中選出折中的推薦排產(chǎn)方案。通過多個規(guī)模的仿真實驗驗證了所提出模型和求解算法的有效性。實驗結(jié)果表明，改進(jìn)后的ISPEA2算法求出的Pareto最優(yōu)解的支配性明顯優(yōu)于改進(jìn)前算法和加權(quán)法所求得的解，同時，最終確定的推薦排產(chǎn)方案與改進(jìn)前相比訂單提前/拖期懲罰成本、車間完工時間和負(fù)載不均衡程度均有效降低。

鑄造并行車間主生產(chǎn)計劃未來可能的研究方向包括以下兩點：

(1)當(dāng)前模型考慮的鑄造車間只能生產(chǎn)一種工藝類型的訂單，而實際情況下可能存在特殊車間能夠完成多種不同類型的生產(chǎn)任務(wù)?？紤]該特殊車間的并行車間排產(chǎn)問題更具挑戰(zhàn)性。

(2)實現(xiàn)鑄造主生產(chǎn)計劃求解方案與鑄造企業(yè)現(xiàn)行數(shù)字化信息化生產(chǎn)管理軟件的集成，推動鑄造行業(yè)智能化發(fā)展。