如何提高打孔机的生产效能

开篇：润墨网以专业的文秘视角，为您筛选了一篇如何提高打孔机的生产效能范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要

制作电路板时，需要在板上打孔，孔有多种类型，需要打孔机上的不同刀具以规定的顺序打孔才能制作完成，由于打孔机钻头的移动和切换刀具都需要时间，所以希望可以找到较好的打孔策略，即钻头行进的线路和切换刀具的方案，使得完成一块电路板的时间尽可能的短。本文主要通过程序搜索来寻找最佳单钻头工作线路。

我们将所给数据点加入所需刀具作为第三维，改造成三维坐标，化为一个完全图，将问题转化为旅行商问题(TSP)。构造任意两个坐标点之间的距离矩阵，以方便将来选择路线，同时得到一个很好的性质，即距离满足三角不等式，将问题转化为寻找最佳汉密尔顿回路。对于某些孔型要求特定的刀具打孔顺序，我们对同一坐标的不同刀具点添加了访问关系，只有在访问过之前刀具状态点的前提下才能访问下一个刀具状态点，保证了加工顺序符合要求。做如上处理后，我们通过枚举起点，利用“最邻近点法”，对于每个点，都选择距离最近的路线作为下一路线。在得到初步的最佳路线后，利用“二边逐次修正法”，不断对所得路线进行优化，最终得到了比较理想的路线，计算出了相关数据，如换刀次数，总时间，对应成本等等。我们还用Matlab导入数据点，画出了路线图。

最后，我们对结果做了概述，对模型进行了分析，发现本模型可移植性强，各类参数可自行设置，复杂度低，效率也较高。同时也发现了本模型的几个可以改进的方面。

关键字：打孔机 TSP 旅行商问题 最佳汉密尔顿回路 最邻近点法

中图分类号：D412.64 文献标识码：A 文章编号：

问题概述

过孔是印刷电路板的重要组成部分，每块电路板上有上千个过孔，并且过孔有多种类型，需要打孔机上的不同刀具以规定的顺序打孔才能制作完成，由于打孔机钻头的移动和切换刀具都需要时间，所以希望可以找到较好的打孔策略，即钻头行进的线路和切换刀具的方案，使得完成一块电路板的时间尽可能的短，从而使得生产电路板的效能最大化。

在本文中，我们使用了构造性算法和改进型算法结合的方式，用最邻近点法确定初步方案，再通过二边逐次修正法改善方案。

初步假设

(1)钻头要归位。

(2)钻头无碰撞体积。

(3)钻头行进匀速。

(4)忽略打孔时间。

(5)换刀和行进可以同时进行，但是相应的费用不减。

模型建立与结果

为了将行进与换刀这两个过程统一，我们对数据点做了处理，将其扩充到了三维。对于每种孔型的点，将其x,y坐标作为前两维，所需要的刀具种类作为第三维。并且如果一个过孔需要多种刀具制作，我们就处理成多个点。经过这样的处理，原本的平面数据点换成了三维空间的点。比如对于C孔的某一点(x,y)，在新的坐标下变成了两个点(x,y,a)与(x,y,c)。

在这样的坐标下，这些点以及两两之间的边组成了一个完全图（完全图就是指任何两点之间都有连线的图），本问题就转化为了经典的旅行商问题(TSP)，即寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本的路线。

根据假设，刀具在行进过程中可以同时进行刀具转换，但相应费用不减。所以可以定义如下距离矩阵，其中，i，j为任意两个点，并且已经化为上文提到的三维坐标形式，D(i,j)表示从i到j所需时间，s(i,j)表示i,j之间距离，t换代表换刀时间。

那么点i到点j的时间就是从i移动到j所需时间和切换i和j所需的时间中较大的那个，于是有

(1)

定义了距离函数之后,我们发现它满足三角不等式:

(2)

这是一个十分有用的条件。在图论的相关知识中，有如下定理

在加权图G=(V，E)中，若对任意x，y，z∈V，x，y，z两两不同，都有D(x,y)

根据以上定理，最佳路线一定不会经过两个相同的状态(也就是说点的坐标相同,当前刀具也相同)，所以我们只需要对于经过处理后的三维数据点寻找最优哈密尔顿回路即可。

本问题与最优哈密尔顿回路的差别在于，刀具加工是有次序的，例如孔型C的两个数据点(x,y,a)和(x,y,c)，由于规定必须先用刀具a加工再用刀具c加工，那么在行进路线中，(x,y,a)必须出现在(x,y,c)之前。这样的限制为我们选择最佳路径制造了困难，我们用如下的方法来解决此问题。

以G类孔为例，它的刀具加工顺序为d，g，f。 假设现在有一个G类孔，平面坐标为(x,y)，那么它在新坐标下变为3个点A(x,y,d)，B(x,y,g) 与C(x,y,f)。我们先将(x,y,g)与(x,y,f)点设置为不可访问的，并且将这三个点建立联系，一旦访问到了(x,y,d)这个点，程序会自动将(x,y,d)设为不可访问的，而将(x,y,g)“解禁”，那么(x,y,g)变为可以访问的点，同理，当探索到（x,y,g）后，（x,y,f）又被“解禁”，成为可行点，这样的做法就保证了这3个点（状态）的访问顺序必然是按照刀具加工次序的。

于是我们的目标函数就是:

(3)

其中i1,i2…in为1到n的全排列，并且in+1=i1。

由于最优哈密尔顿回路问题是一个NP-完全问题，从上述目标函数可以看出，穷举法需要列举n!种情况，无法找到多项式数量级复杂度的算法，所以只能采取近似算法。

1.最邻近点法

对于起点，我们采用枚举法。取定起点之后，每一步都选择当前可行边中最短的那一条，这样的复杂度为O(n^2)，枚举起点则使复杂度提高至O(n^3)，对于题中数据，变换坐标之后达到了2814个点，O(n^3)的算法是可以被接受的。而更好的生成树+贪心法的复杂度为O(n^4)，程序运行大约需要100多小时，所以我们选择了复杂度相对较低的最邻近点法。这样，我们得到了初步的线路。

2.二边逐次修正法

在上一步中，我们得到了初步的线路，记为

H=v1,v2,v3,…,vi,…,vj,…,vn,v1

对于所有i,j,1

H=v1,v2,v3,…,vi,vj,v(j-1),…,v(i+1),v(j+1),…,vn,v1

具体实现时，我们对于上文中的i和j采用随机抽取的形式，抽取数量为50000000，保证了线路被很好地优化。

最终得出的单钻头结果（我们最后选取最少时间为最佳路线）

未修正的最邻近点法 做修正后的结果

我们还计算了最优路线(最短时间)的换刀情况，发现是由e-d-c-b-a-h-g-f-c，共八次，在要求的刀具加工顺序下，这样的换刀次数是最少的，从而说明了修正后的最邻近点法对于本题是适用的。

结果概述

此模型可移植性较强，诸多参数，比如安全间距，行进速度，换刀时间，孔型等等都可以自行设置，适用于不同情况。复杂度低，但可以高效地找到比较理想的解。

在单钻头的情况中，利用最邻近法找到初解，利用二边逐次修正法不断优化线路。这种算法简单且高效，对于本题换刀时间远大于行进时间的特点表现优秀。

可改进方面

如果知道钻头的具体形状，可以将两个钻头的距离函数设计得更为精确，从而使结果也更加精确。

参考文献

【1】Reinhard Diestel《Graph Theory》(Third Edition)世界图书出版公司第10章 Hamilton Cycles

【2】高随祥 《图论与网络流理论》高等教育出版社第4章第4节旅行商问题(Traveling Salesman Problem,TSP)

【3】赵静 《数学建模与数学实验》高等教育出版社第13章 行遍性问题

【4】科曼 《算法导论》 （潘金贵等译）机械工业出版社

【5】薛定宇 《高等应用数学问题的Matlab求解》清华大学出版社

【6】姜启源《数学模型》 高等教育出版社