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

張銳杰，高 琦，鞏高鑠

（1.山東大學(xué) 機(jī)械工程學(xué)院，濟(jì)南 250061；2.山東大學(xué) 高效清潔機(jī)械制造教育部重點(diǎn)實(shí)驗(yàn)室，濟(jì)南 250061）

0 引言

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

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

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

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

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

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

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

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

圖2 鋼筋交叉示意圖

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

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

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

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

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

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

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

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

2.2 約束條件

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

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

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

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

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

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

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

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

2）鋼筋交叉且未超邊界

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

3）鋼筋未交叉且超邊界

4）鋼筋交叉且超邊界

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

3.1 排板算法原理

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

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

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

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

圖3 兩種劃分方式示意圖

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

圖4 四種劃分方式示意圖

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

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

該算法的運(yùn)行流程如圖5所示。

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

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

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

圖5 排板算法的流程圖

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

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

4 系統(tǒng)開發(fā)及實(shí)例驗(yàn)證

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

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

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

圖7 模臺(tái)設(shè)計(jì)界面

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

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

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

表1 （續(xù)）

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

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

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

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

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

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

5 結(jié)語

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