陳繼文,張譯勻,高曉明,楊紅娟

(1.山東建筑大學機電工程學院,山東 濟南 250101)(2.山東建筑大學建筑城規(guī)學院,山東 濟南 250101)(3.山東建筑大學信息與電氣工程學院,山東 濟南 250101)

“十四五”建筑發(fā)展規(guī)劃要求大力發(fā)展裝配式建筑,以標準部品為基礎,推動建立專業(yè)化、規(guī)模化、信息化生產(chǎn)體系[1]。裝配式建筑是“建筑+制造”跨界融合模式,PC(混凝土預制)構(gòu)件生產(chǎn)調(diào)度是影響工廠化生產(chǎn)效率的關鍵因素之一,為確保施工階段及時裝配,合理安排PC構(gòu)件生產(chǎn)調(diào)度具有重要意義[2]。

PC構(gòu)件的生產(chǎn)調(diào)度主要以構(gòu)件及時交付和成本最小化為研究目標,對多約束PC構(gòu)件生產(chǎn)調(diào)度進行優(yōu)化管理,以期最大化利潤。本文針對該問題建立PC構(gòu)件生產(chǎn)調(diào)度優(yōu)化模型,基于啟發(fā)式自適應遺傳算法,設計最優(yōu)選擇法、局部變異算子,以降低成本、提高收益和效率,實現(xiàn)生產(chǎn)調(diào)度的優(yōu)化。

1 生產(chǎn)調(diào)度優(yōu)化分析

1.1 PC構(gòu)件生產(chǎn)調(diào)度

PC構(gòu)件生產(chǎn)調(diào)度問題中每個構(gòu)件均在每個工序上加工一次,各構(gòu)件通過一定的順序完成加工。受制于PC構(gòu)件的生產(chǎn)特性、緩沖區(qū)和生產(chǎn)資源約束[3]等因素,PC構(gòu)件的生產(chǎn)線還未達到完全自動化,除養(yǎng)護階段可以不設置工人工作外,其余步驟均需工人看守[4]。整合關鍵的6道工序進行研究,如圖1所示。

PC構(gòu)件生產(chǎn)調(diào)度問題基于流水車間展開,其工作內(nèi)容為根據(jù)顧客的生產(chǎn)訂單進行分配處理,訂單內(nèi)包含多個需要加工的構(gòu)件,每個構(gòu)件在每個工序上只加工一次,并且構(gòu)件加工的順序都是相同的,直到完成所有工序。經(jīng)典的流水線車間調(diào)度(FSP)認為每個機器只能對一個工件進行加工,加工順序不可發(fā)生中斷,而在實際的預制構(gòu)件生產(chǎn)過程中,同時存在順序執(zhí)行、平行執(zhí)行、不可中斷工序和可中斷工序,因此將其視為特殊的FSP調(diào)度問題[5]。例如養(yǎng)護工序是可以多個構(gòu)件同時進行的,組裝、放置預埋件等操作是可以中斷的,養(yǎng)護和混凝土澆筑則不可中斷。建立PC構(gòu)件生產(chǎn)調(diào)度的數(shù)學模型具體條件設置如下:

1)初始時刻機器均可使用,構(gòu)件采用順序加工,依次在機器上排隊完成,構(gòu)件加工過程不可中斷,養(yǎng)護階段可以多個構(gòu)件并行處理。

2)所有構(gòu)件均按相同加工順序進行加工生產(chǎn),構(gòu)件根據(jù)到達時間早晚規(guī)定優(yōu)先級,先到先加工,兩道工序之間有緩沖區(qū),且緩沖區(qū)有限,構(gòu)件數(shù)目小于緩沖區(qū)容量時允許存放,構(gòu)件數(shù)目大于緩沖區(qū)容量時則在該機器上等待。

1.2 數(shù)學模型的建立

生產(chǎn)成本劃分為5個部分:人工成本、材料成本、機器工作成本、停機等待成本以及交貨期懲罰。人工成本是所有階段人工所需費用的總和,規(guī)定養(yǎng)護階段不需要工人,即機器編號g=4時不需要計算人工成本。材料成本指的是砂石、鋼筋等物品的消耗,根據(jù)實際數(shù)據(jù)設為M。機器工作成本指的是機器工作過程所用電量之和,停機等待成本考慮的則是機器空閑等待的時長tMs,空閑等待單位時間成本為Ms,并且養(yǎng)護階段機器持續(xù)運行,無需停機等待。交貨期懲罰是指構(gòu)件結(jié)束加工時間過早需要存儲而產(chǎn)生的庫存費用Cf,i,若延遲交貨則需要承擔相應的違約金Wy,i,對生產(chǎn)構(gòu)件設置一個交貨時間窗αi,提前時間為ad,i=max{0,Di,6-Si},延遲時間為d1,i=max{0,Si-Di,6},其中Si為第i個構(gòu)件規(guī)定完成時間。

(1)

(2)

(3)

式中:i為構(gòu)件號,C為生產(chǎn)成本,CR,g為單位時間人工成本,CD,g為單位時間機器成本,ti,g為構(gòu)件i在機器g上加工所需的時間,Q為交貨期懲罰,Ti,g為構(gòu)件i在機器g上的開始時間,Di,g為構(gòu)件i在機器g上的加工結(jié)束時間,n為該批構(gòu)件總數(shù)。

目標函數(shù)為:

(4)

式中:P(i)為生產(chǎn)該批構(gòu)件所獲得的利潤,Li為生產(chǎn)構(gòu)件i所獲得的收益。

生產(chǎn)約束:正常生產(chǎn)情況為構(gòu)件在當天工作時間和加班時間內(nèi)能完成生產(chǎn);非正常生產(chǎn)情況為在當天工作時間和加班時間內(nèi)未完成加工的構(gòu)件需延至第二天進行生產(chǎn)。養(yǎng)護工作不可中斷,從當天延續(xù)至第二天后能夠完成屬于正常生產(chǎn);若需要在當天工作結(jié)束后第二天上班之前完成,則完成時間為第二天開始上班的時間。

非養(yǎng)護階段的構(gòu)件在不同情況下完工時間的約束描述為:

(5)

Ti,g=24(D+1)A>24D+Hz+Hj

(6)

D=[A/24]

(7)

A=Ti,g+ti,g

(8)

式中:A為非養(yǎng)護階段加工構(gòu)件當天所用的工作時間;D為A占一整天的小時數(shù),不足1 h取整;Hz為正常工作時間;Hj為加班時間。

養(yǎng)護階段的構(gòu)件生產(chǎn)在不同情況下完工時間的公式描述為:

(9)

A1=Ti,4+ti,4

(10)

D1=[A1/24]

(11)

式中:A1為養(yǎng)護階段構(gòu)件在當天工作時間內(nèi)完工所用時間或構(gòu)件超出一天所用工作時間;D1為A1占一整天的小時數(shù),不足1 h取整。

緩沖區(qū)約束:緩沖區(qū)根據(jù)實際情況設置大小,不考慮緩沖區(qū)無限大的情況。等待時間具體計算公式如下:

(12)

式中:TW,i,g為構(gòu)件i等待機器g加工的時間;Ti-Hg,g+1為構(gòu)件(i-Hg)在機器(g+1)上的開始時間,其中Hg為各機器之間緩沖區(qū)的大小。

根據(jù)緩沖區(qū)約束可知,首個構(gòu)件開始工作時間記為0時刻,其余各構(gòu)件的開始工作時間為:

(13)

2 改進遺傳算法設計

PC構(gòu)件生產(chǎn)調(diào)度模型是基于FSP建模的,為了提升求解的準確性與效率,結(jié)合PC構(gòu)件生產(chǎn)調(diào)度的各種影響因素對標準遺傳算法進行改進,引入最優(yōu)選擇法和局部變異算子,改進后的遺傳算法提高了局部搜索能力[6],如圖2所示。

圖2 算法流程圖

2.1 選擇操作

選擇操作是對PC構(gòu)件生產(chǎn)順序中優(yōu)良個體的挑選,選出較好生產(chǎn)順序的個體經(jīng)過交叉變異操作遺傳給下一代。選擇操作采用兩種方法:輪盤賭法與最優(yōu)選擇法。最優(yōu)選擇法是選擇出適應度排名最好的前幾個進行保留,不參與后續(xù)遺傳操作直接放入下一代新種群,其余進行后續(xù)的遺傳變異。輪盤賭法[7]是個體適應度與整體適應度的比值在輪盤上所占的面積,適應度高所占面積大、選中概率高,低則反之。

2.2 變異與交叉操作

變異運算是在一條染色體上根據(jù)一定的概率,選取隨機數(shù)量的基因進行修改以獲得最優(yōu)的生產(chǎn)序列。為滿足種群的多樣性并保留適應度較高的父代,變異采用整體變異和局部變異兩種方式。

整體變異對于適應度低的染色體進行了徹底的更新,生成新的排列。PC構(gòu)件生產(chǎn)順序采用3種方法完成整體變異操作,即隨機選擇2個斷點i1、i2進行3種排列組合,其中i1表示第i1個位置的染色體,i1-1表示i1前一位的染色體,以此類推,他們的概率分別為0.3、0.3、0.4,其排列組合分別表示為:

(1～i1,i2,i1+1～i2-1,i2+1～n)

(1～i1-1,i1+1～i2,i1,i2+1～n)

(1～i1-1,i2,i1+1,i2-1,i1,i2+1～n)

局部變異則是對父代進行小范圍更改,保留了父代中的良好基因,能夠?qū)?yōu)良的基因遺傳給下一代,并且降低出現(xiàn)局部最優(yōu)的概率。PC構(gòu)件生產(chǎn)順序中隨機選取一小段進行變異,其數(shù)量可根據(jù)具體結(jié)果進行優(yōu)化,小范圍變異保證優(yōu)良個體能夠順利遺傳,也滿足染色體的多樣性。設定局部長度為3,局部改變這3個位置的染色體順序,以取得新的生產(chǎn)順序,具體如圖3所示。

圖3 局部變異

由于每個構(gòu)件都是唯一存在的且不可重復加工,每個構(gòu)件加工完一遍即完成工作,但兩個染色體之間做順序交叉會產(chǎn)生基因重復,即有一個構(gòu)件重復加工,另一個構(gòu)件卻一次都未加工。為避免出現(xiàn)上述錯誤,采用部分匹配交叉生成新的染色體。部分匹配交叉[8]避免了基因重復出現(xiàn)導致的異常,其修復染色體的原理是:在交叉范圍內(nèi)建立染色體與染色體間的匹配關系,在范圍外借助此關系解決重復問題。圖4為部分匹配加交叉詳細過程示意圖。

圖4 部分匹配交叉過程

3 算法仿真測試

3.1 預制構(gòu)件生產(chǎn)信息

在某預制構(gòu)件廠收集預制構(gòu)件相關數(shù)據(jù)[9],此訂單中預制構(gòu)件共有20個,要保證每個構(gòu)件在規(guī)定時間內(nèi)交貨并獲取最大利益,具體數(shù)據(jù)見表1。應用建立的模型與算法進行仿真測試,在MATLAB R2016a上進行運算,首先設置算法的參數(shù):迭代次數(shù)為600,種群規(guī)模為200,種群交叉概率為0.95,變異概率為0.30。

構(gòu)件生產(chǎn)工序之間緩沖區(qū)大小設置為(2,3,2,1,0,4),其中材料成本M總計24 220元。構(gòu)件加工成本即機器總用電量,用電費用按照工業(yè)用電標準設定[9],每個機器的用電消耗量為(4.3,66.0,9.3,14.2,20.6,0);構(gòu)件加工的人工成本為各階段工資總和,各階段工資為(56.1,133.4,107.4,0,53.1,25.0);工人加班時間設置為4 h,正常工作時間設置為10 h。

3.2 仿真方法性能對比分析

遺傳算法選擇算子的常用方法有最優(yōu)選擇法和輪盤賭法等。變異算子包括全局變異算子和局部變異算子,增加局部變異算子能夠更好地保留適應度較高的父代,也能夠避免一般迭代下容易進入早熟而出現(xiàn)的死循環(huán)。設置迭代次數(shù)為600,母代數(shù)量均為200,多次取樣對比,選取出現(xiàn)率較高的4組,為直觀看到本文提出的算法模型對此問題的解決效果,對不同選擇方法以及變異方法的對比總結(jié)見表2。

表2 算法選擇變異效果對比信息

通過實驗數(shù)據(jù)可以明顯看出,選最優(yōu)并且有局部變異的情況下,優(yōu)化后的利潤生產(chǎn)總值較其他3組高,并取得利潤最大值5 235.59元,達到良好的優(yōu)化效果。根據(jù)完工時間的長短可知,選最優(yōu)且有局部變異的情況下運行4次后的時間保持在78.4～78.5 h,較其他3組耗時短而且時長趨于穩(wěn)定,誤差較小。綜上可知,對時間以及成本優(yōu)化效果較好的方法是選最優(yōu)并且有局部變異的遺傳算法。

3.3 仿真最優(yōu)結(jié)果

由表2可以看出,經(jīng)改進遺傳算法優(yōu)化后的構(gòu)件生產(chǎn)在較短的時間內(nèi)取得了更高的利潤。優(yōu)化過程中經(jīng)過多次迭代取得最優(yōu)解,多次迭代結(jié)果如圖5所示,生成的最優(yōu)解甘特圖如圖6所示。

圖5 調(diào)度迭代曲線

圖6 甘特圖

由圖5可知,經(jīng)過多次尋優(yōu),115代左右收斂并取得了近似最優(yōu)解,目標函數(shù)的值保持穩(wěn)定,達到利潤最優(yōu)值,得到了最優(yōu)生產(chǎn)調(diào)度順序;平均適應度上下波動幅度有一定范圍,表明算法不會陷入局部最優(yōu),保證了結(jié)果的合理性。圖6顯示最后一個構(gòu)件在最后一臺機器上的結(jié)束時間為78.4 h,該生產(chǎn)調(diào)度優(yōu)化達到了預期目標,證明該優(yōu)化算法具有更高的可靠性。

4 結(jié)束語

基于PC構(gòu)件的生產(chǎn)工藝及特點,對PC構(gòu)件生產(chǎn)調(diào)度進行優(yōu)化,經(jīng)實際案例應用分析得出:綜合考慮多種約束的PC構(gòu)件生產(chǎn)調(diào)度模型,能夠更加貼合實際地解決生產(chǎn)過程中的問題;采用最優(yōu)選擇法篩選并保留父代,使良好基因得以遺傳給下一代;引入局部變異思想,提高了算法的局部搜索能力;該模型一定程度上節(jié)約了時間與空間資源,不僅能夠提高車間的生產(chǎn)效率,還可以減少不必要的生產(chǎn)成本和懲罰成本,為PC構(gòu)件生產(chǎn)動態(tài)管理提供了技術(shù)基礎。