打孔机生产效能的提高优秀作品

NCEPU2012年华北电力大学校内数学建模竞赛-1-电路板的打孔机工作流程设计摘要打孔机完成的打孔作业在印刷电路板的生产过程中占有极其重要的地位，通过合理优化打孔路线，进而减少生产时间及生产成本，提高生产效能，是生产作业过程中必须解决的问题。论文以总工作时间最短为目标函数，建立数序模型，寻找最优路径，最短工作时间以及最少生产成本。忽略打孔时间，认为总的工作时间为钻孔行进时间和刀具转换时间的叠加。总的作业成本为行进成本和刀具转换成本之和。为了解决问题，建立了以下三种模型：模型一：机械模型，按照所需刀具种类和打孔次序，将孔进行分类，并合理安排打孔刀具的顺序，进行分块局部优化。认为用一种刀具打完相应所有孔后，再换刀；通过蚁群算法解得最短路径62480000mil,最短工作时间：2.46h，加工过程总费用95999.328(元)。模型二：简化模型，以所有点为研究对象，进行全局优化。假定钻孔行进过程中不进行换刀操作，打完某一孔后，先换刀，再行进。利用贪婪算法和蚁群算法的混合算法解得，最短路径为54941000mil，最短工作时间：2.60h，加工过程总费用84570(元)。模型三：改进模型，认为钻孔行进过程中进行换刀操作，通过引入有效换刀时间，将总的工作时间分为钻头行进时间和有效换刀时间。利用贪婪算法和蚁群算法的混合算法解得，最短路径为55231000mil，最短工作时间：2.347h，加工过程总费用84570(元)，经分析该模型精确度更高，具体的刀具转换方案及最优路径见附录（一）。在模型二和模型三建立的过程中，将衡量孔的坐标由原始的二维空间坐标，扩充为四维坐标：二维空间坐标，所需刀具种类坐标，加工次序坐标。这样将一个需要多种刀具才能打完的孔型，扩充为多个只需一种刀具的孔，有效的解决了不必一次性打完一个孔型的问题。关键词：蚁群算法贪婪算法坐标维度扩充群孔加工路线设计NCEPU2012年华北电力大学校内数学建模竞赛-2-Ⅰ问题的提出与重述印刷电路板（PCB）制造技术是电子信息制造业的重要基础和组成部分，而由打孔机完成的过孔作业在其生产中占有重要的地位。其中加工路径的选择，很大程度上决定着加工效率和生产成本。问题旨在通过研究单钻头的最优作业路线以及具体的刀具转换方案，尽最大可能的缩短工作时间，减少作业成本，提高打孔机的生产效能。Ⅱ模型假设1、同一孔型钻孔作业时间相同，且由生产工艺决定，与问题的优化无关，此时间给予忽略。2、钻头行进速度相同为180/mms,行进成本为0.06/mm元。3、相邻两刀具的转换时间为18s,转换的时间成本为7元/min。4、刀具转换可以采用顺时针和逆时针的方式，且转换时间具有累加性。5、刀具在行进过程中可以同时进行刀具转换，但相应费用不减。6、不同孔型所需刀具种类、个数及加工次序不同。7、同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。NCEPU2012年华北电力大学校内数学建模竞赛-3-Ⅲ符号说明符号符号所表示的意义n,N原始孔数和扩充之后的孔数,,,iiiiiPxymn扩充后的孔iP的坐标描述ixiy为二维空间坐标；im为刀具种类in为第i次进行加工id第i个孔和第i+1个孔的距离D加工过程中刀具所走总路程V刀具的行进速度it打完第i个孔，准备打第i+1个孔时，刀具行进时间。ir打完第i个孔，准备打第i+1个孔时，刀具转换所需时间。R加工过程中刀具转换的总时间tT加工过程总时间dprice刀具行进成本rprice刀具转换的时间成本Tprice加工过程总费用ir打完第i个孔，准备打第i+1个孔的有效刀具转换时间。R加工过程中总的有效刀具转换时间NCEPU2012年华北电力大学校内数学建模竞赛-4-Ⅳ基本思想和模型的准备4.1基本思想4.1.1目标函数的建立：为了提高生产效能，题目已知条件指出，关键是减少刀具行进时间（即缩短刀具移动路径）和换刀时间。并且通过所给数据进行分析，刀具行进成本和换刀成本都与时间成正相关。因此论文以总的工作时间最短为目标函数，建立数学模型求解，得到最优行进路线，最短时间以及最低成本。4.1.2原始数据的处理：充分考虑题目条件，10种孔型所需刀具种类、个数、加工次序各不相同。将原始的2124个孔进行扩充，原则如下：将原来衡量孔的坐标由原始的二维空间坐标，扩充为四维坐标，即：二维空间坐标，所需刀具种类坐标，加工次序坐标。这样以来原来一个的孔被分解为几个空间位置相同,但加工刀具和加工次序不同的孔。从而有效的解决了不必一次性打完一个孔型的问题。4.1.3算法的确定：为实现高质量、高效率、低成本的产品制造，优化加工路径是加工过程中的一个关键环节。但对于成千上万的群孔，找到一条理想的加工路径并不容易。假设在一块已确定初始位置的印刷电路板（PCB）上加工某类孔（数量为2n）加工完毕后返回，则其可选路径为1!2n条，当10n时，其可选路径为181440条；当20n时，可选路径为166.0810条；当100n时，其路径条数已经成为了天文数字，可以说当加工孔的数量很大时，在所有路径中找到一条最短路径是不现实的，只能从比较理想的路径中挑选一种作为加工路径。为了得到理想的加工路径，主要有以下算法：NCEPU2012年华北电力大学校内数学建模竞赛-5-（1）、传统算法：局部搜索法、贪婪算法、动态规划法；（2）、智能优化算法：模拟退火法、遗传算法、蚁群算法、人工免疫算法等。考虑到传统算法和智能优化算法的优缺点，为了在有限的时间内得到较为理想的路径，论文选用贪婪算法和蚁群算法相结合进行模型的求解。4.1.4结合实际的考虑：在实际生产过程中，一块线路板上的过孔全部加工完成后，再制作另一线路板。因此最优路径确定为闭合路径，即加工起始点和加工结束点重合。为下次加工做准备。4.2模型的准备（1）、首先要做的工作是绘制10种孔型在印刷电路板（PCB）上的位置。（2）、将原始的2124个数据孔进行扩充，得到2814个新的数据孔。Ⅴ机械模型的建立与求解5.1机械模型的建立根据8种刀具将孔型进行分类如下：abcdefgh1A1C1B1E2C2I2J1D1G1D1I1J2E3G1F2G1F1H其中：a、b···g、h表示刀具类型；大写字母表示孔型，下标i表示第i次打该孔型；eg:3G表示第3次打孔型G；现根据所需刀具种类，结合打孔次序，安排工作方式，使用一种刀具打完所有所需的孔型之后，再换刀进行打孔。由于刀具行进总路程很长，在相邻两次换刀时行进路程可以忽略。由图表知孔型E第一次需用c刀具，第二次需用f刀具；而孔型J第一次需NCEPU2012年华北电力大学校内数学建模竞赛-6-用f刀具，第二次需用c刀具。由于c刀具和f刀具的矛盾限制，现将2J（即第2次打孔型J）单独拿出来进行打孔，从而可以先用c刀具打完孔型，在用f刀具打完所需孔型。具体的打孔次序安排如下：abdechgfc1A1C1B1D1G1D1I1E2C2I1F1H1F2G1J2E3G2J5.2机械模型的求解通过MATLAB编写程序，利用蚁群算法进行求解可得：（1）、各个刀具分别打孔的最优作业路线-4-3-2-1012345x105-20246810x105-3-2-101234x105-10123456789x105a刀具打孔b刀具打孔-4-2024x105-20246810x105-4-20246x105-20246810x105d刀具打孔e刀具打孔NCEPU2012年华北电力大学校内数学建模竞赛-7--4-20246x105-20246810x105-4-2024x105-10123456789x105c刀具打孔h刀具打孔-4-3-2-10123x105-20246810x105-4-20246x105-20246810x105g刀具打孔f刀具打孔-4-20246x105-20246810x105c刀具打孔2JNCEPU2012年华北电力大学校内数学建模竞赛-8-（2）、最短路径，最短时间，最低成本最短路径：刀具转换时间：1418252Rs总的最短工作时间：8886.044()2.46()tTsh刀具行进成本76.248102.560.06100dprice95969.928()元刀具转换的时间成本29.4()rprice元加工过程总费用=95999.328Tprice（元）Ⅵ简化模型的建立与求解6.1简化模型的建立6.1.1数据扩充对于区域G中的n个原始孔进行扩充，得到N个新孔。设N个孔的一个排序为123,,,NPPPPP,其中孔,,,iiiiiPxymn有四个坐标。具体含义如下：ixiy孔iP的二维空间坐标；123······8himca刀具b刀具刀具刀具123in第一次加工第二次加工第三次加工若孔,,,iiiiiPxymn和孔,,,jjjjjPxymn满足ijxx，ijyy且ijmm，表示将原来的一个孔扩充为两个新孔，虽然两个新孔的空间坐标一致，但含义不同：（1）、,,,iiiiiPxymn表示使用第im种刀具必须在第in次加工时在位置,iixy上打的孔iP。（2）、,,,jjjjjPxymn表示使用第jm种刀具必须在第jn次加工时在相同位77777777771.351101.266100.591100.507101.098100.253100.270100.590100.338106.24810DmilmilNCEPU2012年华北电力大学校内数学建模竞赛-9-置上打的孔jP。（3）、若孔型对加工刀具im，jm的次序没有限制，可认为所需刀具均可进行第一次加工，即1in，jn=1。（4）、对于空间位置相同的两个孔，若ijnn,则必须先打孔iP，后打孔jP；若1ijnn，则孔iP和jP先后次序无关。6.1.2目标函数的建立：设id为第i个孔和第i+1个孔的距离，D为加工过程中刀具所走总路程，则有：221111(,)(,)iiiiiiiiidxyxyxxyy11NiiDd设ir为打完第i个孔，准备打第i+1个孔时，刀具转换所需时间，R为加工过程中刀具转换的总时间。则有：1118min,8iiiiirmmmm11NiiRr设刀具的行进速度为V,加工过程总时间为tT，刀具行进成本为dprice，刀具转换的时间成本rprice，加工过程总费用Tprice。现假设行进过程中不进行刀具转换，则有：目标函数：tDTRV加工过程总费用TpricedpriceDrpriceR；6.2简化模型的求解NCEPU2012年华北电力大学校内数学建模竞赛-10-考虑到经过扩展后的数据量十分庞大，因此采用贪婪算法和蚁群算法相结合的混合算法进行编程，用贪婪算法得到一组较优解，再通过蚁群算法进行迭代，从而进一步减小误差：（1）、最优作业路线：（2）、最短路径，最短时间，最低成本最短路径：75.494110Dmil刀具转换时间：1548Rs总的最短工作时间：9361.8()2.60()tTsh刀具行进成本75.4941102.560.06100dprice84389.376()元刀具转换的时间成本180.6()rprice元加工过程总费用=84570Tprice（元）Ⅶ模型的改进7.1改进模型的建立-4-3-2-1012345x105-20246810x105优化结果0510150.811.21.41.61.82x104平均时间和最短时间NCEPU2012年华北电力大学校内数学建模竞赛-11-结合实际情况，考虑刀具在行进过程中可以同时进行刀具转换。设在打完第i个孔，准备打第i+1个孔过程中，刀具行进时间为it，刀具转换时间ir，则：iidtv定义ir为打完第i个孔，准备打第i+1个孔的过程中的有效刀具转换时间,R为加工过程中总的有效刀