基于改進(jìn)遺傳算法的PC構(gòu)件生產(chǎn)調(diào)度優(yōu)化

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

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

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

PC構(gòu)件的生產(chǎn)調(diào)度主要以構(gòu)件及時(shí)交付和成本最小化為研究目標(biāo),對(duì)多約束PC構(gòu)件生產(chǎn)調(diào)度進(jìn)行優(yōu)化管理,以期最大化利潤。本文針對(duì)該問題建立PC構(gòu)件生產(chǎn)調(diào)度優(yōu)化模型,基于啟發(fā)式自適應(yīng)遺傳算法,設(shè)計(jì)最優(yōu)選擇法、局部變異算子,以降低成本、提高收益和效率,實(shí)現(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è)構(gòu)件均在每個(gè)工序上加工一次,各構(gòu)件通過一定的順序完成加工。受制于PC構(gòu)件的生產(chǎn)特性、緩沖區(qū)和生產(chǎn)資源約束[3]等因素,PC構(gòu)件的生產(chǎn)線還未達(dá)到完全自動(dòng)化,除養(yǎng)護(hù)階段可以不設(shè)置工人工作外,其余步驟均需工人看守[4]。整合關(guān)鍵的6道工序進(jìn)行研究,如圖1所示。

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

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

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

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

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

(1)

(2)

(3)

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

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

(4)

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

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

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

(5)

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

(6)

D=[A/24]

(7)

A=Ti,g+ti,g

(8)

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

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

(9)

A1=Ti,4+ti,4

(10)

D1=[A1/24]

(11)

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

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

(12)

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

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

(13)

2 改進(jìn)遺傳算法設(shè)計(jì)

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

圖2 算法流程圖

2.1 選擇操作

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

2.2 變異與交叉操作

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

整體變異對(duì)于適應(yīng)度低的染色體進(jìn)行了徹底的更新,生成新的排列。PC構(gòu)件生產(chǎn)順序采用3種方法完成整體變異操作,即隨機(jī)選擇2個(gè)斷點(diǎn)i1、i2進(jìn)行3種排列組合,其中i1表示第i1個(gè)位置的染色體,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)

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

圖3 局部變異

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

圖4 部分匹配交叉過程

3 算法仿真測(cè)試

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

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

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

3.2 仿真方法性能對(duì)比分析

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

表2 算法選擇變異效果對(duì)比信息

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

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

由表2可以看出,經(jīng)改進(jìn)遺傳算法優(yōu)化后的構(gòu)件生產(chǎn)在較短的時(shí)間內(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)解,目標(biāo)函數(shù)的值保持穩(wěn)定,達(dá)到利潤最優(yōu)值,得到了最優(yōu)生產(chǎn)調(diào)度順序;平均適應(yīng)度上下波動(dòng)幅度有一定范圍,表明算法不會(huì)陷入局部最優(yōu),保證了結(jié)果的合理性。圖6顯示最后一個(gè)構(gòu)件在最后一臺(tái)機(jī)器上的結(jié)束時(shí)間為78.4 h,該生產(chǎn)調(diào)度優(yōu)化達(dá)到了預(yù)期目標(biāo),證明該優(yōu)化算法具有更高的可靠性。

4 結(jié)束語

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