基于遺傳算法的PC構(gòu)件工廠排產(chǎn)研究

(1.中建三局綠色產(chǎn)業(yè)投資有限公司，武漢 430074；2.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，武漢 430068； 3.湖北工業(yè)大學(xué)土木建筑與環(huán)境學(xué)院，武漢 430068)

引言

隨著裝配式建筑項(xiàng)目的持續(xù)深入推進(jìn)，近幾年建筑產(chǎn)業(yè)化基地在全國(guó)各地相繼落成，PC構(gòu)件工廠紛紛拔地而起。由于裝配式建筑項(xiàng)目的規(guī)模和數(shù)量不斷增加，客觀上要求PC構(gòu)件工廠生產(chǎn)效率不斷提高，生產(chǎn)產(chǎn)能持續(xù)增長(zhǎng)。排產(chǎn)是生產(chǎn)中的一種匹配方式，不同的排產(chǎn)模式對(duì)應(yīng)不同的匹配方案，目的使生產(chǎn)產(chǎn)能最大化和各生產(chǎn)線負(fù)載實(shí)現(xiàn)均衡[1]。一方面，由于建筑工程體量大、建筑結(jié)構(gòu)復(fù)雜，構(gòu)件具有數(shù)量眾多、類型復(fù)雜的特點(diǎn)，造成構(gòu)件設(shè)計(jì)標(biāo)準(zhǔn)化程度低，不利于構(gòu)件的批量生產(chǎn)；另一方面，構(gòu)件工廠的數(shù)字化管理水平不高，還處于手工或半自動(dòng)化生產(chǎn)方式，生產(chǎn)自動(dòng)化程度低。以上兩個(gè)因素造成現(xiàn)有PC構(gòu)件工廠排產(chǎn)調(diào)度系統(tǒng)性差，未達(dá)預(yù)期設(shè)計(jì)生產(chǎn)能力。研究構(gòu)件排產(chǎn)調(diào)度方案，提高構(gòu)件生產(chǎn)產(chǎn)能，降低生產(chǎn)成本，具有重大的應(yīng)用價(jià)值和現(xiàn)實(shí)意義。

由于排產(chǎn)調(diào)度是一個(gè)典型的NP問題，國(guó)內(nèi)外在尋求最優(yōu)解方面取得了一定成果。如武韶敏等提出一種面向訂單多目標(biāo)排產(chǎn)問題的改進(jìn)遺傳算法[2]。一些文獻(xiàn)通過引入啟發(fā)規(guī)則，研究多任務(wù)組成訂單的排產(chǎn)模式[3-4]。目前，裝配式建筑項(xiàng)目尚處于起步階段，PC構(gòu)件排產(chǎn)調(diào)度方案依靠人工制定，其準(zhǔn)確性和客觀性較差。目前國(guó)內(nèi)學(xué)者對(duì)PC構(gòu)件生產(chǎn)線排產(chǎn)有一定研究成果，但對(duì)于工廠級(jí)排產(chǎn)研究尚不多見[1]。

本文在對(duì)PC構(gòu)件廠排產(chǎn)問題進(jìn)行分析和數(shù)學(xué)建模，結(jié)合遺傳算法提出工廠級(jí)的排產(chǎn)方法。實(shí)驗(yàn)表明，本文提出的方法能夠提高多條生產(chǎn)線的生產(chǎn)效率，實(shí)現(xiàn)產(chǎn)能最大化。

1 問題分析和數(shù)學(xué)建模

通常，PC構(gòu)件工廠車間布局多條混凝土預(yù)制構(gòu)件自動(dòng)化流水線，按流水生產(chǎn)線模塊分為外墻生產(chǎn)線、內(nèi)墻生產(chǎn)線、固定模臺(tái)生產(chǎn)線和其他生產(chǎn)線，形成多構(gòu)件多線體生產(chǎn)模式。預(yù)制構(gòu)件排產(chǎn)是一個(gè)多流水線、多工序的離散的復(fù)雜生產(chǎn)過程[5]。由于外墻生產(chǎn)線能夠生產(chǎn)內(nèi)墻生產(chǎn)線的產(chǎn)品，且固定模臺(tái)生產(chǎn)線用來(lái)生產(chǎn)復(fù)雜異型構(gòu)件，本文研究對(duì)象是多條外墻生產(chǎn)線下工廠產(chǎn)能最優(yōu)排產(chǎn)算法。外墻生產(chǎn)流水線上的工位包括清掃、噴涂、鋼筋模板裝配、預(yù)埋件安裝、澆筑振搗、上層板放置、擠塑板安裝、拉結(jié)件安裝、網(wǎng)片安裝、二次澆筑、振動(dòng)趕平、預(yù)養(yǎng)護(hù)、抹面、養(yǎng)護(hù)、拆模、翻板吊運(yùn)。適合生產(chǎn)的主要預(yù)制構(gòu)件有內(nèi)墻板、疊合板、隔墻梁、外墻板(單)、外墻三明治板。排產(chǎn)調(diào)度受PC構(gòu)件類型規(guī)格、生產(chǎn)線數(shù)量、工序時(shí)間及次序關(guān)系等因素的影響。

問題分析 假設(shè)某個(gè)PC構(gòu)件工廠配置L條外墻生產(chǎn)線，每一條生產(chǎn)線K個(gè)工序?，F(xiàn)有類型M，數(shù)量N個(gè)構(gòu)件構(gòu)成生產(chǎn)任務(wù)單，不同類型構(gòu)件的工序作業(yè)不同，求出生產(chǎn)任務(wù)單最優(yōu)的排產(chǎn)方案，保證產(chǎn)能最大。

根據(jù)現(xiàn)場(chǎng)生產(chǎn)情況，本文對(duì)工廠排產(chǎn)過程進(jìn)行建模，其約束條件如下：

(1)模臺(tái)沿設(shè)定軌道順工序向前移動(dòng)，在該固定的工位上完成相應(yīng)的作業(yè)；模臺(tái)空間和時(shí)間約束關(guān)系具有傳遞性。

(2)每一條外墻生產(chǎn)線按照固定節(jié)拍排產(chǎn)模式進(jìn)行生產(chǎn)。

(3)多條外墻生產(chǎn)線相互獨(dú)立、工位配置一致。

(4)人工、物料、機(jī)械設(shè)備能夠滿足各工位的作業(yè)要求，所有生產(chǎn)能夠按時(shí)完成。

N為構(gòu)件數(shù)量，L為生產(chǎn)流水線總數(shù)，i為構(gòu)件ID編號(hào)(i=1,2,…,n)；j為生產(chǎn)線編號(hào)(j=1,2,…,l)；Ri為每一個(gè)構(gòu)件的類型，表示編號(hào)為i的構(gòu)件工序數(shù)量；由于采用固定節(jié)拍，Ti表示類型為Mi構(gòu)件的作業(yè)時(shí)間。Ki是一個(gè)長(zhǎng)度K的序列，表示構(gòu)件在生產(chǎn)線上的加工序列。

Pml是一個(gè)二維矩陣，表示編號(hào)為Mi構(gòu)件需要在對(duì)應(yīng)編號(hào)Lj生產(chǎn)線上加工，即構(gòu)件生產(chǎn)線加工路線；Tml是一個(gè)二維矩陣，表示編號(hào)為Mi的構(gòu)件在Pml對(duì)應(yīng)的生產(chǎn)線上所需的加工時(shí)間。通過多條生產(chǎn)線負(fù)載均衡，讓后續(xù)構(gòu)件進(jìn)入當(dāng)前生產(chǎn)效率較高的生產(chǎn)線，對(duì)應(yīng)最快完工時(shí)間的那個(gè)排產(chǎn)順次就是排產(chǎn)結(jié)果。即

Tmin=min(∑Tml)

(1)

2 改進(jìn)的遺傳算法

本文結(jié)合生產(chǎn)情況和問題分析，提出基于改進(jìn)的遺傳算法的工廠級(jí)構(gòu)件調(diào)度算法。遺傳算法是計(jì)算機(jī)科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，屬于自適應(yīng)尋優(yōu)算法。

2.1 個(gè)體編碼

采用一個(gè) N×K的矩陣來(lái)表示遺傳算法中的個(gè)體， 即一種生產(chǎn)任務(wù)單排產(chǎn)的解決方案，矩陣采用實(shí)數(shù)編碼如下所示:

矩陣 A 的每一行代表一個(gè)構(gòu)件，共有N個(gè)構(gòu)件；矩陣每列對(duì)應(yīng)的生產(chǎn)線的加工工序，也就是一個(gè)構(gòu)件生產(chǎn)流程。 矩陣中元素的行標(biāo)i表示第i個(gè)構(gòu)件，列標(biāo)j表示第j個(gè)工序。由于本文每道工序采用固定節(jié)拍時(shí)間，因此aij的取值是[T,nT]的整數(shù)，表示構(gòu)件i的第j個(gè)工序進(jìn)行加工，T為一個(gè)流水節(jié)拍作業(yè)時(shí)間。

2.2 初始種群的產(chǎn)生

初始種群的個(gè)體是按行產(chǎn)生的。為了滿足構(gòu)件生產(chǎn)約束條件，每個(gè)構(gòu)件作業(yè)任務(wù)從第一道工藝流程開始隨機(jī)產(chǎn)生加工時(shí)間at1∈[T,nT]，接著為第二道工藝流程分配加工時(shí)間at2∈[T,nT]， 以此類推完成單個(gè)構(gòu)件的所有工藝流程的排產(chǎn)，進(jìn)而完成所有構(gòu)件的排產(chǎn)。

2.3 交叉算子

在遺傳算法中交叉具有重要作用，當(dāng)交叉概率偏大時(shí)，增強(qiáng)了遺傳算法對(duì)新空間的搜索能力，但優(yōu)秀基因遭到破壞的可能性也變大，算法收斂速度和穩(wěn)定性下降；當(dāng)交叉概率偏小時(shí)，遺傳算法的搜索會(huì)有滯后性。隨機(jī)在父代中選擇交叉點(diǎn)盲目性很大，算法性能會(huì)嚴(yán)重下降，因此本文不考慮父代基因隨機(jī)交換。由于構(gòu)件按固定節(jié)拍生產(chǎn)，構(gòu)件類型決定了構(gòu)件作業(yè)時(shí)間，按照構(gòu)件的類型把父代基因劃分為若干個(gè)小段，同時(shí)針對(duì)工序相同作業(yè)時(shí)間的構(gòu)件劃分到一個(gè)基因段，劃分完成后在父代中按作業(yè)時(shí)間順序選取相同基因段組成一個(gè)子代。父代基因段適應(yīng)度越高，被選作子代基因段的可能性越大。本文具體實(shí)現(xiàn)方法為：在雜交過程中,對(duì)父代中兩個(gè)個(gè)體對(duì)應(yīng)位上的值相加后采用模運(yùn)算求余,從而得到子代個(gè)體。

2.4 變異操作

傳統(tǒng)遺傳算法的任務(wù)調(diào)度易陷入局部最優(yōu)解,在改進(jìn)的遺傳算法中引入起輔助作用的變異算子并對(duì)其進(jìn)行改進(jìn),以期增加種群多樣性,從而實(shí)現(xiàn)改進(jìn)算法所得解達(dá)到全局最優(yōu)?？紤]該變異算子作為輔助算子應(yīng)具有簡(jiǎn)單易行的特點(diǎn),本算法將傳統(tǒng)變異算子作以下簡(jiǎn)單優(yōu)化,改進(jìn)為一個(gè)均勻變異算子,即可滿足要求。設(shè)k=(k1,k2,…,kn)為參加變異操作的父代個(gè)體。具體實(shí)現(xiàn)方法如下：①以均勻概率選取隨機(jī)數(shù)xi∈[1,q],(i∈N,i∈[1,n]),i從1至n依次取值；②以xi替換ki；③返回步驟①直至i=n 結(jié)束。從而得到新個(gè)體x=(x1,x2,…,xn)為變異后的子代個(gè)體。

2.5 適應(yīng)值函數(shù)

遺傳算法的適應(yīng)度函數(shù)用來(lái)判斷群體中的個(gè)體的優(yōu)劣程度，它根據(jù)所求問題的目標(biāo)函數(shù)來(lái)進(jìn)行評(píng)估。

構(gòu)件排產(chǎn)問題是求解加工耗費(fèi)總時(shí)間的最小值，這需要讓適應(yīng)度值最大化，所以適應(yīng)度函數(shù)定義為：

(2)

其中，tij為第i個(gè)構(gòu)件第j道流水線的作業(yè)時(shí)間；Ki是加工第i個(gè)構(gòu)件所需的最大工序數(shù)；n是構(gòu)件數(shù)。

2.5 終止條件

當(dāng)?shù)螖?shù)超過給定值后，算法停止運(yùn)行，此時(shí)得到的最優(yōu)解就是排產(chǎn)調(diào)度所需的相對(duì)最優(yōu)排產(chǎn)方式。

3 改進(jìn)的遺傳算法具體流程

本文的排產(chǎn)算法將貪心算法和遺傳算法相結(jié)合，利用遺傳算法進(jìn)行子代繁衍，適應(yīng)度應(yīng)用局部貪心算法選擇，保證時(shí)間復(fù)雜度和空間復(fù)雜度盡可能小的情況下來(lái)獲取一種盡可能接近于最優(yōu)的排產(chǎn)算法。改進(jìn)的遺傳算法操作步驟：

1)輸入構(gòu)件的種類、加工工序數(shù)和對(duì)應(yīng)工序的作業(yè)時(shí)間；

2)設(shè)定算法的群體規(guī)模和結(jié)束的循環(huán)代數(shù)，設(shè)定算法的初始交叉概率和變異概率。設(shè)定初始解集作為初始染色體；

3)計(jì)算當(dāng)前染色體適應(yīng)度值，把函數(shù)適應(yīng)度值最大的個(gè)體設(shè)定為當(dāng)前一代的最佳解；

4)檢驗(yàn)是否滿足算法收斂準(zhǔn)則，若滿足，則轉(zhuǎn)步驟7)，否則進(jìn)行步驟5)；

5)對(duì)染色體當(dāng)前的交叉概率和變異概率進(jìn)行動(dòng)態(tài)的自適應(yīng)調(diào)整，以調(diào)整后的交叉概率進(jìn)行改進(jìn)的交叉操作，以調(diào)整后的變異概率進(jìn)行變異操作；

6)對(duì)染色體進(jìn)行選擇操作，把經(jīng)過遺傳操作的染色體作為當(dāng)前染色體。轉(zhuǎn)步驟3)；

7)得到最佳個(gè)體，輸出結(jié)果。

該算法的流程圖如圖1所示。

圖1 改進(jìn)的遺傳算法流程圖

4 排產(chǎn)仿真與結(jié)果分析

4.1 生產(chǎn)流水線建模

AnyLogic仿真軟件作為一種創(chuàng)建真實(shí)動(dòng)態(tài)模型的可視化工具，具有較強(qiáng)的設(shè)計(jì)離散、系統(tǒng)動(dòng)力學(xué)、多智能體和混合系統(tǒng)的建模和仿真能力[1]。大量實(shí)際應(yīng)用表明，借助AnyLogic工具，便于分析和挖掘帶有動(dòng)態(tài)發(fā)展結(jié)構(gòu)及組件間關(guān)聯(lián)關(guān)系，適合創(chuàng)建對(duì)象的動(dòng)態(tài)模型[6-7]。PC構(gòu)件廠排產(chǎn)是一個(gè)典型的多工序生產(chǎn)、多運(yùn)輸平臺(tái)的離散和連續(xù)相結(jié)合的復(fù)雜生產(chǎn)過程，其生產(chǎn)流程具有工序多、人工干擾大、原料不穩(wěn)定、各工位作業(yè)時(shí)間波動(dòng)大等復(fù)雜系統(tǒng)的特性，生產(chǎn)組織和運(yùn)行難度較大。由于外墻生產(chǎn)線可以替代內(nèi)墻生產(chǎn)線生產(chǎn)，本文以外墻生產(chǎn)作為仿真對(duì)象，其生產(chǎn)線各工位之間的內(nèi)部邏輯如圖2所示。

圖2 外墻生產(chǎn)線內(nèi)部工位關(guān)系

圖3 外墻流水線生產(chǎn)流程模型圖

建模約束條件包括：

1)外墻流水線包含16個(gè)工位，根據(jù)不同工位作業(yè)復(fù)雜程度，可擴(kuò)展為25個(gè)子工位；

2)采用固定節(jié)拍排產(chǎn)模式；

3)養(yǎng)護(hù)窯工位的時(shí)間相對(duì)固定，按40個(gè)工位，每個(gè)15分鐘計(jì)算；

本文使用Anylogic 7.0.2 professional創(chuàng)建PC構(gòu)件外墻生產(chǎn)流水線模型，進(jìn)行內(nèi)部邏輯編程、運(yùn)行仿真和數(shù)據(jù)統(tǒng)計(jì)等工作。按照上述工藝流程、生產(chǎn)邏輯搭建模型，模型圖如圖3所示。

4.2 實(shí)驗(yàn)數(shù)據(jù)

為了分析外墻流水線生產(chǎn)產(chǎn)能的影響，本文選取含窗構(gòu)件、含門構(gòu)件、含門窗構(gòu)件和普通單墻等四種不同類型的PC預(yù)制外墻構(gòu)件，每種類型構(gòu)件數(shù)量均為75件。四種不同類型的PC預(yù)制外墻構(gòu)件按工序不同可擴(kuò)展為25個(gè)子工位。外墻流水線的數(shù)量為3條。由于不同類型構(gòu)件的外觀尺寸、體積、結(jié)構(gòu)復(fù)雜程度等不一致，工序相同的構(gòu)件作業(yè)時(shí)間不同，因此各個(gè)工序時(shí)間取決于構(gòu)件類型。比如，外葉墻澆筑作業(yè)時(shí)間與構(gòu)件類型有關(guān)，同時(shí)與構(gòu)件形狀、面積、體積有關(guān)；抹平時(shí)間與構(gòu)件類型、面積有關(guān)；拆模時(shí)間與螺絲數(shù)量成一定比例關(guān)系；網(wǎng)片安裝時(shí)間既取決于網(wǎng)片安裝的面積，又受到出筋數(shù)量的影響等等。綜合考慮上述多種因素，實(shí)驗(yàn)所用的4種不同類型外墻構(gòu)件作業(yè)時(shí)間如表1所示。表1的數(shù)據(jù)全部來(lái)源于某構(gòu)件工廠外墻流水線實(shí)際生產(chǎn)過程，是構(gòu)件多批次多時(shí)段統(tǒng)計(jì)的結(jié)果。

表1 不同構(gòu)件在各工位上的作業(yè)時(shí)間

4.3 仿真流程實(shí)現(xiàn)

本文基于某PC構(gòu)件工廠進(jìn)行建模，該工廠生產(chǎn)線有25個(gè)工位。按照?qǐng)D2所示構(gòu)件實(shí)際的工藝流程，設(shè)計(jì)構(gòu)件生產(chǎn)仿真過程，主要使用以下五種庫(kù)模塊，如表2所示：

表2 庫(kù)模塊及其功能

具體實(shí)施步驟如下：

(1) source模塊生成Module構(gòu)件類，并賦值該構(gòu)件ID，同時(shí)創(chuàng)建時(shí)間集合；

(2) Module構(gòu)件類進(jìn)入queue隊(duì)列模塊排隊(duì)，并從excel電子表格中獲取各個(gè)工位的時(shí)間數(shù)據(jù)；

(3) Module產(chǎn)品類進(jìn)入delay工位模塊，鎖上hold模塊，防止其它產(chǎn)品在進(jìn)來(lái)；

(4) 在deley工位模塊加工該工位的時(shí)間，完成后將實(shí)際時(shí)間記錄到timeList模塊，之后離開該工位模塊，進(jìn)入下一個(gè)deley工位模塊，同時(shí)解開hold鎖模塊，讓下一個(gè)產(chǎn)品進(jìn)來(lái)；

(5) Module構(gòu)件類依次走完剩余deley工位模塊，每次均記錄工位的實(shí)際時(shí)間，開關(guān)hold鎖模塊；

(6) 完成所有deley工位模塊的加工后，進(jìn)入sink終點(diǎn)模塊離開生產(chǎn)線，將每個(gè)工位記錄總進(jìn)行累加，求出總的時(shí)間；

(7) 后面構(gòu)件同上述過程運(yùn)行，最后輸出所有構(gòu)件的實(shí)際生產(chǎn)時(shí)間。

Anylogic仿真運(yùn)行圖，如圖4所示。

4.4 實(shí)驗(yàn)結(jié)果分析

將標(biāo)準(zhǔn)遺傳算法(SGA)[8]和本文算法應(yīng)用于該P(yáng)C構(gòu)件工廠實(shí)際生產(chǎn)進(jìn)行仿真對(duì)比。設(shè)定初始交叉概率0.70，變異概率0.05，種群規(guī)模M=300，進(jìn)化代數(shù)T=100，分別獨(dú)立運(yùn)行20次取平均值。利用Anylogic仿真，得到的結(jié)果如表3所示。

表3 SGA和本文算法的排產(chǎn)結(jié)果

比較分析可得：本文算法波動(dòng)率小，動(dòng)態(tài)穩(wěn)定性高，最優(yōu)解為98.45，排產(chǎn)效果優(yōu)于SGA。但由于引入貪心算法，本文算法運(yùn)行時(shí)間比SGA明顯縮短，運(yùn)行時(shí)間減少比例為17.6%。

圖4 外墻生產(chǎn)線仿真運(yùn)行圖

5 結(jié)語(yǔ)

結(jié)合PC構(gòu)件工廠的生產(chǎn)實(shí)際，本文選用貪心算法和遺傳算法各自優(yōu)點(diǎn)，提出一種產(chǎn)能最大的排產(chǎn)優(yōu)化方法，構(gòu)建了排產(chǎn)優(yōu)化的數(shù)學(xué)模型。引入貪心算法，設(shè)計(jì)了的改進(jìn)遺傳算法求解上述數(shù)學(xué)模型，提高了傳統(tǒng)遺傳算法的收斂速度。通過對(duì)算法對(duì)比，改進(jìn)算法比SGA算法顯著縮短了構(gòu)件的加工時(shí)間，優(yōu)化效果較為明顯，對(duì)PC構(gòu)件工廠產(chǎn)能提高有一定借鑒意義。