王石

摘要

分析制造業(yè)排樣問題可以分解為布局問題和組合優(yōu)化二類問題，矩形布局問題通過“一刀切”剪切布局算法求解并實施自動化制造過程，組合優(yōu)化問題通過極限算法和規(guī)劃算法進行求解。介紹典型計算機輔助切割排樣系統(tǒng)AutoCUT/AutoSAW在智能制造系統(tǒng)中的應(yīng)用。

【關(guān)鍵詞】排樣 矩形布局 組合優(yōu)化

1排樣問題

排樣問題也普遍被稱為開料問題，也有的行業(yè)稱之為“排版”、“下料”等，本文中出現(xiàn)的“開料”即與排樣屬于同一概念。廣義的排樣問題除了指工件在板料中的優(yōu)化布局外，還應(yīng)考慮各布局的下料數(shù)量，即各布局的組合優(yōu)化，因此也稱下料規(guī)劃問題。由此，制造業(yè)中常見的矩形排樣問題可以分為如圖1所示的2個子問題：

（1）矩形布局問題。

（2）組合優(yōu)化問題。

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

2.1矩形布局排樣

切割布局問題也稱為“Cutting問題”，是指在板料中優(yōu)化布局不同尺寸切割零件。切割布局算法通常提取板材的特征和零件的特征，進行組合優(yōu)化排布，從而產(chǎn)生若干零件組塊集合，切割加工時先將整料切割成零件組塊，然后再切割出零件。“一刀切”加工廣泛適合于家具、建材、玻璃等行業(yè)，其工藝特點是每次切割都將材料一分為二，得到零件組塊，對于不規(guī)則零件則再將組塊進行沖壓得到最終形狀，如此直到所有零件切割完成。

剪切布局主要適用于鋸切方式，常采用開料鋸等設(shè)備。由于鋸切一分為二的工藝特點，需要盡量采用平行走刀剪切方式，即每一步都盡可能的平行切割多次，有效減少切割方向轉(zhuǎn)換。家具板材優(yōu)先使用電子裁板鋸，每次鋸切都產(chǎn)生一個矩形工件，因此盡量采用平行線的切割工藝能夠減少換板次數(shù)，從而降低加工時間和提高設(shè)備切割效率。圖2解釋了適用于鋸切方式下的平行剪切方法，根據(jù)加工復(fù)雜度，可以設(shè)定不同搜索層次生成布局圖形，一層剪切連續(xù)切割一組即可得到最終零件，二層剪切則在一組切割完成后，轉(zhuǎn)換半成品方向，再進行一次切割，從而分兩步切割出最終毛坯，而三層切割則可能部分零件需要進行三次轉(zhuǎn)向才能切割完成，依次類推。

2.2排樣布局的組合

實際生產(chǎn)中往往不止是一個切割布局圖，而通常是一批訂單需求分解得到的批量切割任務(wù)，因此需要考慮多個開料布局和需求數(shù)量的優(yōu)化組合，使得組合后的排樣圖集合既能滿足數(shù)量需求，同時有能達到較好的全局利用率，我們將此類問題歸結(jié)為一個組合優(yōu)化問題，組合優(yōu)化的下層則是布局優(yōu)化問題。組合算法可分為極限求解和規(guī)劃求解兩種方式，極限算法是基于通常的貪心策略，組合優(yōu)化的效果一般，而規(guī)劃算法則應(yīng)用于大批量下料以及尋求最高全局利用率的場合，它通過數(shù)學(xué)方法計算最優(yōu)解，其優(yōu)化效果高于極限算法，但可能出現(xiàn)無解情況而導(dǎo)致計算失敗。

目前研究的布局組合算法是一種基于線性整數(shù)規(guī)劃方法的優(yōu)化算法。其基本思想是先產(chǎn)生足夠多的排樣布局圖數(shù)，然后列出多目標優(yōu)化方程組，通過單純形法等算法來選取最優(yōu)排樣布局的組合。本算法能夠得出問題的全局最優(yōu)解，即全局最優(yōu)排樣方案。

布局組合優(yōu)化的模型如下：

Obj： min（clxl+c2x2+"'+cnxn）

St. ailxl+ai2x2+"'+ainxn≥di

xi>0 1=1，2，…，n整數(shù)

式中：n為切割方式;ci為第i=l，2，…，n的費用;Xi為第i=l，2，…，n;aij為第j種切割方式下第i種零件的數(shù)量，是整數(shù)。

該模型只適用于一維（線材）排樣問題的求解，即時是一維排樣問題，在零件數(shù)量（m）不是很大時，只要零件的長度相對與原料長度足夠短，則模型需要處理數(shù)百萬中切割方式。具體算法實現(xiàn)時可以采用一些簡化搜索策略，減少計算量獲得近優(yōu)解。

3計算機輔助切割排樣系統(tǒng)及其在智能制造中的應(yīng)用

“AutoCUT開料專家”是專門針對工程下料排樣而設(shè)計的排樣優(yōu)化系統(tǒng)，能夠有效解決合理下料問題，高效完成零部件規(guī)劃下料和優(yōu)化排樣布局，目前主要應(yīng)用到定制家具、五金建材等行業(yè)，占有國內(nèi)超過50%的市場份額?！癆utoSAW智能鋸”則在AutoCUT求解切割優(yōu)化問題的基礎(chǔ)上，主要針對電子開料鋸進行嵌入式設(shè)計的設(shè)備智能化軟件，它能夠?qū)赑LC控制的電子開料鋸進行智能化升級，將生成的優(yōu)化排樣方案直接控制電子鋸，自動化完成優(yōu)化和切割全過程，最大幅度的節(jié)約人工、加快生產(chǎn)周期、提高材料利用率，本軟件目前裝備了國內(nèi)絕大部分電子鋸設(shè)備，是當前主流的鋸切裝備智能優(yōu)化軟件。

AutoCUT/AutoSAW在工業(yè)智能制造中有著廣泛的應(yīng)用前景。在定制家具智能制造系統(tǒng)中，智能優(yōu)化下料位于企業(yè)資源計劃（ERP）、訂單與設(shè)計系統(tǒng)（CAD）與設(shè)備制造系統(tǒng)（CAM）之間，與企業(yè)生產(chǎn)定制系統(tǒng)的數(shù)據(jù)管理（PDM）密切聯(lián)系，同時是驅(qū)動企業(yè)后續(xù)生產(chǎn)過程的第一道自動化工序。AutoCUT向上承接ERP/CAD系統(tǒng)的產(chǎn)品數(shù)據(jù)，向下提供拆解優(yōu)化后的切割方式輸出，驅(qū)動自動化設(shè)備完成下料和切割毛坯，這為實施企業(yè)制造執(zhí)行系統(tǒng)（MES）提供支撐。