啟發(fā)式開料算法

1、開料介紹以及啟發(fā)式算法研究目前針對PCB行業(yè)沒有存在可以異形拼版的軟件。但是有部分軟件可以滿足 此功能都是應用在其他的行業(yè)，如果鋼材切割，玻璃。五金之類的行業(yè)，這個 些行業(yè)與PCB的拼版要求有很多工藝上的不一致。比如在鋼材比較注重實際的 利用率，玻璃行業(yè)在留下余料的時候需要考慮加工上的一些可行性。還有就是 卷材行業(yè)有也類似應用。下面針對啟發(fā)式算法做些了初步的探討算法分析問題說明:一般的開料算法可以簡單的表示成如下數學語言：開料問題是尋找平面最優(yōu)布局的優(yōu)化問題，即將一系列二維不規(guī)則零件 P1， P2,Pn合理地排放在原料板B中，使材料的利用率（使用面積總和/占用 得原料板面積）最高，并滿足下面的

2、約束條件；1）料Pi，Pj互不重疊：i，j = l，2，n。2）料Pi必須放在原料板B中：i = 1，2，n。3）滿足一定的排樣要求。4）滿足加工的便捷以及可能性。開料問題可以從兩個方面加以說明，一個是開料過程中的幾何問題，主要是針 對規(guī)則或者不規(guī)則形狀的零件，如何確定物料的最佳排放位置，檢測物料位置 的合理性以及相關算法。另一個是物料的調度問題，即如何從參加物料的物料庫中選出最優(yōu)的物料零件， 如何得到一個優(yōu)化的物料排樣順序。無論是幾何問題還是調度問題，都是非常 復雜的問題。這種復雜性一方面來源于物料形狀的不規(guī)則性，同時也與參與物 料零件的多樣性以及零件的批量、生產周期、排樣方向性要求等有關。

3、這些因 素相互沒有明確邏輯關系，也很難達到一個預期的全局最優(yōu)解。在很多情況下， 得到的結果都是局部最優(yōu)解或者是次優(yōu)解，當然如果只是針對PCB行業(yè)，在物 料的多樣性比其他的開料可能相對比較簡單些，一般不會有太多的料需要進行 一起拼版，一般針對開料優(yōu)化搜索算法有啟發(fā)式搜索算法、人工神經網絡算法、 模擬退火算法、遺傳算法或者他們的組合來解決開料問題。也有這些算法的結 果進行比較與分析，以尋求一種最好的優(yōu)化算法。然而，研究結果表明這些開 料算法的開料效率運行時間極長，利用率沒有手工開料的高。也有開始從料的 形狀著手，通過求解任意多邊形的臨界多邊形（耶?）來研究開料問題。目前的NFP算法大都只能計算兩個

4、凸多邊形或者一個凸多邊形和一個凹多邊形的臨界 多邊形。而對于兩個凹多邊形的臨界多邊形問題，算法沒有很好的解決人工開料讓我們來看看人工在開料是如何考慮的：當人手工排樣時，需要估計出最佳狀態(tài)，然后估計料的最佳組合，然后以此為 模式不斷的排放零件到板材上。從而實現一種零件的優(yōu)化排樣。在此之前已經 將加工需要處理的問題（如在有無法開料的情況，計算出來的利用率再高無法 用于實際的生產也是沒有任何意義的）考慮進去了考慮策略針對上述問題，一般在開料的算法搜索策略上可有如下方面的考慮：針對利用率針對加工便捷，包括開料的便捷。如果是異形，考慮單個料的優(yōu)化組合如果是異形，考慮多個料的優(yōu)化組合這樣就可以使得算法能夠

5、找到一個相對優(yōu)的開料組合。根據這些分析我們可以如下處理：將各種形狀的料處理成矩形，然后按一定的方向進行排版，比如從左上或者左 下開始，所有的料盡可能的往這個方向排，依此類推，直到完成所有。針對PCB行業(yè)的加工以及現在存在的拼版模式，此類方法可以滿足大部分的硬 板在開料方面的需要，由于軟板在外型等各方面都比硬板要復雜，所以需要對 軟板的外形進行特別的處理,比如在找最小矩形時候，如何提高算法的速度已經 在開料過程中的利用率都在考慮的范疇內。在實際的PCB開料和拼版過程中，開料開出來的聯(lián)片尺寸間距和每個Panel所 需留言的電鍍邊為一常量，所以PCB的板子利用率的決定因素有二，分別為每 個Panel

6、的板材凈利用率和Panel的數量。一般在采用不同的算法和方式對后續(xù)的計算時間以及得到的解的優(yōu)劣度有 不同的結果。我們在其過程中必須將開料結合實際PCB中的問題進行參考和校 驗。得到相對最優(yōu)解。具體步驟在PCB開料的過程中有多個決定原因是工程人員在制作拼板的參考因素，我 們將這些因素考慮在二個步驟進行：Set 拼 Panel針對Panel進行大料切割Set 拼 Panel針對啟發(fā)式算法的拼板的過程可以視為在排放狀態(tài)的變化過程.啟發(fā)式搜索 的思路在于不用遍歷某一結點的所有可能后繼狀態(tài)，而是運用人的直覺經驗和 有關知識，直接構造”可能最佳的后繼狀態(tài)，并在其中選最優(yōu)的.這些經驗和 有關知識可以歸結為：

7、新拼板應與已排拼板或原料邊界保持接觸且不重疊.新拼板的最優(yōu)位置與其方向和相對已排零件的位置有關，最佳方向和相對位 置的確定，缺乏可借用的先驗知識，只能靠沿已排拼板邊界移動的試探法來尋 找，這將是算法中耗時最長的部分.拼板邊界移動只需沿已排拼板的合成多邊形邊界進行.用已排拼板和新排拼板形成的凸包面積來確定評估標準根據上述分析，我們認為自動拼板過程主要解決三個問題：一是新拼板的 排放問題；一是狀態(tài)評估問題；三是整理和后續(xù)準備問題.為此我們圍繞這三 個問題設計的自動拼板圖形學算法有：移動算法.在保證排料約束條件和零件緊密靠接基礎上，將新零件沿合成多 邊形的邊界移動，以便對移動的每一位置作出狀態(tài)評估，

8、選出最優(yōu)位置. 狀態(tài)評估算法.將新排料在每個移動位置與已排料合成的面積或者其他評 估方法，作為排料排放位置優(yōu)劣的評估依據.合成多邊形算法.求處于最佳位置和方向的新拼板和已排拼板以及原料邊界 的臺成多邊形，這是下一個拼板排放移動的基準.詳細分析：1.初始化針對目前板的外形等做些處理，減少在后續(xù)算法的復雜度.移動算法由于移動算法在拼板中應用頻率最高，耗時最多.長期以來，國外較為廣 泛使用是臨界多邊形法.待排多邊形B不改變方向地靠接但不重疊已排區(qū)域（多 邊形）繞行一圈，B的一個固定頂點所形成的軌跡叫臨界多邊形.排放的最好的 位置在臨界處臨界多邊形法雖然確立了求取排放B相對A的最佳位置的基本原 則，但

9、A，B中只要有一個是凹多邊形，在繞行時就可能出現A，B重疊的現象，因此，每移動一步都要作重疊判斷.同時，這種事后的重疊判斷給移動的步長 選取帶來了盲目性，且步長不宜過大.對無需重疊判斷的情況(兩個凸多邊形)， 臨界多邊形法的算法復雜度只是O(M+W)，其中M. N為A, B的邊數.而對需 要進行重疊判斷的情況，每次判斷的復雜度為O(MXW).臨界多邊形算法的復 雜度為0(+W)XMN).如果能得到圖形學的一些結果作為先驗知識，事先求出 一次移動不發(fā)生重疊的最佳步長，它可以省略多邊形A，B重疊的事后判斷.大 幅度提高算法的效率目前有關的圖形學結論的基本特征是考慮了 A，B的邊的 某些特征在多邊形

10、靠接過程中的作用.定義1.對一任意的N邊形，可以用N個按逆時針順序排列的頂點集合S， 其中y Y .在集合s中，存在點序列V= VK (XK，YK )，?，VL(XL，YL )， 如果，1KLN，且Y都是遞增，則稱由點序列V組成的一組線段為沿 軸的遞 增線段族；如果1KLN，且Y都是遞減，則稱由點序列 組成的一組線段為沿 軸的遞減線段族.命題.根據定義，若多邊形A和B滿足移動條件，則多邊形B沿x軸移動 與多邊形相接觸的部分為B的遞增線段族的頂點，或線段與的遞減線段族的頂 點或線段之間的接觸.這樣一來，只需計算出單調線族的點到邊距離，就可得 出每次移動的最佳步長.算法l_根據多邊形A，B初始位置

11、判斷多邊形B沿A邊或B邊移動的方向形成 角度X，并計算出移動邊的邊長.判斷B沿形成的角度移動滿足接觸條件的遞增線段的所有頂點，計算 出這些頂點到A的遞減線段族的線段的距離。判別A的滿足接觸條件的遞減線段族的所有頂點，計算出這些頂點到B 的遞增線段族的線段的距離從中選出最小的距離作為移動的步長；將B移動到新位置算法1實際上給出的是多邊形 從一個頂點移動到另一個頂點的距離，即B 沿A(B)的一條邊可以移動的最大距離.按照A，B形成的凸包面積最小的評判原 則，B在這條邊上的最佳位置不一定在移動的最大距離的頂點上，但B靠一側排 放會使原料的剩余面積不至于太零碎，這對下一個零件的排放是有利的，因此， B

12、在A(B)的一條邊上只按最佳步長移動一次(圖2)，再按B每次移動到頂點的凸 包面積選擇B該排放的最佳位置.這比事后的重疊判斷造成的多次步長試探和 重疊判斷計算量小.算法簡捷.另一方面，由于A，B是封閉圖形.可以認為遞 增、遞減線族的頂點數分別只是全部頂 數的一半，每次求最佳步長的計算量只 相當于一次重疊判斷的1 / 4.角度的考慮：在考慮其旋轉角度只考慮如下數據的角度：90, 180, 270以及關于X軸對稱， 關于Y軸對稱等，在PCB加工和實際生產過程中一般不會對其操作與加工對象 無法進行全角度處理，一般是上述幾個角度進行調整與參考。在提高其算法收斂度以及是否需要對SET的圖形進行評估和旋轉

13、參考，在算 法中，設置閥值，如果通過一系列的變化都無法達到設置的閥值。將對原有的 圖形進行矩形處理。具體見下文中描述針對普通的硬板，其復雜外形可以制定一系列的收斂策略加快算法計算速度.狀態(tài)評估在啟發(fā)式算法中，可以自己根據實際的開料的情況進行選擇和修正狀態(tài)評估 參數和方程在滿足PCB實際情況，在Panel拼板時，我們可以側重考慮如下方面實際的板才利用率實際的加工難度剩料面積有些PCB開料軟件和其他行業(yè)的一些下料軟件在使用啟發(fā)算法時候，對其評估 模型的考慮是多種多樣的。例如有些針對鋼板重心之類方面進行評估和參考， 構造其評價參數與方程.1實際板才利用率權值參數設置以及系數在權值的設置上按照實際在P

14、CB制造過程中的參考改造成如下狀態(tài)評估參數實際板在基于矩形狀得到的板材利用率為基點比如：在一個L為225, W為129的尺寸中，可以達到的按一般矩形進行拼版的 的材料利用率可以達到80.62%,在實際考慮權值我們將使用此數值做為算法的 閥值，在狀態(tài)評估參數上我們使用階段參數在收斂和增長速度上參考如下方程：Aq=a*(100*(Xsj-Xfz)+C1)2+b*N+c其中n為階段參數權值，C1為初始參數權值。在異形拼版軟件中,在評價Panel拼版的優(yōu)劣度也可以參考此計算3. 2實際加工難度在PCB實際加工過程中很多參數無法正常加載，考慮到實際加工過程中存在 的問題已經此階段在實際的狀態(tài)中參照的比例

15、 同樣的基準點在將實際的可以得到的加工為起點其參數分為：加工次數，Panel中Set構成數量，以總Panel構成數量Nq=a*(Nsj-Nfz)+C1+b*(1-Ps)+c*(1-S);其中n為階段參數權值，C1為初始參數權值。在做Panel拼版過程中，構造其過程一樣可以借助其評價模型，進行最優(yōu)選擇。3. 3剩料面積PCB中存在很多板材浪費，在拼板過程中如果能夠將剩下的多余的物料能夠有 效利用起來那將得到可觀的收益。在此緯度中主要評價剩下的料是否能夠滿足 其他的小，短等PCB料號的需要不是每個拼板都會對剩下的料進行緯度分析如果在開完料，能夠將料剩下才一大快，節(jié)省成本，所以在此評估模型中此 項目

16、只作為正權項在評估函數中目前暫時不考慮實際操作。.合成多邊形算法暫略。針對Panel進行大料切割開料中Panel數量的考慮與客戶需要的數量已經成本上考衡，已經生產過程 中加工不同板的報廢情況是相關的。目前撇開這個些不考慮，我們在選擇Panel 大小已經其他方式上面會影響利用率同樣如果我們采用開料的利用率與加工難度為評價緯度。開料利用率方程表示如下：K=Sp+Sd+C(1)其利用率Q=Sp/K;其中Sd是電鍍邊的面積；我們設Wp為每個Panel實際的外形寬度，Lp為每 個Panel的實際長度，其X方向的電鍍邊寬度為Xa,Y方向電鍍寬度為Ya,其電鍍 邊的面積 Sd=2Xa*Wp+2*Ya*Lp-

17、4XaYa;在保證每個Panel的利用率的同時，開料的利用率為：Q，在這個基礎上， 我們使用原始的未進行處理的Panel進行參照模型即：在同樣的拼版方式下得到的開料的利用率為基點，使用上面的例子，在 一個L為225, W為129的尺寸中，可以達到的按一般矩形進行拼版的的材料利 用率可以達到80.62%，他的拼板的方式為2*3得到的Panel的尺寸為412*472, 在一個大料寬高為1245*1041的中切割的方式為2*3。我們評估Panel大小的時候計算其利用率可以采用實際的SET的面積，即36*225*129=80.62%而在開料的面積中利用率為：90%，中間差10%的為板邊與電鍍邊所占的面積。我們Panel的評估模型中加入這個考慮因素就行?？梢员ＷC在Panel的較優(yōu) 的時候在大料開料的過程中也有良好的表現。評估的參數可以相對Panel的可以做些相近化的處理總結:針對一般的L字或者一般的硬板使用啟發(fā)算法可以得到一個比較優(yōu)的解。但 是啟發(fā)算法一般計算比較復雜