復(fù)雜下料工藝約束下的二維不規(guī)則零件優(yōu)化排樣方法

吳電建 張三強(qiáng) 楊光友

1.湖北工業(yè)大學(xué)農(nóng)機(jī)工程研究設(shè)計(jì)院,武漢,4300682.湖北省農(nóng)機(jī)裝備智能化工程技術(shù)研究中心,武漢,430068

0 引言

二維不規(guī)則零件的下料問題屬于典型的NPC問題[1-2]。目前,二維不規(guī)則零件優(yōu)化排樣方法已有較多的研究成果。文獻(xiàn)[3-4]用不規(guī)則零件圖形的外接包絡(luò)矩形替代其外形輪廓來降低零件圖形定位的計(jì)算復(fù)雜度,快速獲得排樣方案,但這種方法易造成大量碎化廢料,導(dǎo)致原材料利用率不高。文獻(xiàn)[5-6]借助圖形柵格技術(shù)實(shí)現(xiàn)不規(guī)則零件圖形的像素化表達(dá),通過柵格占空來描述零件圖形輪廓,但這種方法受限于圖形輪廓大小和像素精度尺寸,且算法計(jì)算的內(nèi)存開銷大,難以保證時(shí)間效率。為保留零件圖形輪廓特征,文獻(xiàn)[7-8]引入臨界多邊形算法來實(shí)現(xiàn)零件圖形間位置關(guān)系向點(diǎn)包含關(guān)系的轉(zhuǎn)換,但隨著零件數(shù)量和旋轉(zhuǎn)角度的增多,算法復(fù)雜度增加,計(jì)算時(shí)間延長(zhǎng)。文獻(xiàn)[9-10]提出的零件圖形間碰撞檢測(cè)算法可快速完成零件定位,但算法易陷入局部?jī)?yōu)化,導(dǎo)致排樣方案的原材料利用率波動(dòng)較大。上述優(yōu)化排樣方法針對(duì)原材料、二維不規(guī)則零件等常見約束,尋找原材料利用率更高的排樣方案,但這些排樣方案中的零件雜亂排布。為滿足原材料自動(dòng)送料、機(jī)床連續(xù)切割、零件自動(dòng)碼垛等復(fù)雜下料工藝約束,需人工調(diào)整部分零件位置來構(gòu)造出零件按某種規(guī)律排布的排樣方案,導(dǎo)致現(xiàn)有二維不規(guī)則零件下料生產(chǎn)線出現(xiàn)原材料利用率不高、作業(yè)效率較低等問題。因此,為在提高原材料利用率的同時(shí),保證機(jī)床連續(xù)切割和零件自動(dòng)碼垛的作業(yè)效率,本文針對(duì)下料生產(chǎn)線的復(fù)雜下料工藝約束開展二維不規(guī)則零件優(yōu)化排樣研究。

1 問題描述和數(shù)學(xué)建模

1.1 問題描述

圖1所示為下料生產(chǎn)線上二維不規(guī)則零件下料的主要生產(chǎn)流程及優(yōu)化排樣方法。下料生產(chǎn)線通過原材料自動(dòng)送料、機(jī)床連續(xù)切割和零件自動(dòng)碼垛,實(shí)現(xiàn)零件的自動(dòng)分離和庫(kù)存。

圖1中,下料生產(chǎn)線的3種加工設(shè)備及其工序如下:工序1,送料整平機(jī)完成金屬卷材的自動(dòng)送料、拉直和整平,為后續(xù)工序提供原材料;工序2,數(shù)控切割機(jī)床在指定加工區(qū)域內(nèi)連續(xù)切割,使所需零件從金屬板材上分離;工序3,自動(dòng)碼垛機(jī)定時(shí)定點(diǎn)抓取已分離的零件,并將其轉(zhuǎn)移到臨時(shí)庫(kù)存區(qū)內(nèi),實(shí)現(xiàn)零件的自動(dòng)碼垛。

上述3道工序的下料工藝約束給出了二維不規(guī)則零件下料的優(yōu)化排樣方法及其主要步驟:

(1)分析并提取原材料、二維不規(guī)則零件和下料工藝等約束信息和下料生產(chǎn)優(yōu)化目標(biāo),建立下料生產(chǎn)線的二維不規(guī)則零件下料問題數(shù)學(xué)模型。

(2)針對(duì)該模型設(shè)計(jì)一種基于排樣單元的優(yōu)化排樣算法,構(gòu)造滿足上述所有約束條件的多種排樣方案,并基于最大化原材料利用率,優(yōu)化得到本次送料整平機(jī)上的卷材規(guī)格和對(duì)應(yīng)的排樣方案。

(3)基于優(yōu)選出的排樣方案拆分出對(duì)應(yīng)的重復(fù)單元,計(jì)算出自動(dòng)碼垛機(jī)抓取零件的位置點(diǎn)和數(shù)量等數(shù)據(jù)信息。通過優(yōu)化排樣方法構(gòu)造的排樣方案智能決策并控制下料生產(chǎn)線的主要生產(chǎn)流程。

1.2 數(shù)學(xué)建模

1.2.1符號(hào)定義

數(shù)學(xué)模型中所使用到的變量符號(hào)定義如表1所示。

表1 變量符號(hào)表

1.2.2數(shù)學(xué)模型

基于對(duì)下料生產(chǎn)線上二維不規(guī)則零件下料問題的描述,建立該類問題的數(shù)學(xué)模型:

(1)

s.t.Wc=Wj

(2)

Lc=Sright_x

(3)

mbi≥di

(4)

Ωu∩Ωv=?u,v=1,2,…,n

(5)

?Ωi∈Ω(Lc,u,Wc,u)

(6)

Lc-lleft=Lc,u

(7)

Wc-2wleft=Wc,u

(8)

Ωi+δ=Ωi,u

(9)

S=mU

(10)

其中,式(1)表示最大化原材料利用率f(S)為優(yōu)化目標(biāo);式(2)、式(3)是原材料約束,分別表示本次下料生產(chǎn)可選的卷材寬度和所需的卷材長(zhǎng)度;式(4)是零件約束,表示本次下料得到的每種零件量滿足零件的需求量;式(5)是零件約束,表示任意2個(gè)零件的圖形輪廓不能相交;式(6)是原材料和零件間的關(guān)聯(lián)約束,表示所有零件圖形輪廓必須在原材料區(qū)域內(nèi);式(7)、式(8)表示為保證零件從原材料的順利切割分離,應(yīng)通過預(yù)留原材料邊界實(shí)現(xiàn)貼邊零件的切斷;式(9)表示機(jī)床刀具切割應(yīng)預(yù)留出刀具厚度的等距量,以保證機(jī)床切割加工得到的零件尺寸精度;式(10)表示任意一種排樣方案均由m個(gè)排樣單元組成,通過構(gòu)造重復(fù)的排樣單元來滿足機(jī)床連續(xù)切割加工和零件自動(dòng)碼垛的工藝約束。

2 優(yōu)化排樣算法設(shè)計(jì)

2.1 圖形預(yù)處理

為滿足下料生產(chǎn)線機(jī)床切割加工的工藝約束即式(7)～式(9),在排樣設(shè)計(jì)時(shí)對(duì)當(dāng)前下料卷材和零件的圖形進(jìn)行預(yù)處理,如圖2所示。在卷材圖形長(zhǎng)度、寬度方向上分別增加留邊量lleft和wleft,獲得當(dāng)前卷材的可排樣區(qū)域即圖2a中的紅色區(qū)域;在每種零件圖形輪廓上增加搭邊量δ,得到該零件在卷材上排樣時(shí)的真實(shí)圖形輪廓即圖2b的紅色區(qū)域。

(a)卷材可排樣區(qū)域

2.2 零件圖形間碰撞算法

為滿足零件圖形互不相交的約束(式(5)),實(shí)現(xiàn)零件間的定位,并保證零件排樣的緊密性,基于沖裁件碰撞算法[11-12]設(shè)計(jì)了一種零件圖形間碰撞算法,具體流程如圖3所示。算法主要步驟如下:

圖3 零件圖形間碰撞算法流程圖

(1)選取2個(gè)待排樣的零件,預(yù)處理它們的圖形輪廓,得到其真實(shí)碰撞輪廓。

(2)基于零件的初始位置關(guān)系判斷零件間是否存在水平重合,若存在,轉(zhuǎn)到步驟(3);若不存在,轉(zhuǎn)到步驟(8)。

(3)如圖4a所示,在水平碰撞示意圖中,先提取左側(cè)零件右半部分點(diǎn)集{pl,1,pl,2,…,pl,n},其中,pl,1、pl,n分別為左側(cè)零件點(diǎn)集中縱坐標(biāo)最大的點(diǎn)和縱坐標(biāo)最小的點(diǎn)。

(a)水平碰撞 (b)垂直碰撞

(4)再提取右側(cè)零件左半部分點(diǎn)集{pr,1,pr,2,…,pr,n},其中,pr,1、pr,n分別為右側(cè)零件點(diǎn)集中縱坐標(biāo)最大的點(diǎn)和縱坐標(biāo)最小的點(diǎn)。

(5)將點(diǎn)pl,1和點(diǎn)pr,1中縱坐標(biāo)較小的點(diǎn)作為碰撞區(qū)域最高點(diǎn)pr,1,將點(diǎn)pl,n和點(diǎn)pr,n中縱坐標(biāo)較大的點(diǎn)作為碰撞區(qū)域最低點(diǎn)pr,n。

(6)以最高點(diǎn)pl,1和最低點(diǎn)pr,n為起點(diǎn),向?qū)?cè)零件輪廓做水平射線,得到交點(diǎn)pr,e和pl,e,確定水平碰撞區(qū)域pl,1pl,epr,npr,e。

(7)在水平碰撞區(qū)域內(nèi),分別計(jì)算左側(cè)碰撞點(diǎn)集{pl,1,pl,2,…,pl,e}中每個(gè)點(diǎn)到右側(cè)零件輪廓的水平距離和右側(cè)碰撞點(diǎn)集{pr,e+1,pr,e+2,…,pr,n}中每個(gè)點(diǎn)到左側(cè)零件輪廓的水平距離,將最短水平距離作為零件間的水平碰撞距離,并轉(zhuǎn)到步驟(13)。

(8)如圖4b所示,在垂直碰撞示意圖中,提取上側(cè)零件的下半部分點(diǎn)集{pu,1,pu,2,…,pu,n},其中,pu,1、pu,n分別為上側(cè)零件點(diǎn)集中橫坐標(biāo)最大的點(diǎn)和最小的點(diǎn)。

(9)提取下側(cè)零件上半部分點(diǎn)集{pd,1,pd,2,…,pd,n},其中,pd,1、pd,n分別為下側(cè)零件點(diǎn)集中橫坐標(biāo)最大的點(diǎn)和橫坐標(biāo)最小的點(diǎn)。

(10)將點(diǎn)pu,1和點(diǎn)pd,1中橫坐標(biāo)值較小的點(diǎn)作為碰撞區(qū)域最右點(diǎn)pu,1,將點(diǎn)pu,n和點(diǎn)pd,n中橫坐標(biāo)值較大的點(diǎn)作為碰撞區(qū)域最左點(diǎn)pd,n。

(11)分別以最右點(diǎn)pu,1和最左點(diǎn)pd,n為起點(diǎn),向?qū)?cè)零件輪廓做垂直射線,得到交點(diǎn)pd,e和pu,e,確定垂直碰撞區(qū)域pu,1pu,epd,npd,e。

(12)在垂直碰撞區(qū)域內(nèi),分別計(jì)算上側(cè)碰撞點(diǎn)集{pu,1,pu,2,…,pu,e}中每個(gè)點(diǎn)到下側(cè)零件輪廓的垂直距離和下側(cè)碰撞點(diǎn)集{pd,e+1,pd,e+2,…,pd,n}中每個(gè)點(diǎn)到上側(cè)零件輪廓的垂直距離,選取最短垂直距離作為零件間的垂直碰撞距離。

(13)獲得2個(gè)零件圖形間的碰撞距離。

2.3 排樣單元構(gòu)造方法

為滿足下料生產(chǎn)線機(jī)床連續(xù)切割和零件自動(dòng)碼垛的約束條件(式(10)),基于2.2節(jié)提出的零件圖形間碰撞算法,通過零件圖形的平移、旋轉(zhuǎn)、鏡像等操作實(shí)現(xiàn)多個(gè)零件的動(dòng)態(tài)組合,構(gòu)造多種排樣單元,如圖5所示。針對(duì)待排樣的零件,利用平移矩陣使零件圖形水平方向平移Δx、垂直方向平移Δy后,得到由2個(gè)零件組合而成的一種排樣單元,如圖5a所示;零件圖形平移和旋轉(zhuǎn)后,得到一種排樣單元,如圖5b所示;零件圖形平移、旋轉(zhuǎn)、水平鏡像、垂直鏡像后,得到兩種排樣單元,如圖5c所示。因此,通過控制零件圖形平移量、旋轉(zhuǎn)角度和鏡像方向可得多種排樣單元,不同排樣單元可組合成多種排樣方案。

(a)零件圖形平移變換 (b)零件圖形旋轉(zhuǎn)變換 (c)零件圖形鏡像變換

排樣單元處理機(jī)床連續(xù)切割和零件自動(dòng)碼垛等復(fù)雜下料工藝約束的實(shí)現(xiàn)方法如圖6所示。針對(duì)卷材寬度和零件需求量?jī)煞N約束,基于上述排樣單元設(shè)計(jì)一種優(yōu)化排樣算法,計(jì)算排樣單元內(nèi)的決策變量(Δx,Δy,α)和排樣單元間的決策變量(x,y,m),得到由排樣單元組合而成的排樣方案。該排樣方案可拆分出機(jī)床連續(xù)切割單元,快速指導(dǎo)數(shù)控機(jī)床在板材上連續(xù)切割加工;計(jì)算出自動(dòng)碼垛每次需抓取單元的個(gè)數(shù),控制碼垛機(jī)自動(dòng)抓取固定位置點(diǎn)上已切割分離的多個(gè)零件。基于排樣單元構(gòu)造的排樣方案適用于機(jī)床連續(xù)切割和零件自動(dòng)碼垛的工藝約束,提高下料生產(chǎn)的作業(yè)效率。

圖6 排樣單元處理復(fù)雜下料工藝約束的實(shí)現(xiàn)方法

2.4 基于排樣單元的二維不規(guī)則零件優(yōu)化排樣算法

為構(gòu)造高利用率的卷材排樣方案,并滿足下料生產(chǎn)線的復(fù)雜工藝約束,設(shè)計(jì)了一種基于排樣單元的二維不規(guī)則零件優(yōu)化排樣算法,其流程如圖7所示。初始化多種卷材和二維不規(guī)則零件圖形和數(shù)據(jù)信息,利用2.1節(jié)介紹的方法預(yù)處理待下料的卷材和零件圖形后,得到卷材可排樣區(qū)域和零件實(shí)際排樣輪廓;結(jié)合2.2節(jié)提出的零件圖形間碰撞算法和2.3節(jié)設(shè)計(jì)的排樣單元構(gòu)造方法,設(shè)計(jì)出多種排樣單元,滿足下料生產(chǎn)線的工藝約束,簡(jiǎn)化下料問題的復(fù)雜度;針對(duì)每種規(guī)格的卷材,以卷材左下角為排樣起點(diǎn),依次利用每種排樣單元在卷材寬度方向進(jìn)行排布,再沿卷材長(zhǎng)度方向進(jìn)行重復(fù)排列,直到滿足零件需求量為止。以最大化卷材利用率為優(yōu)化目標(biāo),通過設(shè)計(jì)的優(yōu)化排樣算法搜索、迭代和尋優(yōu)后,找出一種排樣方案,并確定當(dāng)前下料所需的卷材規(guī)格。

圖7 基于排樣單元的二維不規(guī)則零件優(yōu)化排樣算法流程圖

3 算例驗(yàn)證

某企業(yè)生產(chǎn)線常見的8種下料零件的數(shù)據(jù)如表2所示。假設(shè)卷材留邊值為5 mm,零件搭邊值為2 mm;該企業(yè)通常存放寬度0.8 m、1.0 m和1.2 m的卷材。通過算例對(duì)比分析不同優(yōu)化排樣方法構(gòu)造的排樣方案對(duì)應(yīng)的卷材利用率來驗(yàn)證所提方法的可行性和有效性。

表2 8種下料零件數(shù)據(jù)信息

結(jié)合下料生產(chǎn)信息,分別利用本文提出的優(yōu)化排樣方法、文獻(xiàn)[2]的優(yōu)化排樣算法和商用軟件FormingSuite在指定規(guī)格卷材上進(jìn)行零件優(yōu)化排樣設(shè)計(jì)。3種方法針對(duì)每種零件構(gòu)造的排樣方案的卷材利用率如表3所示。

表3 不同排樣方案的卷材利用率

在表3中,加粗的數(shù)字表示本文方法的卷材利用率高于另外兩種方法的卷材利用率。對(duì)比分析表3橫向數(shù)據(jù)可知,本文方法在3種寬度卷材上進(jìn)行零件排樣時(shí)的卷材利用率多數(shù)都高于另外兩種方法;分析表3縱向數(shù)據(jù)可知,本文方法在同一寬度卷材上進(jìn)行零件排樣設(shè)計(jì)時(shí)的卷材利用率多數(shù)都高于另外兩種方法;對(duì)于所有零件,本文方法在3種不同寬度卷材的平均材料利用率均高于另外兩種方法。因此,本文方法在處理二維不規(guī)則零件下料問題上具有可行性和有效性。

為更加直觀地對(duì)比3種方法的排樣效果,表4給出了表2中的零件1在3種寬度卷材上的排樣方案。本文方法在寬度0.8 m和1.2 m卷材上的利用率均高于另外兩種方法;在寬度1.0 m卷材上的利用率略低于商用軟件FormingSuite,但高于文獻(xiàn)[2]的排樣算法。在排樣方案上,本文方法考慮多種工藝約束,構(gòu)造出更多的排樣單元,增加了二維不規(guī)則零件在卷材上的排樣方案,提高了排樣解質(zhì)量。

表4 零件1在3種寬度卷材上的排樣方案

4 結(jié)論

(1)以圖形預(yù)處理技術(shù)和零件圖形間碰撞算法為基礎(chǔ),引入排樣單元構(gòu)造方法,得到了滿足機(jī)床連續(xù)切割和零件自動(dòng)碼垛等復(fù)雜下料工藝約束的排樣單元。

(2)8種二維不規(guī)則零件的優(yōu)化排樣算例結(jié)果表明,本文方法構(gòu)造的排樣方案的卷材利用率多數(shù)高于已有算法和商用軟件,具有可行性和有效性。