PCB,即印制电路板,是电子产业重要部件之一。PCB多为单拼生产方式,即将多个PCB单元板拼合在一张工作板上,经过一系列的工艺成型后进行切割,从而一次性生产多个PCB。实际生产中,选择先将板材切割成数个工作板,然后将工作板切割为多个PCB单元板。本文基于此种生产情况,设计考虑工作板的PCB排样生成算法,用于指导工业生产活动。同尺寸集成电路板下料问题广义上属于矩形单一排样问题,毛坯种类单一、数量不限、方向不定。矩形单一排样问题如今已有成熟算法,计算时间和排样结果均能令人满意。但集成电路板下料问题需要考虑板材上工作板的布局,工作板种类及数量不限,尺寸有一定的约束,属于套裁排样问题范畴。因此该问题较之矩形单一排样问题更为复杂。本文生成算法分为3个步骤,第一步采用规范多级方式生成工作板:多个毛坯组成条带,多根条带拼接形成工作板的排样方式,采用动态规划算法递推得到所有满足尺寸工作板的最大价值和排样方式,记录其中的优质工作板(价值随尺寸增加而增加)。第二步生成段:调用背包算法,将尺寸不一、方向不定的工作板拼合成段,快速生成段的最大价值但不记录其排样方式。第三步生成板材:再次调用背包算法将多个段拼合成板材,形成整个板材的排样方式。考察段横向排列和竖向排列两种不同的排样方式,择优者作为最终的排样方式。设计精确算法生成板材上工作板的排样方式用于评估本文算法,实验结果表明本文算法较之精确算法材料利用率略有不足,但计算时间成倍减少,切割工艺更为简单。随着问题规模的增大,计算量和切割工艺优势更为明显,而材料利用率差距逐渐减小。通过与商业软件的对比,大量测试数据表明,本文算法具有更高的材料利用率,切割工艺也更为简单,可以认定本文算法的有效性。