《电路板的打孔机工作流程设计.docx》由会员分享，可在线阅读，更多相关《电路板的打孔机工作流程设计.docx（42页珍藏版）》请在三一办公上搜索。
1、NCEPU 2012年华北电力大学校内数学建模竞赛 电路板的打孔机工作流程设计摘要打孔机完成的打孔作业在印刷电路板的生产过程中占有极其重要的地位，通过合理优化打孔路线，进而减少生产时间及生产成本，提高生产效能，是生产作业过程中必须解决的问题。论文以总工作时间最短为目标函数，建立数序模型，寻找最优路径，最短工作时间以及最少生产成本。忽略打孔时间，认为总的工作时间为钻孔行进时间和刀具转换时间的叠加。总的作业成本为行进成本和刀具转换成本之和。为了解决问题，建立了以下三种模型：模型一：机械模型，按照所需刀具种类和打孔次序，将孔进行分类，并合理安排打孔刀具的顺序，进行分块局部优化。认为用一种刀具打完相应
2、所有孔后，再换刀；通过蚁群算法解得最短路径62480000mil,最短工作时间：2.46h，加工过程总费用95999.328(元)。 模型二：简化模型，以所有点为研究对象，进行全局优化。假定钻孔行进过程中不进行换刀操作，打完某一孔后，先换刀，再行进。利用贪婪算法和蚁群算法的混合算法解得，最短路径为54941000mil，最短工作时间：2.60h，加工过程总费用84570(元)。模型三：改进模型，认为钻孔行进过程中进行换刀操作，通过引入有效换刀时间，将总的工作时间分为钻头行进时间和有效换刀时间。利用贪婪算法和蚁群算法的混合算法解得，最短路径为55231000mil，最短工作时间：2.347h，加
3、工过程总费用84570(元) ，经分析该模型精确度更高，具体的刀具转换方案及最优路径见附录（一）。在模型二和模型三建立的过程中，将衡量孔的坐标由原始的二维空间坐标，扩充为四维坐标：二维空间坐标，所需刀具种类坐标，加工次序坐标。这样将一个需要多种刀具才能打完的孔型，扩充为多个只需一种刀具的孔，有效的解决了不必一次性打完一个孔型的问题。 关键词： 蚁群算法 贪婪算法 坐标维度扩充 群孔加工路线设计问题的提出与重述 印刷电路板（PCB）制造技术是电子信息制造业的重要基础和组成部分，而由打孔机完成的过孔作业在其生产中占有重要的地位。其中加工路径的选择，很大程度上决定着加工效率和生产成本。问题旨在通过研
4、究单钻头的最优作业路线以及具体的刀具转换方案，尽最大可能的缩短工作时间，减少作业成本，提高打孔机的生产效能。 模型假设1、同一孔型钻孔作业时间相同，且由生产工艺决定，与问题的优化无关，此 时间给予忽略。2、钻头行进速度相同为,行进成本为。3、相邻两刀具的转换时间为,转换的时间成本为。4、刀具转换可以采用顺时针和逆时针的方式，且转换时间具有累加性。5、刀具在行进过程中可以同时进行刀具转换，但相应费用不减。6、不同孔型所需刀具种类、个数及加工次序不同。7、同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须 用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。符号说明符号
5、符号所表示的意义n , N原始孔数和扩充之后的孔数扩充后的孔的坐标描述 为二维空间坐标； 为刀具种类 为第i次进行加工第i个孔和第i+1个孔的距离加工过程中刀具所走总路程刀具的行进速度打完第i个孔，准备打第i+1个孔时，刀具行进时间。打完第i个孔，准备打第i+1个孔时，刀具转换所需时间。加工过程中刀具转换的总时间加工过程总时间刀具行进成本刀具转换的时间成本加工过程总费用打完第i个孔，准备打第i+1个孔的有效刀具转换时间。加工过程中总的有效刀具转换时间 基本思想和模型的准备4.1基本思想4.1.1目标函数的建立：为了提高生产效能，题目已知条件指出，关键是减少刀具行进时间（即缩短刀具移动路径）和换
6、刀时间。并且通过所给数据进行分析，刀具行进成本和换刀成本都与时间成正相关。因此论文以总的工作时间最短为目标函数，建立数学模型求解，得到最优行进路线，最短时间以及最低成本。4.1.2原始数据的处理：充分考虑题目条件，10种孔型所需刀具种类、个数、加工次序各不相同。将原始的2124个孔进行扩充，原则如下：将原来衡量孔的坐标由原始的二维空间坐标，扩充为四维坐标，即：二维空间坐标，所需刀具种类坐标，加工次序坐标。这样以来原来一个的孔被分解为几个空间位置相同,但加工刀具和加工次序不同的孔。从而有效的解决了不必一次性打完一个孔型的问题。4.1.3算法的确定：为实现高质量、高效率、低成本的产品制造，优化加工
7、路径是加工过程中的一个关键环节。但对于成千上万的群孔，找到一条理想的加工路径并不容易。假设在一块已确定初始位置的印刷电路板（PCB）上加工某类孔（数量为）加工完毕后返回，则其可选路径为条，当时，其可选路径为181 440条；当时，可选路径为条；当时，其路径条数已经成为了天文数字，可以说当加工孔的数量很大时，在所有路径中找到一条最短路径是不现实的，只能从比较理想的路径中挑选一种作为加工路径。为了得到理想的加工路径，主要有以下算法：（1）、传统算法：局部搜索法、贪婪算法、动态规划法；（2）、智能优化算法：模拟退火法、遗传算法、蚁群算法、人工免疫算法等。考虑到传统算法和智能优化算法的优缺点，为了在有
8、限的时间内得到较为理想的路径，论文选用贪婪算法和蚁群算法相结合进行模型的求解。4.1.4结合实际的考虑：在实际生产过程中，一块线路板上的过孔全部加工完成后，再制作另一线路板。因此最优路径确定为闭合路径，即加工起始点和加工结束点重合。为下次加工做准备。4.2模型的准备（1）、首先要做的工作是绘制10种孔型在印刷电路板（PCB）上的位置。（2）、将原始的2124个数据孔进行扩充，得到2814个新的数据孔。 机械模型的建立与求解5.1机械模型的建立根据8种刀具将孔型进行分类如下： 其中：a、bg、h表示刀具类型；大写字母表示孔型，下标表示第次打该孔型；eg: 表示第3次打孔型；现根据所需刀具种类，结
9、合打孔次序，安排工作方式，使用一种刀具打完所有所需的孔型之后，再换刀进行打孔。由于刀具行进总路程很长，在相邻两次换刀时行进路程可以忽略。由图表知孔型第一次需用刀具，第二次需用刀具；而孔型第一次需用刀具，第二次需用刀具。由于刀具和刀具的矛盾限制，现将（即第2次打孔型）单独拿出来进行打孔，从而可以先用刀具打完孔型，在用刀具打完所需孔型。具体的打孔次序安排如下： 5.2机械模型的求解通过MATLAB编写程序，利用蚁群算法进行求解可得：（1）、各个刀具分别打孔的最优作业路线 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔（2）、最短路径，最短时间，最低成本 最
10、短路径： 刀具转换时间： 总的最短工作时间： 刀具行进成本 刀具转换的时间成本 加工过程总费用 简化模型的建立与求解6.1简化模型的建立6.1.1数据扩充对于区域G中的n个原始孔进行扩充，得到N个新孔。设N个孔的一个排序为,其中孔有四个坐标。具体含义如下： 孔的二维空间坐标； 若孔和孔满足，且，表示将原来的一个孔扩充为两个新孔，虽然两个新孔的空间坐标一致，但含义不同：（1）、表示使用第种刀具必须在第次加工时在位置上打的孔。（2）、表示使用第种刀具必须在第次加工时在相同位置上打的孔。（3）、若孔型对加工刀具，的次序没有限制，可认为所需刀具均可进行第一次加工，即，=1。（4）、对于空间位置相同的两
11、个孔，若,则必须先打孔，后打孔；若，则孔和先后次序无关。6.1.2目标函数的建立：设为第i个孔和第i+1个孔的距离，为加工过程中刀具所走总路程，则有： 设为打完第i个孔，准备打第i+1个孔时，刀具转换所需时间，为加工过程中刀具转换的总时间。则有：设刀具的行进速度为,加工过程总时间为，刀具行进成本为，刀具转换的时间成本，加工过程总费用。 现假设行进过程中不进行刀具转换，则有：目标函数：加工过程总费用；6.2简化模型的求解考虑到经过扩展后的数据量十分庞大，因此采用贪婪算法和蚁群算法相结合的混合算法进行编程，用贪婪算法得到一组较优解，再通过蚁群算法进行迭代，从而进一步减小误差：（1）、最优作业路线：
12、（2）、最短路径，最短时间，最低成本 最短路径： 刀具转换时间： 总的最短工作时间： 刀具行进成本 刀具转换的时间成本 加工过程总费用 模型的改进7.1改进模型的建立结合实际情况，考虑刀具在行进过程中可以同时进行刀具转换。设在打完第i个孔，准备打第i+1个孔过程中，刀具行进时间为，刀具转换时间，则：定义为打完第i个孔，准备打第i+1个孔的过程中的有效刀具转换时间,为加工过程中总的有效刀具转换时间，则：若 则 ；若 则 则目标函数变为： 但由于相应费用不减，因此加工过程总费用为：7.2改进模型的求解方法同上，利用贪婪算法和蚁群算法相结合的混合算法进行编程。（1）、最优作业路线：（2）、最短路径，
13、最短时间，最低成本 最短路径： 刀具转换时间： 总的最短工作时间： 刀具行进成本 刀具转换的时间成本 加工过程总费用 （3）、刀具转换方案 请参照附录（一） 结果分析在模型一机械模型中，模型最为简单，忽略的因素最多，因而路程最长，成本最大。对于模型二简化模型及模型三改进模型，由于运用全局优化，使得最终的路径长度大大减少，成本也大大减少。但由于模型二假设行进时不转刀，且转到次数较多，因而总时间较大。综合考虑还是模型三改进模型的结果更好。总之，由于算法精度的原因以及时间的限制，论文所得结果不一定为最优解，但却比较好的说明了实际情况。 模型的评价及应用9.1模型的优点（1）、优化路径为闭合路径，使得
14、线路板打孔结束后又回到起点，为下次打孔做准备，避免了每次生产过程中调整起始点，符合现实生产要求。（2）、将一个需要多种刀具才能打完的孔型，通过增加坐标维数，扩充为多个只需一种刀具的孔，有效的解决了不必一次性打完一个孔型的问题。（3）、通过建立以总时间最短为目标函数，引入有效刀具转换时间，使得研究刀具边行进边换刀问题得以简化。同时，由于在这种情况相应费用不减，因而这种模型所得结果更有利于提高生产效能。（4）、采用贪婪算法找出若干较优路径，然后利用蚁群算法进行迭代，这样一方面提高了计算精度，另一方面减少了时间复杂度。9.2模型的缺点由于加工孔数众多，在所有路径中找到一条最优路径是不现实的，只能从比
15、较理想的路径中挑选一种作为加工路径，受时间因素的制约，论文得到最终结果不一定是最优解，只是较优解。9.3模型的应用本问题基于TSP最优路径问题。经过查找资料知道，运用此类思想，可以解决现实生活中的很多问题，比如循环物流系统设计，邮箱取信问题，随机车辆调度，路径规划，三方服务代理等。这类问题的研究及其解决对于提高生产效能，减少成本及其资源的浪费具有积极作用。尤其是随着世界经济的发展和市场竞争的加剧，小至一个企业大到一个民族，只有坚持效率至上的原则，才能紧跟时代的步伐，引领时代的潮流。同时，此类问题的解决对于应对当今世界资源短缺的现状，有一定的推动作用。总之，通过建立相关数学模型，使得这类问题得到
16、很好的解决，对于整个国民经济体系的发展和提高具有不可估量的作用。 拓展与展望（1）、经过查阅相关资料，了解到有一种双钻头的打孔机：两钻头可以同时作业且作业是独立的，但为了避免钻头间的触碰和干扰，受到两钻头合作间距的限制。这是我们今后要研究和解决的问题。（2）、由于受到算法的制约，使得优化效果不能达到十全十美，或多或少存在着一些缺陷，基于此，今后的研究方向是融合多种算法的优点，使用混合算法。并且研究决定算法好坏的影响因素，如算法复杂度、存储空间大小等，制定一些算法评价指标及其权重，从而构造出一套优化算法的模糊综合评价体系。参考文献1 董臻圃，康志校等，数学建模方法与实践 M，北京：国防工业出版社
17、，2006.8。2 王向东，戎海武，数学实验M，北京:高等教育出版社，2004。3 马良，朱刚，宁爱兵等，蚁群优化算法 M，科学出版社，2008.2。4 全国大学生数学建模组委会，数学建模的实践 M，北京：高等教育出版社，2007.8。5 张振普，王大承，群孔加工路径的优化算法 J，五邑大学学报，2008.5，22 (2):25-30。6 赵曦，叶和平，广义旅行商问题及其求解J，东莞理工学院学报，2007.10，14(5):75-79。7 张宏，李爱平，刘雪梅，面向TSP求解的混合蚁群算法 J，计算机工程，2009.4,35(8):34-38。8 洪玉振，TSP最短路径的必要条件初探 J，河海
18、大学学报，2006.11,34(6):716-720。9 周利民，赵万华，卢秉恒等，数控钻床多孔钻削的路径生成算法 J，机械工程师，1996,3:10-11。10 陈洪，蔡佳，张玉成等，多分类贪婪算法的一致性 J，湖北大学学报（自然科学版），2005,4:21-26。附录： （一）模型三改进模型的刀具转换方案及最优路线： （二）程序代码：（一）模型三改进模型的刀具转换方案及最优路线:- 42 -xy刀型1000243600a3200242800a5400242400a7800240600a10200242600a9600250400a12800250800a16000252400a190002
19、54000a16000248200a25400252200a28500254000a31600252200a34300254500a38000252000a41000254000a44200252000a47400254000a50600252000a53500254000a60000254000a62300250500a55300243500a57300223500a60000221400a50600221400a47400222400a44200221400a41000223000a38200221000a34800223500a31600221600a28500221500a238002
20、23500a19000221400a16000223600a12800221600a9600221600a6400223600a3500221500a200221600a-3000223600a-6400221600a-9200221600a-12400223200a-15600221600a-19000223600a-21800221600a-17800211200a-12400211200a-9400209800a200210600a9600209800a15800211000a18800211000a44200210800a50600211200a53600209800a88800192
21、800a90600190800a88800188800a90600187000a88800185000a90600183000a88800181000a90600179000a88800177000a90600175000a88800173200a90600171200a88800169200a88800161200a90600159400a88800157400a90600155400a88800153400a90600151400a88800149400a90600147600a88800145600a90600143600a88800141600a90600139600a88800137
22、600a90600135800a114000137600a116000135800a116000139600a114000141600a116000143600a114000145600a116000147600a114000149400a116000151400a114000153400a116000155400a114000157200a116000159400a114000161400a116000167200a114000169200a116000171200a114000173200a116000175000a114000177000a116000179000a11400018100
23、0a116000183000a114000185000a116000187000a114000188800a116000190800a114000192800a159200218300a170200207300a181200218300a170200229300a145600246000a130800262600a103400271600a102000269600a90000267600a88400265600a90000263600a88400261600a90000259800a88400257800a90000255800a88400253800a90000251800a88400249
24、800a102000246000a103400247800a88400269600a90000271600a88600293200a90000295200a102000297200a103600295200a103600299200a102000301200a103600303000a102000305000a103600307000a102000309000a103600311000a102000312800a103600314800a102000316800a103600318800a102000320800a103600322800a102000324800a103600326600a1
25、02000328600a103600330600a102000332600a103600334400a102000336400a103600338400a102000340400a103600342400a102000344400a103600346200a102000348400a103600350200a79000318800a77400316800a79000314800a63600320600a52800322600a50400316800a53000302800a53000299000a62800301000a44200267000a41600265000a36000268600a2
26、2200265600a9400266600a6400265800a-1800265000a-7800265800a-9400268600a-11000267000a400272800a-5800254000a-3000252800a3400250000a-1400241800a-3600242600a-6000242600a-12400251600a-24800259200a-36200257400a-36600254800a-38000268800a-35000270800a-51200284200a-48600293000a-57600292400a-50000310000a-480403
27、30058a-43040330058a-38040330058a-33040330058a-33040335058a-38040335058a-43040335058a-48040335058a-53040335058a-53040330058a-58040330058a-58040335058a-63040335058a-63040330058a-68040330058a-68040335058a-93200326400a-95400325000a-97600324000a-100200322400a-95200320500a-94600318400a-95025312418a-981743
28、12418a-101400315600a-104474312418a-107600312400a-107623309269a-104474309269a-104474306119a-101400306200a-107623306119a-110800306000a-113922306119a-113922302970a-113922299820a-110773299820a-107623299820a-104474299820a-101324299820a-101324296670a-101324293521a-104474293521a-104474296670a-107623296670a
29、-110773296670a-110773293521a-107700293500a-110800290200a-113922287222a-113922284072a-117072284072a-117072287222a-120222287222a-120222284072a-120200281000a-120222277773a-117072277773a-120200274500a-120222271474a-117072271474a-117000268400a-113922268324a-110773268324a-107623268324a-107623265174a-10447
30、4265174a-101324265174a-101324268324a-101324271474a-101324274623a-101324277773a-98174277773a-98174280922a-98174284072a-101324284072a-101324287222a-104474287222a-107623287222a-107700284000a-107623281000a-104474280922a-107623277773a-107623274623a-107623271500a-110700271500a-110773274623a-104474274623a-
31、104474271474a-110773265174a-120222262025a-120222268324a-123371268324a-129670268324a-129600265200a-132800265200a-132820268324a-132820271474a-132820274623a-129670274623a-126521274623a-129670271474a-129670277773a-129670280922a-126521280922a-126521284072a-129670284072a-132800284000a-132820280922a-132820
32、277773a-136000280800a-139000281000a-139000277800a-142200277800a-142200274600a-142269271474a-145418271474a-145418274623a-145418277773a-148600277800a-148568274623a-148600281000a-145400281000a-142200281000a-142200284200a-142200287200a-142269290371a-142269293521a-142269296670a-139119296670a-135970296670
33、a-136000293600a-139119293521a-132820293521a-132820296670a-129670296670a-126521296670a-126521293521a-129670293521a-129670287222a-126521287222a-132820287222a-135970287222a-139000287200a-136000284000a-135970274623a-135970271474a-139119271474a-139119268324a-135970268324a-135970265174a-135970262025a-1391
34、19265174a-142269262025a-145418262025a-154200261800a-154400268200a-152800282200a-148600284200a-145400284200a-145400287200a-151600287200a-155000290600a-155200293600a-151718299820a-148568299820a-145418299820a-145418302970a-142269302970a-142269306119a-145418306119a-145418309269a-142269309269a-1422693124
35、18a-139119312418a-135970312418a-135970309269a-139119309269a-135970306119a-135970302970a-139119302970a-139119299820a-135970299820a-132820299820a-129670299820a-126521299820a-126521302970a-126521306119a-129670306119a-129670302970a-132820302970a-132820306119a-132820309269a-132820312418a-129670312418a-12
36、6521312418a-126521309269a-129670309269a-123371309269a-120222309269a-120222312418a-123371312418a-117072312418a-117072309269a-113922309269a-110773309269a-113922312418a-117072306119a-117072302970a-117072299820a-117072296670a-117072293521a-113922293521a-113922296670a-120222296670a-120222293521a-120222299820a-120222302970a-120222306119a-139119315568a-142269315568a-145418315568a-148568315568a-148568318718a-151718318718a-152000321800a-151600324400a-149000324800a-142200326000a-142269318718a-148600312400a-148568309269a-148568306119a-148568302970a-151718302970a-148568296670a-157800325000a-160
