《打孔机效能的提高数学建模论文》由会员分享，可在线阅读，更多相关《打孔机效能的提高数学建模论文（12页珍藏版）》请在金锄头文库上搜索。
1、打孔机生产效能的提高摘 要打孔机在加工作业时，单个钻孔的作业时间，钻头的行进时间以及刀具的转换时间是影响生产效益的三个因素，每当在钻头完成一个电路板的过孔加工时，钻头行进的时间以及刀具转换的时间越短，生产效益越高，且钻头行进的总时间由钻头行进路线决定，而刀具转换总时间由线路板上各孔的位置以及钻头行进方案决定。由于对同一孔型钻孔作业的时间是相同的，所以打孔机的生产效能定义分析得知打孔机的生产效能取决与两个因素：刀具总转换时间T1和打孔机钻头的行进时间T2。对此，分析数据得刀具转换时间和时间的成本都远远大于打孔机行进的时间和成本。为达到最优的作业成本应该是主要使刀具转换的费用最小，即刀具转换的次数
2、最小。本文中我们使用遗传算法寻找刀具转换最优次序，在最优的刀具转换方案的基础上分步择优打孔，即每次打完需要该种刀具的所有孔型，分别求出行进的最短路径，建立每种刀具的当前最优择路模型，从而获得最高的打孔机生产效能，即完成题目要求。【关键词】 生产效能 TSP 遗传算法 刀具转换1 问题的重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻
3、孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，如图1所示。bcdefgha图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18 s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从
4、刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工
5、刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。2 问题的分析本题要求提出一个最优的打孔机打孔方案，该方案要求满足打孔成本小同时作业完成时间尽可能短，问题描述中已经给出所有打孔点的坐标和孔型，在实际生产中，打孔机必然会不间断进行工作，即完成一块电路板的打孔作业后会回到初始位置和初始状态以便开始下一块电路板的打孔工作，因此初步将本题理解为一个多
6、目标TSP问题。3 模型的假设及符号说明3.1 模型的假设（1）假设题目中提供的数据真实准确，且允许存在一定的误差；（2）假定对于同一孔型的作业时间都是相同的，并且不考虑钻孔时间；3.2 符号说明符号具体含义及说明Tt刀具总转换时间； Tm刀具行进总时间； ki编号为i的刀具；dis(i,j)从刀具ki转换到kj的转换次数；Zkij从刀具ki转换到kj的成本；4 模型的建立与求解通过对题目描述以及所给数据进行进一步分析，我们可以知道每个孔的孔型和坐标，但是从数据量分析我们可以发现孔的数目在2000以上，而且部分孔型需要用两到三种刀具进行加工，即这些孔型需要进行2-3次打孔，如此便使得一块电路板
7、上的打孔次数进一步扩大。面对如此庞大的数据，若将此问题当做多目标TSP来对待，模型与求解规模必定十分庞大，必须借助一些非常规方法，其结果最优性也难以得到保证，因此我们需要对问题进行简化与分解。从题目描述我们得知相邻刀具转换一次所需时间是18s，刀具转换成本为7元/min，而刀具行进成本为0.06元/min，并且分析孔点分布数据我们可以明显看到同一孔型的孔点分布相对集中，即使用某种刀具进行多个孔点的连续打孔时，刀具的移动范围相对于全板较小，因此刀具转换的成本远远大于刀具行进的成本。所以想要打孔成本最小，必须要使刀具转换次数尽可能少，于是我们将整个问题进行了一次简化，即认为刀具转换次数越少，生产效
8、能越高，至此，我们将问题分解为了两个子问题：1，刀具最优转换顺序2，优化每种刀具各自的行进路线，使行进路径最短。（1）刀具转换次序最优化该问题的目标即为找到一条最优的刀具转换次序，使刀具转换次数最少，从而使得成本最小，从表1可知每种孔型所需加工刀具和加工顺序，为了方便问题的处理，我们将刀具分为18类（如表2），并对每一类进行编号（如表3）表2孔型ABCDEFGHIJ所需刀具a1b1a2 d1 c2 g1d2h2e2f3c1e1f1h1g2c3c4f2因此刀具转换次序最优问题就变成了18个元素排序优化问题，根据前文分析，最后一个刀具加工完成后需回到初始刀具状态，所以该问题是一个以刀具转换总成本最
9、小为目标的TSP问题。我们使用ki表示编号为i的刀具，i属于118，所以从刀具ki转换到刀具kj的成本为Zkij=ave * dis(i,j)其中ave表示刀具转换一次的成本，dis(i,j)表示从刀具ki转换到刀具kj的转换次数。从刀具ki转换到刀具kj的时间为Tkij=atim * dis(i,j) 其中atim表示刀具转换一次的时间。我们令刀具转换次序为循环向量TURN =（Kturn1Kturn18）,有此我们可以计算刀具转换的有向图的可达矩阵E,其中eij=1or 0.若从ki转换到kj的转换行为正好存在于TURN中,则eij=1,否则为0。所以刀具转换总成本刀具转换总时间的公式类似
10、由模型可知Zt和Tt成正比关系，因此我们从中选择一个Zt作为目标函数即可。因此问题模型变为目标：Min = Zt其中 Zkij=ave * dis(i,j)eij属于E from 循环向量TURN对此类以循环向量TURN为决策变量的优化模型，我们使用遗传算法求解，通过调用Matlab遗传工具包，带入数据求解得到最优刀具转换次序为。d -c -b -a -h -g -f -e -c至此，问题1得以解决。（2）优化每个刀具的打孔行进路径。根据得到的最优刀具转换次序，我们可以获得每次刀具转换后需要加工的点的集合。次序刀具编号孔型1dd1,d2D,G2cc2E3bb1B4aa1,a2A,C5hh1,h
11、2F,H6gg1,g2F,G7ff1,f2E,G,J8ee1,e2D,I9cc1,c3,c4C,I,J令次序为p的刀具需要加工的点总数为Np,点表示为hole_p，对所有加工次序为p的点进行编号得编号为i的点表示为hole_p(i)因为在问题1中已经根据刀具类型对孔型进行了分类，所以在问题2中无须再考虑刀具类型。所以编号为i的点具体表示为hole_p(i) ，其中Xp(i),Yp(i)分别表示该点的横纵坐标。从hole_p(i)行进到hole_p(j)的成本为Mpij = ave_m * | , |其中ave_m表示刀具的单位进行成本，| , |表示两点之间的距离，计算时采用欧几里得距离。从h
12、ole_p(i)行进到hole_p(j)的时间为Tpij = (| , |)/v其中v为刀具行进速度。在刀具次序为p时，令行进路径所对应的的有向图的可达矩阵为Ep,当hole_p(i)到hole_p(j)的路径在我们选择的路径上时epij = 1 否则为0.所以次序p的移动总成本为移动总时间为由模型可知Zm和Tm成正比关系，因此我们从中选择一个Zm作为目标函数即可。我们对此建立0-1模型进行求解。Min = ZmMpij = ave_m * | , |综上所述，将问题转换为一个混合整数线性规划模型，可以使用Matlab软件进行求解。分别求得p=19时的最优路径与最小成本。因此加工一块电路板的总
13、成本为在matlab中根据建立模型求解，得到每种次序的刀具的最优行进路径图如下。次序d次序c次序b次序a次序h次序g次序f次序e次序c同时可以算出每种刀具转换方案下的行进路径长度如下刀具转换方案dcbahgfec行进距离1525.82780.32880.13103745.6621.71570.21435.51159.4刀具转换成本由最优刀具转换次序计算得Zt = 18.9元 949.4688元因此总成本 Z = 968.3688 元5 模型的评价与改进方向5.1 模型的评价5.1.1 模型的优点对打孔工作按照刀具转换时间和行进时间分层考虑，大大简化了题目的复杂性。对于每种刀具的行进路径结果以图的形式表现，清晰明了。5.1.2 模型的缺点遗传算法的收敛性有时候比较差，需要很长时间的迭代计算才能得出较好的收敛结果。6 参考文献1姜启源、谢金星、叶俊 数学模型（第三版） 高等教育出版社2王正林 MATLAB语言常用算法锦集 电子工业出版社3 俞庆生、林冬梅、王东多旅行商问题研究综述J.2012 4陈晓江，黄樟灿.数值分析M.北京：科学出版社,2010：82-8
