打孔机生产效能的提高wenti.doc

封一答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目: D题 打孔机生产效能的提高组 别：本科生参赛队员信息(必填)：姓 名专业班级及学号联系电话参赛队员1石鹏09级信息管理与信息系统 091619011913039803612参赛队员2罗永智09级信息管理与信息系统091619011413674592763参赛队员3董贵军09级信息管理与信息系统 091619010215145938872 参赛学校：哈尔滨医科大学大庆校区封二答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3. 评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛评阅3打孔机生产效能的提高摘要：本文对印刷电路板过孔的生产效益如何提高进行了研究。钻孔加工是工厂制造电路板过程中非常重要一个环节，过孔的加工费用通常占制板费用的30%到40%，因此提高过孔的生产效能在一定程度上影响到作业成本和作业时间，提高钻孔加工效能已成为制造业中急需解决的重要问题。提高孔加工的效率，就务必要找到最优的打孔路径。因此，要结合实际问题，应用理论知识进行打孔路径的优化，以实现加工的高效率和低成本。孔加工是典型的TSP问题。本文对钻头转换的时间，费用进行了研究，对于单钻头，首先结合所需刀具的转换，确定10种孔型的加工的最优次序，简称最佳走刀路线，再运用模拟退火算法对每个孔型建立模型，对每个模型路径进行求解，最后用MATLAB对数据计算出最短距离，做出最佳走刀路线图，求其作业时间和成本，为提高生产效能，设计出双钻头。对于双钻头，首先确保两个钻头的间距不小于3cm（称为两钻头合作间距），再利用遗传算法同样结合MATLAB作图求其最短距离，求得作业时间和作业成本；同时，再考虑两钻头间距对作业效能的影响。最后，通过单钻头和双钻头的作业时间和作业成本进行比较得出双钻头基于单钻头所提高的生产效能。 关键字：最佳走刀路线 生产效能 TSP问题 模拟退火算法 遗传算法一、问题的重述打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。 现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状， 而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18 s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。1求出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本2为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、问题的分析1单钻头分析：本体旨在解决如何提高电路板打孔机的生产效能，要想提高打孔机效能（即打孔所用的时间最少），必须使钻头走过的路径达到最短以及提高钻头的行进速度，同时减少钻头刀具的转换次数。现已假定钻头的行进速度不变（即18mm/s），因此钻头移动路径的长短和钻头刀具的转换次数是决定生产效能的两个因素，通过对电路板孔型和解决的问题的分析得知，要想求出最佳的作业成本和作业时间，首先求出钻头的最佳转换次序，通过钻头的转换次序确定所要打的孔型，最后确定孔群加工的路径并优化。孔群加工的路径优化问题为典型的旅行商问题，简称TSP，对于单钻头的孔群路径优化问题用模拟退火算法求解；根据模拟退火算法先求但钻头问题。行进时间等于作业最短路径除以钻头的行进速度再加上刀具的最佳转换时间，行进时间即为总时间；根据每秒钻头行进的成本和每秒钻头刀具转换的成本即可得出单钻头的走刀的作业成本。2双钻头分析：对于双钻头，决定生产效能的不仅是移动路径的长短和钻头的转换次数，两个钻头的合作间距也决定她的生产效能。对于双钻头合作加工去掉对刀点合并后是一个待加工孔群序列，因此通过染色体表示双钻头孔群加工路径问题的可能解，即利用遗传算法进行求解。当两个钻头合作时，为使问题简化，把钻头看做质点，双钻头的两个钻头可以同时作业，且作业时独立的，即两个钻头可以同时进行打孔，也可以一个钻头打孔，另外一个钻头转换刀具，为避免两个钻头之间的碰撞，现假设在过孔加工的任何时刻两个钻头的间距必须不小于3cm（称为两钻头的合作间距），利用遗传算法做出双钻头的最优作业线路图并求出作业时间，并与单钻头的作业时间和成本比较，可得出其生产效能提高多少。最后研究打孔机的两个钻头合作间距对生产效能的影响。三、基本假设1 . 假设对于同一孔型钻孔作业时间都是相同的2 . 假设钻头的行进速度是相同的且钻头移动是匀速的3 . 忽略各个孔型的大小，将孔型视为质点4 . 将钻头视为质点四、模型定义1.模拟退火算法：模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA 算法的主要步骤描述如下.算法1. SA-Algorithmprocedure SA _ Algorithm( i0, T 0) ;/ * Si0为任一初态, T0 为初始控制参数* /begin( 1) sSi0; C* Ci ; k 0/ * 简记Ci = C( Si) , C* 为当前代价值. * /( 2) repeat( 2. 1) repeat( 2. 1. 1) s j Generate( s ) ;( 2. 1. 2) if Cj C* then ss jelse if Accept( j , s ) t hen ss j end ifend if( 2. 1. 3) until内循环结束条件;( 2. 2) T K + 1Update( Tk) ; k k+ 1( 3) until TkEend2.旅行商问题（Traveling Sale man Problem，TSP）：又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。旅行商问题就是求解巡回线路的耗费的最小值。数学模型描述如下：3.遗传算法：遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。所以，遗传算法中，编码方案和各种算子的设计特别重要，编码和算子设计如图1所示图1五、符号说明1.时间：秒（s），分（min）2.最短路径：minDistance，Shortest_Length3.孔坐标：密尔（mil）六、模型的建立和求解1.单钻头模型建立 首先利用枚举法得出刀具的最佳转换步骤，进而得出各种孔型的加工次序。现列出15中相对较为省时的方法：. a-b-c-d-e-f-g-h-g-f-e-d-c. b-c-d-e-f-g-h-a-b-c-d-e-f. c-d-e-f-g-h-a-b-c-d-e-f. d-e-f-g-h-a-b-c-d-e-f. e-f-g-h-a-b-c-d-e-f-g-f. f-g-h-a-b-c-d-e-f-g-h-e-d-c. g-h-a-b-c-d-e-f-g-f-e-d-c. h-a-b-c-d-e-f-g-h-f-e-d-c. a-h-g-f-e-d-c-b-a-h-g-f.b-a-h-g-f-e-d-c-b-a-h-g-f.c-b-a-h-g-f-e-d-c-b-a-h-g-f.d-c-b-a-h-g-f-e-d-c-b-a-h-g-f.f-e-d-c-b-a-h-g-f-e-d-c.g-f-e-d-c-b-a-h-g-f-e-d-c.h-g-f-e-d-c-b-a-h-g-f-e-d-c通过计算可以得出如下表：转换方 法转换次 数131312111214131312131415121314 表 2即：第一种方法的刀具转换次数为13次；第二种方法的刀具转换次数为13次；第三种方法的刀具转换次数为12次；第四种方法的刀具转换次数为11次；第五种方法的刀具转换次数为12次；第六种方法的刀具转换次数为14次；第七种方法的刀具转换次数为13次；第八种方法的刀具转换次数为13次；第九种方法的刀具转换次数为12次；第十种方法的刀具转换次数为13次；第十一种方法的刀具转换次数为14次；第十二种方法的刀具转换次数为15次；第十三种方法的刀具转换次数为12次；第十四种方法的刀具转换次数为13次；第十五中方法的刀具转换次数为14次；比较得出第四种刀具转换方法为最优刀具转换方法，即d-e-f-g-h-a-b-c-d-e-f 次转换方法最佳。注释：第一步，首先从d刀开始打孔，d刀所能打的孔型为D（d）、G（d）；第二步，转换刀具，换为e刀，e刀所能打的孔型为D（e）、I（e）；第三步，转换刀具，换为f刀，f刀能打的孔型为J（f）；第四步，转换刀具，换为g刀，g刀能打的孔型为F（g）、G（g）；第五步，转换刀具，换为h刀，h刀能打的孔型为F（h）、H（h）；第六步，转换刀具，换为a刀，a刀能打的孔型为A（a）、C（a）；第七步，转换刀具，换为b刀，b刀能打的孔型为B（b）；第八步，转换刀具，换为c刀，c刀能打的孔型为C（c）、E（c）、I（c）、J（c）；第九步，转换刀具，把刀具通过d刀和e刀，转到f刀，f刀能打的孔型为E（f）、G（f），到此，所有的孔型都已加工完毕。我们对建立的模型用MATLAB进行编程，程序如下global D;load PointCoordinates.txt;m,n=size(PointCoordinates);D = sqrt(PointCoordinates( :,ones(1,m) - PointCoordinates( :,ones(1,m).2 +. (PointCoordinates( :,2*ones(1,m) - PointCoordinates( :,2*ones(1,m).2 );iter_max=150%input(请输入固定温度下最大迭代次数iter_max= );m_max=50%input(请输入固定温度下目标函数值允许的最大连续未改进次数m_nax= ) ;T=10000%起始温度tau=1e-12%input(请输入最低温度tau= );iter_num=0;%某固定温度下迭代计数器m_num=0;%某固定温度下目标函数值连续未改进次数计算器path0=randperm(m);%构造一个初始可行解,产生一组1到m的随机排列disp(path0);Distance0=leng(path0,m)figure;plot(PointCoordinates(path0,1),PointCoordinates(path0,2),PointCoordinates(path0,1),PointCoordinates(path0,2),*)% while (T=tau)&(m_num=tau)% path0=path2; iter_num=0;%某固定温度下迭代计数器 m_num=0;%某固定温度下目标函数值连续未改进次数计算器 while (m_numm_max)&(iter_num=tau)&(m_num=tau)% path0=path2; iter_num=0;%某固定温度下迭代计数器 m_num=0;%某固定温度下目标函数值连续未改进次数计算器 while (m_numm_max)&(iter_numiter_max) dt,path1=ChangePath2(path0,m);% dt=len(path1)-len(path0) if (dtrand(1) path0=path1;% dt;% Distance=leng(path2,m); iter_num=iter_num+1; m_num=0; else m_num=m_num+1 ;% iter_num=iter_num+1; end end T=0.9*T;% iter_num% m_numendTBestPath=path0;disp(BestPath)figure;plot(PointCoordinates(path0,1),PointCoordinates(path0,2),PointCoordinates(path0,1),PointCoordnates(path0,2),*)minDistance=leng(path0,m) if (dtrand(1) path0=path1;% dt;% Distance=leng(path2,m); iter_num=iter_num+1; m_num=0; else m_num=m_num+1 ;% iter_num=iter_num+1; end end T=0.9*T;% iter_num% m_numendTBestPath=path0;disp(BestPath)figure;plot(PointCoordinates(path0,1),PointCoordinates(path0,2),PointCoordinates(path0,1),PointCoordnates(path0,2),*)minDistance=leng(path0,m)上述为主程序，子程序和孔群坐标见附录。2.单钻头模型运行结果及分析对于单钻头的假设，采用模拟退火算法由MATLAB软件进行数据处理，根据最佳切刀方案（d-e-f-g-h-a-b-c-d-e-f）得出各个刀所加工路线的随机图形、最优图形、最短距离如下： d刀加工D、G孔的随机图形（图2）、最优图形（图3）和最短距离： 图2 图 3minDistance =1.0678e+007（mil）e刀加工D、I孔的随机图形（图4）、最优图形（图5）和最短距离： 图4 图5minDistance =1.0085e+007(mil)f刀加工J孔的随机图形（图6）、最优图形（图7）和最短距离： 图6 图7minDistance =4.6150e+006(mil)g刀加工F、G孔的随机图形（图8）、最优图形（图9）和最短距离： 图8 图9minDistance =3.1940e+006(mil)h刀加工F、H孔的随机图形（图10）、最优图形（图11）和最短距离： 图10 图11minDistance =4.2002e+006(mil)a刀加工A、C孔的随机图形（图12）、最优图形（图13）和最短距离： 图12 图13minDistance =6.4890e+007(mil)b刀加工B孔的随机图形（图14）、最优图形（图15）和最短距离： 图14 图15minDistance =5.4749e+007(mil)c刀加工C、E、I、J孔的随机图形（图16）、最优图形（图17）和最短距离： 图16 图17minDistance =3.0997e+007(mil)f刀加工E、G孔的随机图形（图18）、最优图形（图19）和最短距离： 图18 图19 minDistance =4.8637e+006(mil)由上图1到图18可知单钻头作业的最优线路（包括刀具转换方案）的条件下得到最短距离为各刀依次加工对应孔型最优路径长之和，结果如下：Shortest_Length = 1.882719(mil)= 4.78210626(mm)注：1mil=0.0254mm所有钻头的行进速度是相同的，为180mm/s，所以：钻头的进行时间=4.78210626/180=2.6567257(s)刀具转换时间=1118=198(s)则単钻头打孔的作业时间(T)为钻头进行时间与刀具转换时间之和，即：作业时间=2.6765257(s)综上，作业成本=钻头进行成本+刀具切换成本, 即：钻头进行成本=4.782106260.06=2.869263756(元)刀具切换成本=1987/60=23.1(元)则：作业成本=2.869263756+23.1=2.869494756(元)3.双钻头模型建立与分析根据遗传算法编写代码如下：% Verify InputsN,dims = size(xy);nr,nc = size(dmat);if N = nr | N = ncerror(Invalid XY or DMAT inputs!)endn = N;% Sanity Checkspop_size = 4*ceil(pop_size/4);num_iter = max(1,round(real(num_iter(1);show_prog = logical(show_prog(1);show_res = logical(show_res(1);% Initialize pop = zeros(pop_size,n);for k = 1:pop_sizepop(k,:) = randperm(n);end% Run the GAglobal_min = Inf;total_dist = zeros(1,pop_size);dist_history = zeros(1,num_iter);tmp_pop = zeros(4,n);new_pop = zeros(pop_size,n);if show_progpfig = figure(Name,TSP_GA | Current BestSolution,Numbertitle,off);Endfor iter = 1:num_iter% Evaluate Each Population Member (Calculate Total Distance)for p = 1:pop_sized = dmat(pop(p,n),pop(p,1); % Closed Pathfor k = 2:nd = d + dmat(pop(p,k-1),pop(p,k);endtotal_dist(p) = d; end% Find the Best Routemin_dist,index = min(total_dist);dist_history(iter) = min_dist;if min_dist 0 break; endend% R=unidrnd(PointNum,1,2);I=R(1);J=R(2);if IJ if JPointNum p2(1:I)=p1(1:I); p2(I+1:J)=p1(J:-1:I+1); p2(J+1:PointNum)=p1(J+1:PointNum); len0=D(p1(I),p1(I+1)+D(p1(J),p1(J+1); len1=D(p2(I),p2(I+1)+D(p2(J),p2(J+1); ds=len1-len0; else p2(1:I)=p1(1:I); p2(I+1:J)=p1(J:-1:I+1); len0=D(p1(I),p1(I+1)+D(p1(J),p1(1); len1=D(p2(I),p2(I+1)+D(p2(J),p2(1); ds=len1-len0; endelse if IPointNum p2(1:J)=p1(J:-1:1); p2(J+1:I)=p1(J+1:I); p2(I+1:PointNum)=p1(PointNum:-1:I+1); len0=D(p1(J),p1(J+1)+D(p1(I),p1(I+1)+D(p1(1),p1(PointNum); len1=D(p2(J),p2(J+1)+D(p2(I),p2(I+1)+D(p2(1),p2(PointNum); ds=len1-len0; else p2(1:J)=p1(J:-1:1); p2(J+1:I)=p1(J+1:I); len0=D(p1(J),p1(J+1)+D(p1(I),p1(1); len1=D(p2(J),p2(J+1)+D(p2(I),p2(1); ds=len1-len0; endend单钻头子程序2function leng=leng(p1,PointNum)global D;s=0;length=0;for i=1:PointNum-1 if i=1 s=D(p1(1),p1(2)+D(p1(1),p1(PointNum); else s=s+D(p1(i),p1(i+1); endendleng=s;孔坐标（部分数据）孔型A孔型B孔型CX1000Y243600X-100200Y360800X-110000Y420000X-10000Y301000X-101000Y202200X-123200Y523800X-100200Y246000X-101000Y207800X-123600Y420000X-100200Y322400X-101000Y212800X-128600Y471500X-101200Y122800X-101000Y217800X130600Y320400X-101324Y265174X-101000Y223200X-130600Y443200X-101324Y268324X101000Y355000X130800Y262600X-101324Y271474X-101200Y15000X-132200Y409200X-101324Y274623X-101200Y228400X-141400Y465800X-101324Y277773X-101200Y-3000X145000Y331800X-101324Y284072X-101200Y84000X145600Y246000X-101324Y287222X-101600Y155600X-148400Y479200X-101324Y293521X-101600Y165500X-152000Y227200X-101324Y296670X-101700Y149700X15400Y485800X-101324Y299820X-101700Y171400X-156800Y465800X-101400Y306200X-101800Y143800X-163200Y203600X-101400Y315600X-101900Y177300X167200Y127400X10200Y242600X102600Y627400X167200Y142000X102000Y246000X-103200Y86000X-167600Y443200X102000Y269600X104200Y677600X-168200Y222000X102000Y297200X-105000Y83800X-177600Y467000X102000Y301200X-106600Y373400X-187200Y479200X102000Y305000X-106600Y378200X188400Y423400X102000Y309000X-106600Y447900X-191800Y194600X102000Y312800X-107000Y86000X-193400Y467400X102000Y316800X-10800Y270600X-194800Y432600X102000Y320800X10800Y432000X198200Y127400X102000Y324800X-108200Y390000X198200Y142000X102000Y328600X-11000Y277000X207200Y480600X102000Y332600X-110000Y13200X-208200Y194600X102000Y336400X-110000Y-2000X217600Y489400X102000Y340400X-110300Y471500X224400Y376200X102000Y344400X110600Y633400X229800Y186000X102000Y348400X-112200Y-17400X-239000Y342600孔型D孔型E孔型FX-17400Y44100X10200Y800000X-311300Y33400X-1740