基于多目標(biāo)差分進(jìn)化算法的預(yù)制構(gòu)件生產(chǎn)重調(diào)度研究

于 淼，趙 潔，焦紅超

(沈陽(yáng)建筑大學(xué)管理學(xué)院，遼寧 沈陽(yáng) 110168)

裝配式建筑在我國(guó)發(fā)展還不夠成熟，預(yù)制構(gòu)件生產(chǎn)管理專業(yè)化程度低，生產(chǎn)過(guò)程中出現(xiàn)了調(diào)度混亂、生產(chǎn)效率低下、成本高等問題[1]，一定程度上阻礙了建筑工業(yè)化進(jìn)程。因此，對(duì)預(yù)制構(gòu)件進(jìn)行科學(xué)排產(chǎn)極其重要。目前，眾多學(xué)者對(duì)預(yù)制構(gòu)件生產(chǎn)車間展開了研究，有學(xué)者針對(duì)生產(chǎn)工序?qū)δＰ瓦M(jìn)行了改造。Li等[2]從供應(yīng)鏈角度考慮預(yù)制構(gòu)件生產(chǎn)過(guò)程的勞動(dòng)力、庫(kù)存資源約束，構(gòu)建了以生產(chǎn)成本最小化為目標(biāo)的生產(chǎn)調(diào)度模型。Wang等[3]通過(guò)構(gòu)建全供應(yīng)鏈生產(chǎn)調(diào)度模型，分析了新增工序?qū)ν旯r(shí)間的影響規(guī)律。Kong等[4]在原有生產(chǎn)調(diào)度模型中增加裝配環(huán)節(jié)，指出裝配式建筑包含生產(chǎn)—運(yùn)輸—裝配3個(gè)部分，建立了以最大生產(chǎn)效率為目標(biāo)的裝配式建筑全過(guò)程的資源調(diào)度模型。

為貼合現(xiàn)實(shí)生產(chǎn)條件，一些學(xué)者把資源約束引入生產(chǎn)調(diào)度模型，Chan等[5]在約束條件中加入養(yǎng)護(hù)室處理能力約束。Ko等[6]在Chan等[5]的基礎(chǔ)上增加了相鄰兩個(gè)工位之間的緩沖區(qū)容量約束，提高了模型實(shí)用性。在算法求解方面，遺傳算法應(yīng)用較多。謝思聰?shù)萚7]運(yùn)用遺傳算法，解決了招投標(biāo)和生產(chǎn)兩個(gè)階段的預(yù)制構(gòu)件優(yōu)化問題。程月明等[8]運(yùn)用非支配排序遺傳算法求解了考慮養(yǎng)護(hù)窯數(shù)量的混凝土預(yù)制構(gòu)件優(yōu)化模型。Ma等[9]采用非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithms，NSGA)對(duì)多條生產(chǎn)線優(yōu)化模型進(jìn)行了求解，完成了多條生產(chǎn)線優(yōu)化。

上述研究都是針對(duì)考慮資源約束的裝配式建筑預(yù)制構(gòu)件的靜態(tài)生產(chǎn)調(diào)度的，忽略了預(yù)制構(gòu)件加工環(huán)境的動(dòng)態(tài)性和不確定性。此外，在預(yù)制構(gòu)件生產(chǎn)調(diào)度效果評(píng)價(jià)上，對(duì)完工時(shí)間和懲罰成本這兩個(gè)相互沖突的目標(biāo)的處理上存在欠缺。針對(duì)以上研究存在的不足，筆者在綜合考慮模板約束和緩沖區(qū)約束的條件下對(duì)緊急插單情況下裝配式建筑預(yù)制構(gòu)件多目標(biāo)生產(chǎn)調(diào)度問題進(jìn)行研究，運(yùn)用多目標(biāo)差分進(jìn)化算法，優(yōu)化預(yù)制構(gòu)件生產(chǎn)調(diào)度方案，通過(guò)合理安排構(gòu)件生產(chǎn)順序，保證構(gòu)件在滿足完工時(shí)間最短和懲罰成本最少的雙目標(biāo)下順利交貨。

一、預(yù)制構(gòu)件生產(chǎn)調(diào)度問題描述

混凝土預(yù)制構(gòu)件生產(chǎn)車間與制造業(yè)的生產(chǎn)車間類似，都是經(jīng)過(guò)各種生產(chǎn)環(huán)節(jié)，生產(chǎn)出所需要的產(chǎn)品[10]。預(yù)制構(gòu)件的生產(chǎn)過(guò)程如圖1(a)所示。根據(jù)生產(chǎn)的工藝特征將其分為并行工序和串行工序，其中，混凝土養(yǎng)護(hù)為并行工序，可同時(shí)處理多個(gè)工件，其余則為串行工序。在預(yù)制生產(chǎn)環(huán)境中，該條流水線由Nk道工序組成，待生產(chǎn)j個(gè)預(yù)制構(gòu)件，每個(gè)預(yù)制構(gòu)件均包含Nk道工序，且這j個(gè)預(yù)制構(gòu)件必須在所有工序上以相同的順序進(jìn)行加工。Sj，Nk為對(duì)預(yù)制構(gòu)件(j，Nk)開始進(jìn)行加工的時(shí)間；Pj，Nk為對(duì)預(yù)制構(gòu)件(j，Nk)進(jìn)行處理所需的時(shí)間；E(j，Nk)為預(yù)制構(gòu)件加工結(jié)束的時(shí)間；dj為不施工方向預(yù)制構(gòu)件生產(chǎn)方提出的交貨日期。該批預(yù)制構(gòu)件的調(diào)度結(jié)束后，有一批數(shù)量為n*的緊急插單任務(wù)出現(xiàn)(見圖1(b))，需要立即進(jìn)行排程，將這批預(yù)制構(gòu)件記為j*={n+1，n+2，，n+n*}。插單對(duì)生產(chǎn)計(jì)劃造成擾動(dòng)，原先的調(diào)度計(jì)劃失效，需要進(jìn)行重新調(diào)度。

圖1 預(yù)制構(gòu)件生產(chǎn)工序與問題描述

預(yù)制構(gòu)件生產(chǎn)應(yīng)當(dāng)滿足以下要求：①每個(gè)工件必須按1，2，，m順序在所有機(jī)器上進(jìn)行工序處理；②除混凝土澆筑、養(yǎng)護(hù)外，其余工序均為搶占式工序；③預(yù)制構(gòu)件的加工時(shí)間包括其準(zhǔn)備時(shí)間，已知且不會(huì)發(fā)生變化；④除混凝土養(yǎng)護(hù)外，工序允許等待。

二、預(yù)制構(gòu)件生產(chǎn)調(diào)度模型

預(yù)制構(gòu)件生產(chǎn)調(diào)度模型參數(shù)如表1所示。

表1 預(yù)制構(gòu)件生產(chǎn)調(diào)度模型參數(shù)定義及說(shuō)明

1.優(yōu)化目標(biāo)

對(duì)預(yù)制構(gòu)件調(diào)度結(jié)果進(jìn)行評(píng)價(jià)時(shí)，需要同時(shí)兼顧多個(gè)目標(biāo)，確保調(diào)度結(jié)果符合預(yù)制構(gòu)件生產(chǎn)優(yōu)化的要求。因此，本研究選用完工時(shí)間和懲罰成本作為評(píng)價(jià)指標(biāo)，對(duì)調(diào)度結(jié)果進(jìn)行評(píng)價(jià)。完工時(shí)間為

f1=E(n，Nm)

(1)

懲罰成本通過(guò)完工時(shí)間大于交貨期產(chǎn)生的延遲成本和小于交貨期產(chǎn)生的庫(kù)存成本兩部分的和來(lái)計(jì)算

(2)

式中：Ej為預(yù)制構(gòu)件j的完工時(shí)間。

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

F=min(f1，f2)

(3)

2.約束條件

(1)可中斷工序

模具組裝、預(yù)埋件放置、拆模、構(gòu)件修補(bǔ)均屬于可中斷工序，即在8 h內(nèi)該工序沒有完成，可延后到第二天完成。可中斷工序的完工時(shí)間為

1，2，5，6

(4)

預(yù)制構(gòu)件生產(chǎn)工序累計(jì)完成時(shí)間為

T=max[E(j-1，Nk)，E(j，Nk-1)]+Pj，Nk

(5)

(2)不可中斷工序

①混凝土澆筑?；炷翝仓^(guò)程中涉及水泥的使用，屬于不可中斷工序，如果在加班時(shí)間內(nèi)可以完成，則選擇加班完成，反之，混凝土澆筑工序應(yīng)推遲到第二天進(jìn)行。預(yù)制構(gòu)件混凝土澆筑工序完工時(shí)間為

E(j，Nk)=

(6)

式中：HA為加班時(shí)間(HW>HA)。

②混凝土養(yǎng)護(hù)?；炷琉B(yǎng)護(hù)屬于非搶占式工序，不同類型的預(yù)制構(gòu)件可以在同一時(shí)間進(jìn)行養(yǎng)護(hù)，因此，混凝土養(yǎng)護(hù)開始時(shí)間在澆筑工序之后，其完成時(shí)間為

T*=E(j，N3)+Pj，Nk

(7)

E(j，Nk)=

(8)

③模板約束。預(yù)制構(gòu)件生產(chǎn)效率受模具數(shù)量的影響，因模板數(shù)量有限，會(huì)出現(xiàn)預(yù)制構(gòu)件模板等待時(shí)間。當(dāng)模具均被占用，只有等先進(jìn)行拆模工序的預(yù)制構(gòu)件釋放模板后，下一個(gè)預(yù)制構(gòu)件才能開始模具安裝。第j個(gè)預(yù)制構(gòu)件使用β模具的開始時(shí)間為

S(j，β，N1)≥minXβ{?y{E(y，β，N5)}}

(9)

式中：β為模具類型；Xβ為模具β的數(shù)量。

④緩沖區(qū)約束。緩沖區(qū)約束指相鄰工序之間的空間容量要大于預(yù)制構(gòu)件半成品的需要[11]。若工序Nk與工序Nk+1之間的存儲(chǔ)容量為BNk，那么構(gòu)件j從Nk離開的時(shí)間必須晚于構(gòu)件j-BNk進(jìn)入Nk+1的時(shí)間，此舉可保證各工序之間不發(fā)生阻塞現(xiàn)象。緩沖區(qū)約束表達(dá)式為

E(j，Nk)≥S(j-BNK，Nk+1)

(10)

三、算法設(shè)計(jì)

多目標(biāo)差分進(jìn)化算法是一種主要針對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化的算法。利用父代個(gè)體向量間差分的原理進(jìn)行種群個(gè)體的迭代更新，得到所求問題的最優(yōu)解。算法包括交叉、變異和選擇3個(gè)核心操作，符合進(jìn)化算法的一般流程[12]。

1.編 碼

采用整數(shù)序列編碼方式，先將工件連續(xù)編號(hào)，再將工件編號(hào)的排列組合作為一個(gè)完整的編碼序列。例如：工件總數(shù)為10，隨機(jī)編碼序列A=[4,6,5,3,8,2,1,9,7,10]，說(shuō)明每道工序加工的工件順序?yàn)?，6，，10。

2.適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用z1、z2表示，計(jì)算式為

z1=f1；z2=f2

(11)

3.種群初始化

設(shè)置種群規(guī)模、最大迭代次數(shù)、交叉概率。隨機(jī)生成1個(gè)初始種群p，對(duì)初始種群p的適應(yīng)度函數(shù)值進(jìn)行計(jì)算。

4.交叉變異

對(duì)初始種群p進(jìn)行交叉變異，產(chǎn)生第二代種群q，計(jì)算第二代種群q的適應(yīng)度值。

5.引入支配關(guān)系

對(duì)p、q進(jìn)行比較，如果p支配q，挑選p作為新一代種群，如果p與q沒有支配關(guān)系，則全部作為新一代種群。

6.擁擠距離計(jì)算

對(duì)步驟(5)產(chǎn)生的新種群按照式(12)進(jìn)行擁擠距離計(jì)算，然后根據(jù)計(jì)算結(jié)果挑選擁擠距離大的個(gè)體產(chǎn)生新的種群。

(12)

7.終止準(zhǔn)則

若滿足G≥100，則輸出Pareto最優(yōu)解集；反之，令迭代次數(shù)G=G+1，直到達(dá)到最大迭代次數(shù)，終止循環(huán)。

完整的MODE算法流程如圖2所示。

圖2 MODE算法流程

四、案例分析

筆者以某企業(yè)的預(yù)制外墻板生產(chǎn)線為例進(jìn)行分析，其預(yù)制構(gòu)件生產(chǎn)信息如表2所示，其中，N1為模具組裝；N2為預(yù)埋件放置；N3為混凝土澆筑；N4為混凝土養(yǎng)護(hù)；N5為拆模；N6為構(gòu)件修補(bǔ)。預(yù)制構(gòu)件各工序加工時(shí)間與交付時(shí)間、違約費(fèi)與庫(kù)存費(fèi)均通過(guò)實(shí)地調(diào)研和與部分負(fù)責(zé)人訪談得到(見表2)。在這一批次的8個(gè)預(yù)制構(gòu)件生產(chǎn)過(guò)程中，使用了A、B、C 3種模具。每天的常規(guī)工作時(shí)間(HW)為8 h。根據(jù)企業(yè)要求，加班時(shí)長(zhǎng)(HA)不能超過(guò)4 h，相鄰工位緩沖區(qū)空間設(shè)置為1，即相鄰工位能同時(shí)容納1個(gè)預(yù)制構(gòu)件。預(yù)制構(gòu)件生產(chǎn)準(zhǔn)備工作已經(jīng)做好，收到一個(gè)緊急訂單，該訂單包含2個(gè)預(yù)制構(gòu)件H，其生產(chǎn)信息如表3所示。

1.初始調(diào)度方案求解

數(shù)值計(jì)算過(guò)程中，初始種群規(guī)模NP=100，交叉概率CR=0.9，最大迭代次數(shù)G=100，采用MATLAB R2018b 軟件編程，利用多目標(biāo)差分進(jìn)化算法實(shí)現(xiàn)多目標(biāo)調(diào)度優(yōu)化。根據(jù)算法所設(shè)置的數(shù)值精度，對(duì)模型進(jìn)行求解，求得Pareto最優(yōu)解集(見圖3)。該初始調(diào)度產(chǎn)生3個(gè)調(diào)度方案(見表4)。

表2 預(yù)制構(gòu)件生產(chǎn)信息

表3 緊急插入訂單信息

2.預(yù)制構(gòu)件重調(diào)度

緊急訂單出現(xiàn)后，需要對(duì)初始預(yù)制構(gòu)件和緊急訂單中的構(gòu)件進(jìn)行重新決策，首先選擇初始調(diào)度中設(shè)備閑置時(shí)間最大的方案，對(duì)該方案中預(yù)制構(gòu)件和緊急訂單中包含的構(gòu)件進(jìn)行重調(diào)度。新增2個(gè)預(yù)制構(gòu)件H各工序占用各工序的處理時(shí)間如表5所示。

圖3 MODE算法優(yōu)化得到的Pareto最優(yōu)解

表4 預(yù)制構(gòu)件生產(chǎn)初始調(diào)度計(jì)劃

表5 新增預(yù)制構(gòu)件生產(chǎn)占用各工序時(shí)間 h

(1)重調(diào)度生產(chǎn)方案選擇

初始調(diào)度方案中，各工序空閑時(shí)間為從該工序生產(chǎn)的持續(xù)時(shí)間中抽去所有加工工件在機(jī)器上加工處理的時(shí)間，則各方案的各工序閑置時(shí)間如表6所示。方案1的機(jī)器閑置時(shí)間為173.4 h，閑置時(shí)間最長(zhǎng)且大于表5中新增構(gòu)件H所需的生產(chǎn)時(shí)間，因此，選擇方案1進(jìn)行生產(chǎn)重調(diào)度。

表6 預(yù)制構(gòu)件生產(chǎn)初始調(diào)度各方案閑置時(shí)間 h

(2)重調(diào)度求解

根據(jù)方案1，由于緊急訂單到達(dá)時(shí)，4號(hào)預(yù)制構(gòu)件的第一道工序已經(jīng)完成，進(jìn)行重調(diào)度時(shí)其第一道工序加工時(shí)間為0，則方案1預(yù)制構(gòu)件生產(chǎn)重調(diào)度模型輸入信息如表7所示。

表7 預(yù)制構(gòu)件生產(chǎn)重調(diào)度模型輸入信息

筆者運(yùn)用多目標(biāo)差分進(jìn)化算法對(duì)預(yù)制構(gòu)件重調(diào)度模型進(jìn)行求解，得到4個(gè)新的調(diào)度方案(見圖4)。為突出該算法的求解效果，將多目標(biāo)差分進(jìn)化算法與啟發(fā)式算法NEH(Nawaz、Enscore、Ham)進(jìn)行比較，NEH算法的核心思想是根據(jù)工件的加工時(shí)間把工件按照從大到小的順序進(jìn)行排列。選取序列中最靠前的兩個(gè)工件進(jìn)行組合，找到最小的工件排序，重復(fù)以上操作，直到全部工件被組合完畢[13]。啟發(fā)式算法NEH的參數(shù)設(shè)置參考多目標(biāo)差分進(jìn)化算法(MODE)、初始種群迭代次數(shù)、交叉概率，優(yōu)化后得到2個(gè)新的調(diào)度方案(見圖5)。

圖4 MODE算法優(yōu)化得到的重調(diào)度Pareto最優(yōu)解

圖5 NEH算法優(yōu)化得到的重調(diào)度Pareto最優(yōu)解

筆者引入距離和CPU運(yùn)行時(shí)間兩個(gè)指標(biāo)對(duì)兩種算法得到的帕累托最優(yōu)解的質(zhì)量進(jìn)行評(píng)價(jià)。

①距離指標(biāo)(GD)是檢驗(yàn)算法求得的所有非支配解之間的遠(yuǎn)近程度的數(shù)值[14]。計(jì)算式為

(13)

式中：C為非支配解集合中的解的數(shù)量；dp為所有非支配解中任一向量距離與其他向量之間的最小歐式距離。GD越小，則非支配解距離非支配解集合越近，算法性能越好[14]。

②CPU運(yùn)行時(shí)間是主要用于檢測(cè)算法運(yùn)行效率的指標(biāo)。運(yùn)行效率隨著運(yùn)行時(shí)間的縮短而提高。

根據(jù)兩種算法的優(yōu)化結(jié)果計(jì)算上述兩項(xiàng)指標(biāo)，評(píng)價(jià)結(jié)果如表8所示。比較運(yùn)行時(shí)間可知，MODE算法比NEH算法時(shí)間短，其運(yùn)行效率優(yōu)于NEH算法；比較距離可知，MODE算法比NEH算法更接近最優(yōu)解，其收斂性更好。

表8 多目標(biāo)優(yōu)化實(shí)驗(yàn)結(jié)果對(duì)比

3.結(jié)果分析

MODE算法優(yōu)化得到4個(gè)調(diào)度方案(見表9)，完工時(shí)間隨著懲罰成本的增加而減少。因此，當(dāng)企業(yè)接到緊急訂單時(shí)，可以選取完工時(shí)間最小的方案進(jìn)行生產(chǎn)。

表9 MODE算法優(yōu)化得到的預(yù)制構(gòu)件生產(chǎn)重調(diào)度計(jì)劃

五、結(jié) 語(yǔ)

筆者通過(guò)對(duì)插單擾動(dòng)下裝配式建筑預(yù)制構(gòu)件生產(chǎn)重調(diào)度問題進(jìn)行研究，優(yōu)化了預(yù)制構(gòu)件生產(chǎn)順序，達(dá)到了降低預(yù)制構(gòu)件生產(chǎn)成本的目的。通過(guò)構(gòu)建多目標(biāo)的預(yù)制構(gòu)件生產(chǎn)調(diào)度模型，選取多目標(biāo)差分進(jìn)化算法進(jìn)行算法設(shè)計(jì)，求得最優(yōu)預(yù)制構(gòu)件排產(chǎn)計(jì)劃，并通過(guò)案例分析證明了所構(gòu)建的求解預(yù)制構(gòu)件生產(chǎn)優(yōu)化模型操作簡(jiǎn)單，運(yùn)用的多目標(biāo)差分進(jìn)化算法在獲得Pareto最優(yōu)解上優(yōu)于啟發(fā)式算法，進(jìn)一步豐富了預(yù)制構(gòu)件生產(chǎn)求解思路，可為裝配式建筑預(yù)制構(gòu)件生產(chǎn)方提供參考，有利于預(yù)制構(gòu)件生產(chǎn)方針對(duì)緊急插單問題，安排合理的排產(chǎn)計(jì)劃。