闞海明 胡曉彥

摘要：為了解決集成電路板（PCB）在生產(chǎn)過程中的自動(dòng)排布問題，實(shí)現(xiàn)不同類型PCB板的一次性自動(dòng)套裁排樣，在傳統(tǒng)自適應(yīng)遺傳算法基礎(chǔ)上引入了梯度概念，實(shí)現(xiàn)了適用于PCB的自動(dòng)排樣算法（AGA_Grad）。相比現(xiàn)有成熟的PCB板套裁排樣軟件，AGA_Grad有參數(shù)設(shè)置簡(jiǎn)單、計(jì)算收斂速度更快及排列更優(yōu)等優(yōu)點(diǎn)，用于指導(dǎo)工業(yè)生產(chǎn)，能夠明顯提高多種類型PCB板的排樣速度。

關(guān)鍵詞：矩形排樣；電路板下料；動(dòng)態(tài)規(guī)劃；遺傳算法

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2020）07-58-3

0引言

矩形排樣已有比較成熟的算法，算法時(shí)間和排樣結(jié)果基本都能滿足生產(chǎn)需要。但在一些小批量、多品種的集成電路下料生產(chǎn)過程中，經(jīng)常會(huì)面臨將多種類型、大小不一PCB放在同一個(gè)工作板上布局的問題，該問題屬于典型的套裁排樣，不僅需要考慮板材的布局，還要考慮待加工PCB的自身形狀。當(dāng)前該類算法大致分為3類：①以傳統(tǒng)精確算法實(shí)現(xiàn)排樣，但耗時(shí)較長(zhǎng)；②生成普通排樣的近似算法；③根據(jù)自身特性及生產(chǎn)情況，一定程度上進(jìn)行簡(jiǎn)化。文獻(xiàn)[1-4]提出生成最優(yōu)2段排樣方式的確定型算法，一定程度上簡(jiǎn)化了切割過程；文獻(xiàn)[5]中的動(dòng)態(tài)規(guī)劃算法解決了考慮切割刀數(shù)的2段排樣方式，對(duì)工業(yè)生產(chǎn)有一定的指導(dǎo)作用；文獻(xiàn)[6-8]在傳統(tǒng)單一排樣算法、套裁排樣算法基礎(chǔ)上進(jìn)行了改進(jìn)。

企業(yè)PCB生產(chǎn)過程有小批量、多品種的典型特點(diǎn)，需要實(shí)現(xiàn)套裁排樣加工，本文將遺傳算法應(yīng)用在其中實(shí)現(xiàn)了PCB套裁排樣，得到了理想效果。

1問題描述

1.1 PCB下料問題

在實(shí)際生產(chǎn)過程中，需要將不同類型的PCB盡可能多地拼放在同一張母板上，經(jīng)過工藝成型將定型的PCB單元板再切割下來(lái)，從而達(dá)到一次性生產(chǎn)多個(gè)PCB的目的，這樣有助于在一定程度上簡(jiǎn)化下料過程。

PCB下料過程中可將單張板材切割成若干大小尺寸不等和價(jià)值已知的矩形毛坯，約束條件有：①確定工作板尺寸；②毛坯數(shù)量不確定，毛坯位置不能重疊，毛坯之間距離可調(diào)整；③使得板材中排入的毛坯數(shù)量盡可能多，整體材料利用率最大，整體材料利用率計(jì)算公式為：材料利用率=（毛坯數(shù)量*單個(gè)毛坯面積/板材總面積）*100%。

3實(shí)驗(yàn)結(jié)果分析

為了測(cè)試AGA_Grad算法的合理性，做了測(cè)試，隨機(jī)生成30組PCB板尺寸，選擇母板為2 500mm*3 000mm，如表1所示。

為了方便比較，分別采用普通遺傳算法和AGA_Grad算法對(duì)表2中PCB板進(jìn)行切割排序，實(shí)際計(jì)算時(shí)發(fā)現(xiàn)二者所需時(shí)間相差無(wú)幾，但收斂速度AGA_Grad算法明顯優(yōu)于普通遺傳算法，迭代次數(shù)對(duì)比如圖2所示。

PCB板的排列結(jié)果如圖3所示，其中切割使用面積占總面積的82%。

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

本文研究了PCB板實(shí)際生產(chǎn)過程中的排樣問題，在自適應(yīng)遺傳算法的基礎(chǔ)上引進(jìn)了梯度概念，提出了AGA_Grad算法，并結(jié)合某研究所實(shí)際生產(chǎn)數(shù)據(jù)證明了該算法的有效性，獲得了滿意的效果。

參考文獻(xiàn)

[1] CUI Yaodong，HE Dongli，SONG Xiaoxia.Generating Optimal Two-section Cutting Patterns for Rectangular Blanks[J]. Computers & Operations Research，2006，33（6）：1505-1520.

[2] CUI Yaodong.A New Dynamic Programming Procedure for Three-staged Cutting Patterns[J].Journal of Global Optimization， 2013， 55（2）：349-357.

[3]季君，陸一平.查建中，等.生成矩形毛坯最優(yōu)兩段排樣方式的確定型算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（1）：183-191.

[4]孔令熠，陳秋蓮.二維多階段矩形剪切排樣算法[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（5）：231-233.

[5]羅丹，崔耀東，李秋蓉.生成勻質(zhì)塊排樣方式的遞推算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（3）：1112-1115.

[6]潘衛(wèi)平，陳秋蓮，崔耀東.考慮切割刀數(shù)的最優(yōu)兩段排樣算法研究[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，39（3）：687-692.

[7]李東興.同尺寸集成電路板下料算法研究[D].南寧：廣西大學(xué)，2016.

[8] FAYARD D，ZISSIMOPOULOS V. Approximation Algorithm for Solving Unconstrained Two-dimensional Knapsack Problems[J]. European Journal of Operational Research， 1995，84（3）：618.