于 淼，趙 潔，焦紅超

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

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

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

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

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

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

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

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

二、預(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ù)定義及說明

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

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

f1=E(n，Nm)

(1)

懲罰成本通過完工時間大于交貨期產(chǎn)生的延遲成本和小于交貨期產(chǎn)生的庫存成本兩部分的和來計算

(2)

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

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

F=min(f1，f2)

(3)

2.約束條件

(1)可中斷工序

模具組裝、預(yù)埋件放置、拆模、構(gòu)件修補均屬于可中斷工序，即在8 h內(nèi)該工序沒有完成，可延后到第二天完成?？芍袛喙ば虻耐旯r間為

1，2，5，6

(4)

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

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

(5)

(2)不可中斷工序

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

E(j，Nk)=

(6)

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

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

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

(7)

E(j，Nk)=

(8)

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

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

(9)

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

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

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

(10)

三、算法設(shè)計

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

1.編 碼

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

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

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

z1=f1；z2=f2

(11)

3.種群初始化

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

4.交叉變異

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

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

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

6.擁擠距離計算

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

(12)

7.終止準(zhǔn)則

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

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

圖2 MODE算法流程

四、案例分析

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

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

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

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

表3 緊急插入訂單信息

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

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

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

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

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

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

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

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

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

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

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

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

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

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

筆者引入距離和CPU運行時間兩個指標(biāo)對兩種算法得到的帕累托最優(yōu)解的質(zhì)量進行評價。

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

(13)

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

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

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

表8 多目標(biāo)優(yōu)化實驗結(jié)果對比

3.結(jié)果分析

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

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

五、結(jié) 語

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