張 闖，高 強(qiáng)，2*，叢玉龍，蔣興文，周 明

（1.沈陽(yáng)工程學(xué)院，遼寧 沈陽(yáng) 110136；2.沈陽(yáng)建筑大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽(yáng) 110168）

在大型工業(yè)產(chǎn)品中，如機(jī)床、輪船及飛機(jī)常常需要很多的小零件，如螺釘、螺帽、螺栓和活塞等。在零件的生產(chǎn)過(guò)程中，第一步是需要依照零件產(chǎn)品尺寸從原材料中截取初級(jí)產(chǎn)品。在這道工序中，不同的截取方案具有不同的材料利用率，而原材料的利用率（原材料截取初級(jí)產(chǎn)品的總體積與原材料體積之比）直接影響產(chǎn)品的生產(chǎn)成本。在市場(chǎng)上，零件的截面（表面）形狀是多種多樣的，有圓形、矩形等，零件的厚度（高度）尺寸也是大小不一的。在原材料尺寸固定的前提下，截取初級(jí)產(chǎn)品后產(chǎn)生的廢料最少是企業(yè)的追求。

本文以6 060 mm×2 160 mm板材加工盡可能多的橫徑為60 mm，豎徑為40 mm的正橢圓形產(chǎn)品為例，探討滿足產(chǎn)品數(shù)量要求的整體切割方案。

1 外切矩形件直接排樣

二維零件排樣問(wèn)題是近年來(lái)的研究熱點(diǎn)[1]，首先將橢圓簡(jiǎn)化為外切矩形，通過(guò)緊密切割[2]（無(wú)縫隙排列）的方式建立模型，即矩形件排樣優(yōu)化。將原材料水平放置，以原材料左下角為坐標(biāo)原點(diǎn)（0，0），以長(zhǎng)邊所在直線為x軸，短邊所在直線為y軸，建立平面直角坐標(biāo)系。但緊密切割存在橫向擺放、豎向擺放兩種情況如圖1所示。

圖1 矩形件排樣

首先若將產(chǎn)品橫向擺放，并且彼此間無(wú)縫隙緊密排列。排列到最后可能會(huì)出現(xiàn)橫向擺放不足以擺放一塊，但是豎向擺放還有余量的情況。同理豎向擺放會(huì)出現(xiàn)橫向擺放不足以擺放一塊，但是橫向擺放還有余量的情況。

對(duì)于橫向擺放，先采用從上往下逐排擺列擺放的方式，假設(shè)先將t1塊產(chǎn)品緊密橫放排列，t2塊產(chǎn)品緊密豎放排列；再?gòu)南峦现鹋排帕袛[放，將t3塊產(chǎn)品緊密豎放排列，t4塊產(chǎn)品緊密橫放排列。n為可切割的產(chǎn)品數(shù)，可建立數(shù)學(xué)模型：

同理，對(duì)于豎向擺放，可建立數(shù)學(xué)模型：

求解后結(jié)果見(jiàn)表1，最優(yōu)結(jié)果為5 454塊。

表1 矩形件排樣求解結(jié)果

2 外切矩形件優(yōu)化排樣

由于外切矩形件直接排樣在面對(duì)不同規(guī)格零件時(shí)，需要重新建立數(shù)學(xué)模型，實(shí)用性較差。故將其算法優(yōu)化[3]，增強(qiáng)算法的實(shí)用性。

將第i塊產(chǎn)品中心的坐標(biāo)與切割方向記為（xi，yi，di），其中i=∈N*，di=±1，（xi，yi）表示第i塊產(chǎn)品的中心坐標(biāo)，di=1表示第i塊產(chǎn)品的長(zhǎng)邊水平切割，di=-1表示第i塊產(chǎn)品短邊的水平切割。為了使原材料的利用率最大，只需總的產(chǎn)品所占面積最大，即可滿足切割產(chǎn)品數(shù)目最多。

在約束條件上要確保以下三點(diǎn)：

（1）任意兩塊產(chǎn)品不能重合，即橫坐標(biāo)或縱坐標(biāo)滿足式（3）兩種關(guān)系之一。

（2）每塊產(chǎn)品必須要在原材料的范圍內(nèi)，即需要同時(shí)滿足式（4）兩種關(guān)系。

（3）產(chǎn)品的總面積必須大于等于零，且不能超過(guò)原材料面積，即需要滿足式（5）的關(guān)系。

綜上，該數(shù)學(xué)模型可以表示為：

其中：i∈N*，j∈N*，i≠j，n∈N*。

求解結(jié)果為最多擺放5 454塊，與外切矩形件直接排樣相同，但建模與計(jì)算速度較外切矩形件直接排樣更快，該模型可適用于復(fù)雜的矩形切割問(wèn)題，但對(duì)于橢圓切割問(wèn)題，該方法空間利用率過(guò)低，無(wú)法滿足設(shè)計(jì)需求。

3 橢圓最小密排優(yōu)化

上述模型通過(guò)將橢圓簡(jiǎn)化為矩形，通過(guò)矩形件排樣的算法建立模型，得到了最佳的切割方式，這種模型如果是切割矩形件可以得到最優(yōu)解，但是切割橢圓由于橢圓面積僅占外接矩形面積的π/4，約為78.5%，顯然不是最優(yōu)解。而橢圓致密的排列方式一定是要使每一個(gè)橢圓盡可能地靠近，并且是按照一定規(guī)律排列，如同理想原子的排列一樣。

阿克塞爾圖早在1910年就對(duì)圓形的六角密堆積進(jìn)行了證明[4]，對(duì)于圓形而言，六角密堆積是最致密結(jié)構(gòu)，致密度為，其排列方式如圖2所示。

圖2 六角密堆積示意圖

圓的六角密堆積是平面上最有效的堆積方式，所以像橢圓這種的圓錐曲線輪廓的工件，可以根據(jù)圓的六角密堆積建立仿射坐標(biāo)系[5]，將橢圓類比成圓，進(jìn)行密堆積排列。再對(duì)上述算法進(jìn)行優(yōu)化，即可得到最優(yōu)解。

對(duì)于橢圓的密堆積排列，首先建立仿射坐標(biāo)系，該問(wèn)題不需要建立三維仿射坐標(biāo)系，在平面內(nèi)建立二維仿射坐標(biāo)系即可。即原坐標(biāo)系內(nèi)的任意一點(diǎn)（x，y）原本表示為r→=xι→+yJ→，現(xiàn)在仿射坐標(biāo)系內(nèi)（x′，y′）的坐標(biāo)表示為r→=x'ι→+y'J→=xι→+1.5yJ→。通過(guò)坐標(biāo)反變換，即可得到橢圓的密堆積排列如圖3所示。

圖3 橢圓件密堆積示意圖

橢圓件的密堆積排列與圓的密堆積排列相似，是有規(guī)律的無(wú)限排列，若不限制邊界無(wú)限排列，其致密度為90.7%。

將第一塊橢圓件貼著原板材左上角排放，則優(yōu)化后的排列方式求解算法設(shè)計(jì)思路如下：

Step1：計(jì)算奇數(shù)行的零件數(shù)。

Step2：計(jì)算偶數(shù)行的零件數(shù)。若奇數(shù)行剩余長(zhǎng)度大于橢圓半長(zhǎng)軸，偶數(shù)行零件數(shù)=奇數(shù)行零件數(shù)，若不超過(guò)a，偶數(shù)行零件數(shù)=奇數(shù)行零件數(shù)-1。

Step3：計(jì)算出總行數(shù)。

Step4：判斷奇數(shù)行和偶數(shù)行的行數(shù)。若總行數(shù)為偶數(shù)，則奇數(shù)行行數(shù)=偶數(shù)行行數(shù)-總行數(shù)/2；反之，偶數(shù)行行數(shù)-（總行數(shù)-1）/2，奇數(shù)行行數(shù)-偶數(shù)行行數(shù)+1。

Step5：計(jì)算出6層的總零件數(shù)。

Step6：找出利用率最大的方案。

求解后結(jié)果見(jiàn)表2。

表2 橢圓最小密排求解結(jié)果

板材橫向擺放的原材料利用率最大，為88.951%，排列數(shù)據(jù)見(jiàn)表3。

表3 所選方案的詳細(xì)結(jié)果

4 結(jié)束語(yǔ)

二維排樣問(wèn)題是工業(yè)原材料加工中經(jīng)常遇到的問(wèn)題，其較強(qiáng)的實(shí)用價(jià)值引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。本文根據(jù)橢圓零件排樣問(wèn)題提出了橢圓的密排結(jié)構(gòu)，對(duì)零件最優(yōu)切割方案進(jìn)行了分析與研究，以期對(duì)此項(xiàng)研究工作的開(kāi)展提供一定參考。