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

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

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

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