適合“一刀切”剪切方式的矩形件排樣算法

適合“一刀切”剪切方式的矩形件排樣算法摘要:本文以滿足剪板機(jī)加工工藝要求，提高板材的利用率為出發(fā)點(diǎn),研究了大量國內(nèi)外有關(guān)矩形件排樣的各種算法，總結(jié)了適合普通剪床“一刀切”剪切方式的丁字尺算法,模擬退火算法，分層排樣算法，并給出了算法的實(shí)現(xiàn)過程，方法簡單易懂易編程，適合大規(guī)模矩形件排樣,能提高材料利用率和下料效率,期待這些排樣算法能為進(jìn)行矩形排樣的學(xué)者和從事生產(chǎn)實(shí)踐的技術(shù)人員提供參考價(jià)值。關(guān)鍵詞:一刀切排樣丁字尺算法模擬退火算法在航空航天領(lǐng)域中各種復(fù)合材料和板材的性能獨(dú)特，而且應(yīng)用廣泛，價(jià)格昂貴，下料是零件加工的首道工序,是浪費(fèi)的源頭，也可以說是節(jié)約成本的起點(diǎn)。因此如何進(jìn)行板材排樣下料，以減少廢料、降低成本是航空業(yè)迫切需要解決的問題。矩形件排樣是指在給定的矩形板材上將一系列矩形零件按最優(yōu)方式進(jìn)行排布，以使材料的利用率達(dá)到最高。矩形件排樣優(yōu)化問題是具有最高計(jì)算復(fù)雜度的一類問題——NP完全問題。對于NP完全問題，國內(nèi)外不少學(xué)者也進(jìn)行了大量的研究,至今未找到最優(yōu)算法，因而只能采用有效的近似算法求解。曹炬提出了背包算法，能夠快速地找到近似最優(yōu)解。賈志欣提出了最低水平線排放算法與模擬退火算法相結(jié)合的方法Jakobs最早提出了遺傳算法,但是這些方法不適用于“一刀切”的矩形件排樣。1定義設(shè)排樣所用的板材的長為L、寬為W,板材的數(shù)量足以排下所有要排的矩形件。待排矩形件簡稱樣件,排樣所用原材料稱板材，待排件數(shù)量記作n,每個(gè)樣件記為Ri(i=1,2,…,n)。矩形件排樣問題通常是指將一系列矩形零件R=(R1,R2,…,Rn)排布在一寬為W,長(高)為L的矩形板材P上，使得排放區(qū)域的廢料盡可能少，并要滿足以下約束：(1)Ri、Rj互不重疊,iWj,i,j=1,2,…,n(2)Rt旨?jí)蚯冶仨毞旁赑內(nèi)」=1,2,…,n(3滿足一定工藝要求。2算法任何一種優(yōu)越的算法都是為了更好地滿足生產(chǎn)需求，單純考慮材料的利用率，就會(huì)增加零件排樣的復(fù)雜度，影響下料的時(shí)間，所以，對于排樣算法的研究，就要兼顧材料利用率，又要考慮下料的效率，同時(shí)也要符合加工設(shè)備的工藝要求，下面介紹幾種符合剪板機(jī)“一刀切”剪切方式的算法。丁字尺法為提高生產(chǎn)效率,要求在一塊板材上下料的矩形件不超過3種(見圖1),直線TB,MR將矩形板材分成三塊,分別為S1,S2,S3。對于大型企業(yè)的大規(guī)模矩形件生產(chǎn)加工效果比較好，能夠加快工人的下料效率,可在生產(chǎn)中推廣應(yīng)用。數(shù)學(xué)模型設(shè)板材長和寬分別為L、鞏有N種零件，其長、寬、數(shù)量分別為li、Wi和ni(1<i<N),ni為一個(gè)很大的數(shù)目。每一行(列)上的零件只能橫放或者豎放，假設(shè)板材的數(shù)量是足夠的。將一個(gè)矩形件(li,Wi)看作(li,Wi)和(Wi,li)兩種零件考慮,且有l(wèi)i+N=Wi。式中x,y是li和lj的函數(shù)，所以目標(biāo)函數(shù)的決策變量是li、lj和lk。對模型的搜索算法求解步驟(1)對整塊板材利用搜索算法，尋找余料最少的零件組合。(2)設(shè)定一個(gè)能夠接受的材料利用率回詁,當(dāng)零件組合后的利用率大于ratio,則接受組合，否則轉(zhuǎn)下一步。(3)當(dāng)任意零件組合的利用率都小于ratio,根據(jù)利用率大小,可以將板材利用二分法縱向分成小塊。(4)對分塊后的小塊板材繼續(xù)執(zhí)行(1)。十字線法該種方法同樣是在考慮材料利用率前提下，兼顧生產(chǎn)時(shí)下料的效率。通過劃十字線將第一塊板材分成A、B、C、D四個(gè)部分(見圖2),從板材的左下角出發(fā),隨著P(x,y)的變