面向多約束矩形預(yù)制構(gòu)件的自動排板算法研究

張銳杰，高 琦，鞏高鑠

（1.山東大學(xué) 機械工程學(xué)院，濟南 250061；2.山東大學(xué) 高效清潔機械制造教育部重點實驗室，濟南 250061）

0 引言

隨著裝配式建筑的大力發(fā)展，預(yù)制構(gòu)件生產(chǎn)企業(yè)的生產(chǎn)規(guī)模也越來越大。預(yù)制構(gòu)件排板是企業(yè)制定生產(chǎn)計劃的前提，而大多數(shù)預(yù)制構(gòu)件生產(chǎn)企業(yè)目前采用人工排板的方式，不僅不利于生產(chǎn)計劃的編排，還存在工作效率低、模臺利用率低的問題。開展預(yù)制構(gòu)件自動排板算法的研究對于企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本具有重要意義。

平面排板問題可以劃分為平面填充問題和平面切割問題。預(yù)制構(gòu)件排板問題作為典型的平面填充問題具有間距約束、鋼筋交叉和超邊界約束的特點。在間距約束方面，鄭彥[1]等研究了貨物擺放問題，貨物在倉庫中擺放時需要留有取出貨物的通道空間；在超邊界約束方面，張思[2]研究了艦載機自動排布方法，艦載機在航母甲板上排布只需要考慮艦載機的支撐輪不能超出甲板，其他部分可以超出甲板尺寸。在平面切割問題方面，蔡小娜[3]等考慮了玻璃下料問題的“一刀切”等排板方式的約束條件，并提出相應(yīng)的改進算法；管衛(wèi)利[4]等考慮了帶剪刃長度約束的約束條件，并對算法進行了改進。但是，針對矩形預(yù)制構(gòu)件排板算法方面的研究比較少，主要因為生產(chǎn)排板時需要考慮的約束條件比較多，建立排板優(yōu)化模型比較困難。

本文結(jié)合矩形預(yù)制構(gòu)件實際生產(chǎn)的要求，分析矩形預(yù)制構(gòu)件排板時要考慮的約束條件，建立一種考慮間距約束、鋼筋交叉和超邊界約束的矩形預(yù)制構(gòu)件排板優(yōu)化模型，并基于該排板優(yōu)化模型對矩形預(yù)制構(gòu)件自動排板算法開展研究，提出了一種面向多約束矩形預(yù)制構(gòu)件的自動排板技術(shù)。

1 預(yù)制構(gòu)件排板問題

預(yù)制構(gòu)件由鋼筋和混凝土構(gòu)成，相較于其他產(chǎn)品的最大特點在于存在出筋現(xiàn)象，如圖1所示，其中，預(yù)制構(gòu)件長度和寬度用l和w表示，鋼筋伸出部分長度分別用l'、l''和w'、w''表示。

圖1 預(yù)制構(gòu)件出筋示意圖

在實際生產(chǎn)的時候，預(yù)制構(gòu)件由四邊的模具進行成型加工，在劃線之后利用磁力盒將模具固定在模臺上面，所以，在各個預(yù)制構(gòu)件之間需要具有一定的間距用于放置磁力盒。

部分企業(yè)考慮到盡可能實現(xiàn)模臺利用率的最大化，要求伸出部分鋼筋可以交叉；也有部分企業(yè)考慮到鋼筋交叉會導(dǎo)致生產(chǎn)難度增大，不利于鋼筋網(wǎng)片加工機的使用也不利于生產(chǎn)進度的控制，要求鋼筋不能交叉。所以，在企業(yè)實際生產(chǎn)中，不同企業(yè)存在鋼筋交叉和鋼筋不交叉兩種需求，鋼筋交叉如圖2所示。

圖2 鋼筋交叉示意圖

同樣，對于部分企業(yè)而言，希望通過超邊界排板實現(xiàn)鋼筋出筋部分伸出模臺，要求通過超邊界排板實現(xiàn)模臺利用率最大化；也有部分企業(yè)在設(shè)計蒸養(yǎng)窯的時候未考慮超邊界排板，蒸養(yǎng)窯預(yù)留空間不夠，不具備超邊界排板的條件。所以在企業(yè)實際生產(chǎn)中存在是否超邊界排板兩種需求。

2 預(yù)制構(gòu)件排板優(yōu)化模型

通過對預(yù)制構(gòu)件排板問題的描述我們可以發(fā)現(xiàn)，限制預(yù)制構(gòu)件排板的主要約束條件有：間距約束、鋼筋交叉和超邊界約束。由于預(yù)制構(gòu)件以矩形件為主，建立矩形預(yù)制構(gòu)件排板優(yōu)化模型對于預(yù)制構(gòu)件自動排板算法的研究具有重要意義。

2.1 目標(biāo)函數(shù)

預(yù)制構(gòu)件生產(chǎn)企業(yè)以所生產(chǎn)的混凝土方量作為產(chǎn)能評估的主要指標(biāo)，混凝土方量的提升則意味著產(chǎn)能的提升，而鋼筋只作為輔助原料，不作為產(chǎn)能評估的依據(jù)。所以，在建立矩形預(yù)制構(gòu)件排板優(yōu)化模型時應(yīng)該與企業(yè)生產(chǎn)實際相結(jié)合，把混凝土方量最大化作為排板優(yōu)化模型的目標(biāo)。此時生產(chǎn)的目標(biāo)可以理解為：在單位模臺上所生產(chǎn)的預(yù)制構(gòu)件的混凝土方量越多則經(jīng)濟效益越高。

若以vk表示第i塊模臺上預(yù)制構(gòu)件各自的方量，以Li和Wi分別表示該模臺的長度和寬度，以H表示該類型預(yù)制構(gòu)件的厚度，則第i塊模臺的利用率ηi為：

由于在計算模臺的方量時采用的是預(yù)制構(gòu)件的厚度H，所以能夠?qū)⒃撃Ｅ_的利用率采用面積比值進行表示，以lk和wk分別表示第k塊預(yù)制構(gòu)件混凝土部分的長度和寬度，利用率ηi為：

所以，排板優(yōu)化模型的目標(biāo)函數(shù)為：

2.2 約束條件

排板問題的約束條件如下：

1）各個預(yù)制構(gòu)件不能重疊；

2）各個預(yù)制構(gòu)件之間的生產(chǎn)間距大于等于規(guī)定的生產(chǎn)間距D；

3）各個預(yù)制構(gòu)件混凝土部分不能超出模臺邊界；

4）預(yù)制構(gòu)件的伸出鋼筋是否交叉可以分為兩種情況；

5）預(yù)制構(gòu)件的伸出鋼筋部分能否超出模臺邊界分為兩種情況。

綜上所述，根據(jù)鋼筋是否交叉和是否超邊界可以分為四種情況，分別討論四種情況下的數(shù)學(xué)模型。

1）鋼筋未交叉且未超邊界建立數(shù)學(xué)模型為：

2）鋼筋交叉且未超邊界

模臺的數(shù)學(xué)模型同式(6)和式(7)，建立預(yù)制構(gòu)件的數(shù)學(xué)模型為：

3）鋼筋未交叉且超邊界

4）鋼筋交叉且超邊界

3 預(yù)制構(gòu)件排板算法

3.1 排板算法原理

對于每種待排板的模臺或者模臺的待排板部分，規(guī)定其上的所有預(yù)制構(gòu)件都必須按“左下角原則（每種預(yù)制構(gòu)件始終以模臺剩余部分的左下角位置開始排板）”依次排板。結(jié)合矩形預(yù)制構(gòu)件的特點對該排板算法進行說明。

在選取待排預(yù)制構(gòu)件時可以通過交貨時間優(yōu)先、同一項目優(yōu)先和交貨地點優(yōu)先三個影響因素選擇待排預(yù)制構(gòu)件，以模臺利用率最大化為目標(biāo)，考慮多種約束條件進行排板。

在選取預(yù)制構(gòu)件進行排板時，由經(jīng)驗可知，面積大的預(yù)制構(gòu)件優(yōu)先排板可以提高模臺的利用率，所以將待排預(yù)制構(gòu)件按照面積由大到小進行排序，依次選取面積最大的待排預(yù)制構(gòu)件在模臺上排板。

若預(yù)制構(gòu)件的長度大于模臺的寬度，則該預(yù)制構(gòu)件只能水平放置，則對于模臺剩余部分有如圖3所示兩種劃分方式，豎直劃分為P1和P2兩個部分或水平劃分為P3和P4兩個部分。

圖3 兩種劃分方式示意圖

若預(yù)制構(gòu)件的長度小于模臺的寬度，則該預(yù)制構(gòu)件不僅能水平放置也可以豎直放置，則對于模臺剩余部分有如圖4所示四種劃分方式：水平放置后豎直劃分（P1和P2），水平放置后水平劃分（P3和P4），豎直放置后豎直劃分（P5和P6），豎直放置后水平劃分（P7和P8）。

圖4 四種劃分方式示意圖

3.2 排板算法詳細(xì)步驟

采用連續(xù)迭代排板算法實現(xiàn)預(yù)制構(gòu)件的優(yōu)化排板設(shè)計。

該算法的運行流程如圖5所示。

在選取第一塊預(yù)制構(gòu)件排板后，可以對模臺剩余部分通過不同方式進行劃分，分別對不同劃分方式得到的模臺剩余部分進行排板，相同劃分方式得到的模臺剩余部分不可選用同一塊待排預(yù)制構(gòu)件，即如果在P1排板時選用了該預(yù)制構(gòu)件則P2不可再次選用。采用迭代思想依次劃分依次排板，得到該模臺在同一劃分方法下的不同排板方案，分別利用目標(biāo)函數(shù)計算各排板方案的模臺利用率，將模臺利用率最大的排板方案認(rèn)為該模臺在該劃分方法的排板方案。

同理，分別計算各劃分方法下不同方案的模臺利用率，比較各劃分方法的模臺利用率，將模臺利用率最大的排板方案作為最終該模臺的排板方案。

（其中，ηij表示第i塊模臺的第j種劃分方法的利用率。）

圖5 排板算法的流程圖

此時保證了第i塊模臺的利用率ηi最大化，若要使目標(biāo)函數(shù)η最大化，只需要使各模臺利用率最大化即可。

依次結(jié)合模臺或模臺剩余部分的尺寸約束條件和預(yù)制構(gòu)件的排板算法優(yōu)選出各模臺的排板方案，每確定一個模臺的排板方案便在待排預(yù)制構(gòu)件中剔除該排板方案中的預(yù)制構(gòu)件，直至當(dāng)前模臺不能繼續(xù)排板預(yù)制構(gòu)件或者待排預(yù)制構(gòu)件數(shù)量為零為止。

4 系統(tǒng)開發(fā)及實例驗證

基于上述多約束下矩形預(yù)制構(gòu)件自動排板算法，在Microsoft Visual Studio環(huán)境下編寫代碼開發(fā)完成預(yù)制構(gòu)件自動排板系統(tǒng)。該自動排板系統(tǒng)的軟件界面如圖6～圖8所示，主要可以實現(xiàn)自動排板、自動匹配和手動排板三個功能。

在模臺設(shè)計功能下可以勾選是否超邊界排板和鋼筋是否交叉排板，以確定預(yù)制構(gòu)件自動排板時調(diào)用相應(yīng)算法模型對數(shù)據(jù)進行優(yōu)化。在選擇預(yù)制構(gòu)件功能下可以勾選供貨時間優(yōu)先、同一項目優(yōu)先、供貨地點優(yōu)先，根據(jù)生產(chǎn)計劃調(diào)整待排預(yù)制構(gòu)件順序，從而得到相應(yīng)的排板方案。

圖6 系統(tǒng)主界面

圖7 模臺設(shè)計界面

圖8 選擇預(yù)制構(gòu)件界面

以濟南某建筑公司2018年7月1日實際生產(chǎn)數(shù)據(jù)為例，通過開發(fā)的自動排板系統(tǒng)對該自動排板技術(shù)進行驗證。該企業(yè)當(dāng)天共生產(chǎn)51塊預(yù)制構(gòu)件，累計方量16.758m3，實際生產(chǎn)使用了14塊模臺，預(yù)制構(gòu)件的基本數(shù)據(jù)如表1所示。

表1 預(yù)制構(gòu)件的基本數(shù)據(jù)（單位：mm）

表1 （續(xù)）

實際生產(chǎn)時人工排板結(jié)果如表2所示，模臺的長寬分別是L=9000mm，W=4000mm，此時模臺的利用率為：

表2 人工排板結(jié)果

由于該企業(yè)實際生產(chǎn)時允許鋼筋交叉和超邊界約束，所以采用鋼筋交叉且超邊界模型對預(yù)制構(gòu)件數(shù)據(jù)和模臺數(shù)據(jù)進行優(yōu)化，經(jīng)自動排板系統(tǒng)完成排板，其結(jié)果如表3所示。

表3 系統(tǒng)自動排板的排板結(jié)果

由系統(tǒng)自動排板只需12塊模臺即可完成對于這51塊預(yù)制構(gòu)件的自動排板，此時模臺的利用率為：

可見，系統(tǒng)自動排板相對于人工排板，模臺的利用率提高了9.3%。同時，系統(tǒng)自動排板相對于人工排板可以節(jié)省大量的排板時間，有效地提高了排板的工作效率。

5 結(jié)語

結(jié)合矩形預(yù)制構(gòu)件實際生產(chǎn)的要求，分析出矩形預(yù)制構(gòu)件排板時要考慮的約束條件，建立了考慮多約束的優(yōu)化模型并研究了自動排板算法，提出了一種面向多約束下矩形預(yù)制構(gòu)件的自動排板技術(shù)并開發(fā)了矩形預(yù)制構(gòu)件自動排板系統(tǒng)。自動排板系統(tǒng)的應(yīng)用有效提高了模臺利用率和排板效率。通過自動排板技術(shù)實現(xiàn)了模臺信息與預(yù)制構(gòu)件信息的一一對應(yīng)，打通了企業(yè)的信息鏈，為后續(xù)生產(chǎn)過程中的生產(chǎn)計劃自動制定、劃線機自動劃線、構(gòu)件質(zhì)量追溯和生產(chǎn)過程監(jiān)控提供了數(shù)據(jù)支持。