启发式开料算法.pdfVIP

开料介绍以及启发式算法研究

目前针对PCB行业没有存在可以异形拼版的软件。但是有部分软件可以满足

此功能都是应用在其他的行业，如果钢材切割，玻璃。五金之类的行业，这个

些行业与PCB的拼版要求有很多工艺上的不一致。比如在钢材比较注重实际的

利用率，玻璃行业在留下余料的时候需要考虑加工上的一些可行性。还有就是

卷材行业有也类似应用。

下面针对启发式算法做些了初步的探讨

算法分析

问题说明：

一般的开料算法可以简单的表示成如下数学语言：

开料问题是寻找平面最优布局的优化问题，即将一系列二维不规则零件P1，

P2，…Pn合理地排放在原料板B中，使材料的利用率（使用面积总和／占用

得原料板面积）最高，并满足下面的约束条件；

l）料Pi，Pj互不重叠：i，j＝l，2，…n。

2）料Pi必须放在原料板B中：i＝1，2，…n。

3）满足一定的排样要求。

4）满足加工的便捷以及可能性。

开料问题可以从两个方面加以说明，一个是开料过程中的几何问题，主要是针

对规则或者不规则形状的零件，如何确定物料的最佳排放位置，检测物料位置

的合理性以及相关算法。

另一个是物料的调度问题，即如何从参加物料的物料库中选出最优的物料零件，

如何得到一个优化的物料排样顺序。无论是几何问题还是调度问题，都是非常

复杂的问题。这种复杂性一方面来源于物料形状的不规则性，同时也与参与物

料零件的多样性以及零件的批量、生产周期、排样方向性要求等有关。这些因

素相互没有明确逻辑关系，也很难达到一个预期的全局最优解。在很多情况下，

得到的结果都是局部最优解或者是次优解，当然如果只是针对PCB行业，在物

料的多样性比其他的开料可能相对比较简单些，一般不会有太多的料需要进行

一起拼版，一般针对开料优化有哪些信誉好的足球投注网站算法有启发式有哪些信誉好的足球投注网站算法、人工神经网络算法、

模拟退火算法、遗传算法或者他们的组合来解决开料问题。也有这些算法的结

果进行比较与分析，以寻求一种最好的优化算法。然而，研究结果表明这些开

料算法的开料效率运行时间极长，利用率没有手工开料的高。也有开始从料的

形状着手，通过求解任意多边形的临界多边形（NFP）来研究开料问题。目前的

1

NFP算法大都只能计算两个凸多边形或者一个凸多边形和一个凹多边形的临界

多边形。而对于两个凹多边形的临界多边形问题，算法没有很好的解决.

人工开料

让我们来看看人工在开料是如何考虑的：

当人手工排样时，需要估计出最佳状态，然后估计料的最佳组合，然后以此为

模式不断的排放零件到板材上。从而实现一种零件的优化排样。在此之前已经

将加工需要处理的问题（如在有无法开料的情况，计算出来的利用率再高无法

用于实际的生产也是没有任何意义的）考虑进去了

考虑策略

针对上述问题，一般在开料的算法有哪些信誉好的足球投注网站策略上可有如下方面的考虑：

1．针对利用率

2．针对加工便捷，包括开料的便捷。

3．如果是异形，考虑单个料的优化组合

4．如果是异形，考虑多个料的优化组合

这样就可以使得算法能够找到一个相对优的开料组合。

根据这些分析我们可以如下处理：

将各种形状的料处理成矩形，然后按一定的方向进行排版，比如从左上或者左

下开始，所有的料尽可能的往这个方向排，依此类推，直到完成所有。

针对PCB行业的加工以及现在存在的拼版模式，此类方法可以满足大部分的硬

板在开料方面的需要，由于软板在外型等各方面都比硬板要复杂，所以需要对

软板的外形进行特别的处理,比如在找最小矩形时候，如何提高算法的速度已经

在开料过程中的利用率都在考虑的范畴内。

在实际的PCB开料和拼版过程中，开料开出来的联片尺寸间距和每个Panel所

需留言的电镀边为一常量，所以PCB的板子利用率的决定因素有二，分别为每

个Panel的板材净利用率和Panel的数量。

一般在采用不同的算法和方式对后续的计算时间以及得到的解的优劣度有

不同的结果。我们在其过程中必须将开料结合实际PCB中的问题进行参考和校

验。得到相对最优解。

具体步骤

在PCB开料的过程中有多个决定原因是工程人员在制作拼板的参考因素，我

们将这些因素考虑在二个步骤进行：