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

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

引言

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

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

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

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

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

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

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

(1)模臺沿設定軌道順工序向前移動，在該固定的工位上完成相應的作業(yè)；模臺空間和時間約束關系具有傳遞性。

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

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

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

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

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

Tmin=min(∑Tml)

(1)

2 改進的遺傳算法

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

2.1 個體編碼

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

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

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

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

2.3 交叉算子

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

2.4 變異操作

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

2.5 適應值函數(shù)

遺傳算法的適應度函數(shù)用來判斷群體中的個體的優(yōu)劣程度，它根據(jù)所求問題的目標函數(shù)來進行評估。

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

(2)

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

2.5 終止條件

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

3 改進的遺傳算法具體流程

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

1)輸入構件的種類、加工工序數(shù)和對應工序的作業(yè)時間；

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

3)計算當前染色體適應度值，把函數(shù)適應度值最大的個體設定為當前一代的最佳解；

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

5)對染色體當前的交叉概率和變異概率進行動態(tài)的自適應調(diào)整，以調(diào)整后的交叉概率進行改進的交叉操作，以調(diào)整后的變異概率進行變異操作；

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

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

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

圖1 改進的遺傳算法流程圖

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

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

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

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

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

建模約束條件包括：

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

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

3)養(yǎng)護窯工位的時間相對固定，按40個工位，每個15分鐘計算；

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

4.2 實驗數(shù)據(jù)

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

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

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

本文基于某PC構件工廠進行建模，該工廠生產(chǎn)線有25個工位。按照圖2所示構件實際的工藝流程，設計構件生產(chǎn)仿真過程，主要使用以下五種庫模塊，如表2所示：

表2 庫模塊及其功能

具體實施步驟如下：

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

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

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

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

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

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

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

Anylogic仿真運行圖，如圖4所示。

4.4 實驗結(jié)果分析

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

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

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

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

5 結(jié)語

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