同尺寸集成電路板下料算法研究.pdf

1、PCB，即印制電路板，是電子產(chǎn)業(yè)重要部件之一。PCB多為單拼生產(chǎn)方式，即將多個PCB單元板拼合在一張工作板上，經(jīng)過一系列的工藝成型后進(jìn)行切割，從而一次性生產(chǎn)多個PCB。實際生產(chǎn)中，選擇先將板材切割成數(shù)個工作板，然后將工作板切割為多個PCB單元板。本文基于此種生產(chǎn)情況，設(shè)計考慮工作板的PCB排樣生成算法，用于指導(dǎo)工業(yè)生產(chǎn)活動。
　　同尺寸集成電路板下料問題廣義上屬于矩形單一排樣問題，毛坯種類單一、數(shù)量不限、方向不定。矩形單一排樣問題

2、如今已有成熟算法，計算時間和排樣結(jié)果均能令人滿意。但集成電路板下料問題需要考慮板材上工作板的布局，工作板種類及數(shù)量不限，尺寸有一定的約束，屬于套裁排樣問題范疇。因此該問題較之矩形單一排樣問題更為復(fù)雜。
　　本文生成算法分為3個步驟，第一步采用規(guī)范多級方式生成工作板:多個毛坯組成條帶，多根條帶拼接形成工作板的排樣方式，采用動態(tài)規(guī)劃算法遞推得到所有滿足尺寸工作板的最大價值和排樣方式，記錄其中的優(yōu)質(zhì)工作板（價值隨尺寸增加而增加）。第二步

3、生成段:調(diào)用背包算法，將尺寸不一、方向不定的工作板拼合成段，快速生成段的最大價值但不記錄其排樣方式。第三步生成板材:再次調(diào)用背包算法將多個段拼合成板材，形成整個板材的排樣方式?？疾於螜M向排列和豎向排列兩種不同的排樣方式，擇優(yōu)者作為最終的排樣方式。
　　設(shè)計精確算法生成板材上工作板的排樣方式用于評估本文算法，實驗結(jié)果表明本文算法較之精確算法材料利用率略有不足，但計算時間成倍減少，切割工藝更為簡單。隨著問題規(guī)模的增大，計算量和切割工藝