《流程管理流程再造电路板的打孔机工作流程设计》由会员分享,可在线阅读,更多相关《流程管理流程再造电路板的打孔机工作流程设计(41页珍藏版)》请在金锄头文库上搜索。
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)、最短路径,最短时间,最低成本 最短路径: 刀具转换时间: 总的最短工作时间: 刀具行进成本 刀具转换的时间成本 加工过程总费用 (3)、刀具转换方案 请参照附录(一) 结果分析在模型一机械模型中,模型最为简单,忽略的因素最多,因而路程最长,成本最大。对于模型二简化模型及模型三改进模型,由于运用全局优化,使得最终的路径长度大大减少,成本也大大减少。但由于模型二假设行进时不转刀,且转到次数较多,因而总时间较大。综合考虑还是模型三改进模型的结果更好。总之,由于算法精度的原因以及时间的限制,论文所得结果不一定为最优解,但却比较好的说明了实际情况。