陳潔瓊　樊留群

摘 要：預(yù)制構(gòu)件生產(chǎn)的MES系統(tǒng)中需要使用模臺(tái)排樣任務(wù)結(jié)果以安排生產(chǎn)作業(yè)調(diào)度規(guī)劃。針對生產(chǎn)排產(chǎn)作業(yè)時(shí)工裝模具調(diào)度、模臺(tái)排樣周轉(zhuǎn)時(shí)間長，模臺(tái)面積利用率低的問題，主要研究了以矩形包絡(luò)算法為零件預(yù)處理方式，并結(jié)合空余面積掃描算法的全局性及遺傳算法的最優(yōu)解，在多塊模臺(tái)上盡可能多地?cái)[放預(yù)制構(gòu)件進(jìn)行生產(chǎn)的排樣算法，在上層環(huán)節(jié)中可以通過CAM系統(tǒng)進(jìn)行初始的預(yù)估排樣，并以此作為排樣任務(wù)結(jié)果，為后續(xù)MES系統(tǒng)中的生產(chǎn)作業(yè)調(diào)度規(guī)劃提供較好的下料排樣基礎(chǔ)。

關(guān)鍵詞：預(yù)制構(gòu)件;模臺(tái)排樣;遺傳算法;矩形包絡(luò)

中圖分類號：TP391 ? ? 文獻(xiàn)標(biāo)志碼：A ? ? 文章編號：1003-5168（2022）3-0042-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.03.010

Research on the Layout Optimization of Multi-Die Tables in the Production Line of Precast Components

CHEN Jieqiong FAN Liuqun

（1.Zhejiang Institute of Mechanical & Electrical Engineering， Hangzhou 310053，China; 2.Tongji University， Sino-German Couege，Shanghai 200092，China）

Abstract： In MES system of prefabricated component production， the results of die layout are used to arrange production scheduling. Aiming at the problem of tooling and die scheduling， long turnover time of die layout and low utilization rate of die area， mainly studies the layout algorithm based on genetic algorithm and combining rectangle envelope algorithm and spare area scanning algorithm to place as many prefabricated components as possible on multiple die tables for production， which can be realized through cam system in the upper link The initial estimated layout is used as the result of the layout task， which provides a good basis for the subsequent MES production scheduling planning.

Keywords： prefabricated components; die layout; genetic algorithm; rectangular envelope

0 引言

預(yù)制構(gòu)件生產(chǎn)的MES系統(tǒng)中需要使用模臺(tái)排樣任務(wù)結(jié)果以安排生產(chǎn)作業(yè)調(diào)度規(guī)劃[1]。在預(yù)制構(gòu)件車間，模臺(tái)是核心資源，合理地排樣可以提高模臺(tái)的面積利用率，減少模臺(tái)的周轉(zhuǎn)時(shí)間，從而提高生產(chǎn)線的整體效率。排樣方法直接影響模臺(tái)的利用率、生產(chǎn)線生產(chǎn)效率、預(yù)算成本等。因此，在上層環(huán)節(jié)中可以通過CAM系統(tǒng)進(jìn)行初始、預(yù)估排樣，并以此作為排樣任務(wù)結(jié)果，為后續(xù)MES系統(tǒng)中的生產(chǎn)作業(yè)調(diào)度規(guī)劃提供較好的下料排樣基礎(chǔ)。對二維不規(guī)則零件采用包絡(luò)法預(yù)處理。陳潔瓊等[2]提出了利用空余面積掃描法，并結(jié)合遺傳算法對二維不規(guī)則風(fēng)管零件進(jìn)行排樣優(yōu)化的算法。孫波等[3]設(shè)計(jì)了利用剩余矩形排樣算法對二維矩形件排樣問題進(jìn)行優(yōu)化，并利用遺傳算法進(jìn)行排樣求解。陳仕軍等[4]提出了一種利用空白矩形填充和領(lǐng)域搜索結(jié)合的矩形件排樣優(yōu)化算法。本研究主要研究在多塊模臺(tái)上盡可能多地?cái)[放預(yù)制構(gòu)件進(jìn)行生產(chǎn)的排樣算法。

1 預(yù)制構(gòu)件排樣數(shù)學(xué)模型

針對預(yù)制構(gòu)件的排樣問題，簡單來說就是在一定數(shù)量的模臺(tái)上，布置一定形狀和數(shù)量的預(yù)制構(gòu)件，需要確保這些預(yù)制構(gòu)件相互之間不干涉、重疊，最重要的是不能超過模臺(tái)上的排樣邊界區(qū)域，但是，又需要盡可能地提高模臺(tái)的利用率。

本研究針對預(yù)制構(gòu)件的排樣算法，提出了如下的排樣數(shù)學(xué)模型。

式中：F為模臺(tái)利用率，是指待排樣包絡(luò)板的面積占實(shí)際使用模臺(tái)總面積的比例;m為模臺(tái)的數(shù)量;n為待排樣包絡(luò)板的數(shù)量;wi表示待排樣包絡(luò)板P的寬度;h表示待排樣包絡(luò)板Pi的高度;S=w?表示每個(gè)預(yù)制構(gòu)件的面積;W為模臺(tái)R的寬度;H為實(shí)際排樣后使用的模臺(tái)高度;L為模臺(tái)長;x和y表示待排樣包絡(luò)板Pi的左下角坐標(biāo);?θ表示待排樣包絡(luò)板Pi的旋轉(zhuǎn)角度，其中[θ∈0，90];?mWH為實(shí)際使用的模臺(tái)總面積。

上述模型中，在m塊模臺(tái)R（長為L，寬為W）上將n個(gè)預(yù)制構(gòu)件{ P，P，…，P}按照一定的約束條件排放，使模臺(tái)利用率最大化。模臺(tái)上排放的每個(gè)預(yù)制構(gòu)件的邊都要平行于模臺(tái)的四邊。其中約束條件如下。

①Pi和Pj待排樣包絡(luò)板之間不能重疊，其中，i≠j，i;j=1，2，3，…

②Pi必須排入到模臺(tái)R的邊，即待排樣包絡(luò)板在排樣過程中不能超過模臺(tái)的邊緣。

③Pi的邊必須平行于模臺(tái)R的邊，Pi預(yù)制構(gòu)件可以90°旋轉(zhuǎn)后再進(jìn)行排放。

④只采用一種排放方式，即橫排或豎排（旋轉(zhuǎn)90°再排放），直接排放待排樣包絡(luò)板。其中，橫排是指預(yù)制構(gòu)件的長邊平行于模臺(tái)件的寬，較短邊平行于模臺(tái)的長邊。

⑤由n個(gè)待排樣包絡(luò)板P（i=1，2，3，…，n）組成一個(gè)待排樣包絡(luò)板集合C={P，P，…，P}，其中Pi可以表示為P=（x，y，w，h，θ）。

2 優(yōu)化算法與分析

2.1 零件預(yù)處理

本研究選擇采用矩形包絡(luò)算法對排樣零件進(jìn)行矩形包絡(luò)。對露出鋼筋的預(yù)制構(gòu)件進(jìn)行包絡(luò)，計(jì)算包絡(luò)后形成矩形的預(yù)制構(gòu)件面積。因露出鋼筋長度不一，實(shí)際的模臺(tái)上各預(yù)制板之間還應(yīng)設(shè)置工人行走的區(qū)域，故包絡(luò)后的矩形有多種情形。將包絡(luò)后的矩形面積與預(yù)制構(gòu)件板面積的比值設(shè)置為矩形包絡(luò)比率，通過比較每種包絡(luò)方式產(chǎn)生的包絡(luò)比率，選擇最小的矩形包絡(luò)比率對象作為其后排樣方案中的待排樣包絡(luò)板。

2.2 空余面積掃描算法排樣過程

空余面積掃描法排樣步驟如下。

①將整個(gè)空白模臺(tái)設(shè)置為初始的剩余空白區(qū)域集。

②排入待排樣包絡(luò)板P后更新剩余空白區(qū)域集，再排入下一個(gè)預(yù)制構(gòu)件[Pi]。

③待排樣包絡(luò)板Pi在排入時(shí)，先選擇剩余空白區(qū)域左下角的頂點(diǎn)作為插入點(diǎn)，使預(yù)制構(gòu)件P的左下角頂點(diǎn)放置于空白模臺(tái)左下角頂點(diǎn)（x，y）處，以此坐標(biāo)點(diǎn)作為基準(zhǔn)點(diǎn)累加上P的w和?值，得到坐標(biāo)（x+w，y+?），即為待排樣包絡(luò)板Pi的右上角頂點(diǎn)值，將此值與剩余空白區(qū)域集的最大長L、寬W坐標(biāo)值對比，若x+w，y+?≤（W，L），則排入該包絡(luò)板。否則，將該包絡(luò)板旋轉(zhuǎn)90°后重新進(jìn)行上述排樣步驟。當(dāng)旋轉(zhuǎn)后的包絡(luò)板仍不能排入時(shí)，將該剩余空白區(qū)域最左下角（x，y）在兩軸的方向上加入最小步進(jìn)值x+1，y+1，再重復(fù)上述步驟進(jìn)行排樣。

④當(dāng)待排樣包絡(luò)板P在排入模臺(tái)R時(shí)，嘗試上述步驟③后，無法排入R模臺(tái)中的剩余空白區(qū)域集，則將待排樣包絡(luò)板排入模臺(tái)R中。

⑤重復(fù)上述步驟，直至所有待排樣包絡(luò)板排放在模臺(tái)上。

2.3 遺傳算法編碼

在空余面積掃描法的排樣算法的基礎(chǔ)上，最終的排樣方案由各待排樣包絡(luò)板排入模臺(tái)的順序及其擺放角度決定。包絡(luò)板在采用矩形包絡(luò)算法進(jìn)行處理后，形成的角度從最優(yōu)擺放形態(tài)上看，只有[0°、90°]兩種角度，因此，本算法在設(shè)計(jì)遺傳算法編碼方式時(shí)選擇采用3層染色體編碼的方式進(jìn)行編碼。

在該編碼方案中，3層染色體的數(shù)字依次分別指構(gòu)件排入順序、構(gòu)件所屬批次的編號、構(gòu)件在該批次中所屬編號。正負(fù)號代表零件的放入方向，正號代表0°擺放，負(fù)號代表90°擺放。如圖1所示，當(dāng)一個(gè)染色體的編碼為{-11，22，21，-15，13，-25，35}時(shí)，代表批次號為1、序號為1的構(gòu)件，批次號為2、序號為2的構(gòu)件，批次號為2、序號為1的構(gòu)件，批次號為1、序號為5的構(gòu)件，批次號為1、序號為3的構(gòu)件，批次號為2、序號為5的構(gòu)件，批次號為3、序號為5的構(gòu)件，按照1、2、3、4、5、6、7的順序放入模臺(tái)。其中11、15和23零件為90°擺放，22、21、13、35號零件為0°擺放。

據(jù)此，排樣方案就通過染色體編碼的方式進(jìn)行了標(biāo)記。其后對由排樣方案染色體組成的種群進(jìn)行遺傳算法的操作，可以得到相對最優(yōu)的個(gè)體排樣方案染色體。

在該問題中所要優(yōu)化的目標(biāo)函數(shù)如公式（6）所示。

所有待排樣包絡(luò)板占用模臺(tái)的總體高度H應(yīng)盡可能小。同批次編號的預(yù)制構(gòu)件因后續(xù)裝配需要，應(yīng)保證其排放在同一模臺(tái)或相近的模臺(tái)上。因此，選擇以每3塊模臺(tái)為集進(jìn)行篩選，統(tǒng)計(jì)種群中個(gè)體能完整組成同批次的排樣方案染色體數(shù)量，數(shù)值越大的個(gè)體，適應(yīng)度函數(shù)越高。

而在遺傳算法中，適應(yīng)度函數(shù)代表著個(gè)體適應(yīng)選擇的能力，適應(yīng)度函數(shù)越高，則個(gè)體越容易在選擇中留存下來。選取適應(yīng)度函數(shù)如公式（7）所示，個(gè)體對應(yīng)的排樣方案中零件所占的高度H越小，個(gè)體的適應(yīng)度函數(shù)就越高。

在按評價(jià)指標(biāo)擇優(yōu)后，上一代種群中的個(gè)體需要通過擇優(yōu)、交叉、變異三個(gè)過程來產(chǎn)生下一代種群。

2.4 優(yōu)化算法與流程

本研究提出的算法需要考慮以下三點(diǎn)。第一，對外輪廓上含有預(yù)埋洞和出筋的預(yù)制構(gòu)件進(jìn)行包絡(luò)處理;第二，考慮多模臺(tái)排樣問題;第三，多模臺(tái)排樣約束條件。需要著重說明的是，在進(jìn)行矩形包絡(luò)時(shí)，根據(jù)下述三個(gè)規(guī)則實(shí)現(xiàn)。圖2為某型號預(yù)制墻板的3層包絡(luò)輪廓線。包絡(luò)線需要3層，第一層（最內(nèi)層）：對構(gòu)件進(jìn)行最小矩形包絡(luò);第二層（中間層）：設(shè)置四邊可變參數(shù)作為鋼筋出筋外輪廓線;第三層（最外層）：此層輪廓線可共邊，是人在模臺(tái)上行走的區(qū)域。進(jìn)行排樣時(shí)，以最外層作為包絡(luò)線。

矩形包絡(luò)算法在二維不規(guī)則零件排樣的應(yīng)用上較為廣泛[5-8]，空余面積掃描算法與傳統(tǒng)的BL排樣算法[9]、下臺(tái)階排樣算法[10]比較，顯示出更強(qiáng)的局部優(yōu)化能力，而遺傳算法在全局尋優(yōu)搜索方面的性能要更好。將這三種算法融合使用，提出了一種針對預(yù)制構(gòu)件在多模臺(tái)上排樣的算法。

2.5 實(shí)例展示

圖3為多模臺(tái)排樣后的結(jié)果示意圖，共有4塊模臺(tái)，分別標(biāo)記為1、2、3、4號模臺(tái)。根據(jù)上述提出的排樣算法，圖4展示了同一個(gè)樓層、同批次所需要加工的預(yù)制構(gòu)件，分別為帶預(yù)埋窗洞的墻板3塊、帶預(yù)埋門洞的墻板1塊、樓板3塊?？紤]到生產(chǎn)預(yù)制構(gòu)件后要對同一個(gè)批次的預(yù)制構(gòu)件進(jìn)行入庫存儲(chǔ)擺放、物流運(yùn)輸?shù)葐栴}，應(yīng)將同一個(gè)批次的預(yù)制構(gòu)件盡可能放在鄰近的模臺(tái)上進(jìn)行排樣，并對此優(yōu)化評價(jià)指標(biāo)。

3 技術(shù)優(yōu)點(diǎn)與創(chuàng)新

本次研究主要通過預(yù)制構(gòu)件生產(chǎn)線生產(chǎn)當(dāng)中的排布形式以及對生產(chǎn)系統(tǒng)之間的關(guān)系進(jìn)行論述，同時(shí)利用數(shù)學(xué)模型以及計(jì)算方法進(jìn)行求解，切實(shí)提高了預(yù)制構(gòu)件生產(chǎn)的模臺(tái)利用效率，并進(jìn)一步降低了構(gòu)件的生產(chǎn)成本，也通過實(shí)際的生產(chǎn)數(shù)據(jù)核對了此方法的效果。因此，針對本研究的相關(guān)工作的開展來看，它的優(yōu)勢與創(chuàng)新點(diǎn)有4個(gè)方面。

①在研究對象上，本次研究屬于跨學(xué)科研究。研究不僅實(shí)現(xiàn)了將制造業(yè)的生產(chǎn)理念應(yīng)用到建筑領(lǐng)域中，而且也探討了建筑工業(yè)化領(lǐng)域中的預(yù)制構(gòu)件的生產(chǎn)以及構(gòu)件排樣的排布問題。通過研究的論述以及研究成果，可證明該方式不僅有利于縮短構(gòu)件的生產(chǎn)時(shí)間，并且也能降低構(gòu)件的生產(chǎn)成本。

②從模型應(yīng)用來看，在求解模型上，本研究主要針對矩形件排樣問題進(jìn)行了數(shù)學(xué)內(nèi)涵的展示，同時(shí)構(gòu)建了相應(yīng)的數(shù)學(xué)模型，并以圖像化的處理方式，對模型進(jìn)行了詳細(xì)的解釋，結(jié)合構(gòu)件生產(chǎn)行業(yè)的特定條件，對生產(chǎn)組合模型進(jìn)一步優(yōu)化，這在一定程度上實(shí)現(xiàn)了對矩形件的排樣問題進(jìn)行充分理論敘述與擴(kuò)充。

③在算法實(shí)現(xiàn)上，本研究針對傳統(tǒng)矩形件排樣問題以及其算法進(jìn)行了優(yōu)化，并針對單塊模板進(jìn)行排樣，通過求解單個(gè)模板的排量最優(yōu)解進(jìn)行整合，以此發(fā)現(xiàn)傳統(tǒng)的排樣結(jié)果十分雜亂，且操作性不強(qiáng)。對此，研究采用全新方法，實(shí)現(xiàn)了求解模板的最少需求量，并進(jìn)一步擴(kuò)大其綜合利用效率，從而使其在應(yīng)用的過程中，能夠更貼合預(yù)期目標(biāo)。

④本研究通過實(shí)例分析得出結(jié)論。通過對此種方法的應(yīng)用，能夠提高臺(tái)模利用效率，而且也能進(jìn)一步提升生產(chǎn)效率，還能有效降低養(yǎng)護(hù)的費(fèi)用。同時(shí)，研究論述方法能夠使排樣結(jié)果更加規(guī)整，更有利于實(shí)際操作，具備較高的應(yīng)用性。

4 結(jié)語

本研究主要提出并研究了預(yù)制構(gòu)件在多模臺(tái)上排樣的算法研究，排樣方法是將帶有預(yù)埋洞的預(yù)制件先包絡(luò)成矩形，利用空余面積掃描算法的局部優(yōu)化特點(diǎn)，結(jié)合遺傳算法全局搜索的優(yōu)點(diǎn)，提出了一種針對預(yù)制構(gòu)件在多模臺(tái)上排樣的方法。該算法從理論上可以提高模臺(tái)的利用率，從而提高預(yù)制構(gòu)件生產(chǎn)線的生產(chǎn)效率。在CAM系統(tǒng)中進(jìn)行初始預(yù)估排樣，并以此作為排樣任務(wù)結(jié)果，為后續(xù)MES系統(tǒng)中的生產(chǎn)作業(yè)調(diào)度規(guī)劃提供較好的下料排樣基礎(chǔ)。

參考文獻(xiàn)：

[1] 吳姝嫻.信息化技術(shù)在混凝土預(yù)制構(gòu)件生產(chǎn)過程中的運(yùn)用[J].綠色建筑，2016（6）：24-26.

[2] 陳潔瓊，樊留群，楊劍.遺傳算法在風(fēng)管制造排樣中的應(yīng)用[J].制造業(yè)自動(dòng)化，2017，39（5）：113-115，143.

[3] 孫波.鈑金件剩余矩形排樣遺傳優(yōu)化方法研究[J].西安工業(yè)大學(xué)學(xué)報(bào)，2015，35（4）：287-292.

[4] 陳仕軍，許繼影，戎愛英，等.空白矩形填充和鄰域搜索結(jié)合的矩形件排樣優(yōu)化算法[J].鍛壓技術(shù)，2021，46（2）：52-58.

[5] 楊衛(wèi)波.基于遺傳模擬退火算法的矩形件優(yōu)化排樣[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（7）：259-263.

[6] 朱霄霄.基于矩形包絡(luò)的二維排樣優(yōu)化[D].徐州：中國礦業(yè)大學(xué)，2020.

[7] 楊攀，李富平，楊文通，等.基于遺傳算法和啟發(fā)式方法的二維不規(guī)則零件排料[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2005（7）：36-37.

[8] 隗平平，劉斌.基于并行遺傳算法的矩形件排樣優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2011（3）：78-82.

[9] 韓志仁，林德強(qiáng).基于BL碰撞算法求解排樣過程中干涉的問題[J].沈陽航空航天大學(xué)學(xué)報(bào)，2011，28（2）：1-4.