1、20120806,福建师范大学福清分校数学与计算机科学系,打孔机生产效能的提高,学生: 李欣儿 王伟杰 杨 京 指导老师: 林 娟 福建师范大学福清分校数学与计算机科学系,20120806,福建师范大学福清分校数学与计算机科学系,问题重述,1. 单钻头的孔群加工2. 双钻头的孔群加工,目标：提高打孔机的生产效能,刀具的旋转方向,基本要素：相邻刀具的旋转时间：18s钻头的移动速度：180mm/s钻头的行进成本：0.06元/mm刀具转换的时间成本：7元/min,两钻头合作间距,20120806,福建师范大学福清分校数学与计算机科学系,影响打孔机的生产效能的因素： 1. 单个过孔的钻孔作业时间2.
2、钻头的行进时间3. 刀具的转换时间注意: 因为同一孔型钻孔作业时间都是相同且刀具旋转一次所花费的时间远大于钻头在任意两孔之间的行进时间，所以要提高打孔机的生产效能首先我们考虑减少刀具的转换时间(即减少刀具的转换次数)其次考虑各个刀具所要打孔型点的最优路线。,问题分析,20120806,福建师范大学福清分校数学与计算机科学系,1. 影响刀具转换方案的因素：刀具的顺序固定，不能调换刀具可顺时针和逆时针旋转有的孔型需要多种刀具及规定的加工次序来完成如：C(a,c),E(c,f),G(d,g,f),I(e,c),J(f,c) 因为f,c及c,f有顺序,显然易知会出现f-c-f或c-f-c的情况,最少转
3、换次数大于等于8,且以c或f为开头时可能为8。 由d g f的顺序可知,以c或f开头时,最小转换次数大于8. 最优的刀具转换方案： d(D,G) c(E)b(B)a(A,C)h(F,H)g(F,G) f(E,G,J) e(D,I)c(C,I,J) 最小转换次数:9,刀具转换方案（单钻头）,20120806,福建师范大学福清分校数学与计算机科学系,孔群加工最优作业路线,我们将最优的刀具方案的各个刀具视为一个模块在求各个以刀具为模块的最短路径时,可将问题看作类TSP问题(注意:遍历所有点后不回到原点) 在连接以刀具为模块的各个模块时可看作TSP问题(注意:遍历所有点回到原点)中求得的最优路线去掉此
4、最优路线中相邻两点最大距离的连线,20120806,福建师范大学福清分校数学与计算机科学系,刀具转换方案和最优作业路线（双钻头）,1. 影响刀具转换方案的因素：单钻头孔群加工时包含的所有因素双钻头各自完成的时间2. 孔群加工的最优作业路线两钻头的合作间距两钻头路线同时变化固定长的一个钻头的路线,变化另一个钻头的路线路线中是否存在等待时间如: c刀具与f刀具,20120806,福建师范大学福清分校数学与计算机科学系,模型假设（1）假设打孔时的时间过小可忽略不计；（2）假设打孔时所耗效能忽略不计；（3）假设不出现断电或器具损坏问题； （4）假设打孔后的等待时间极短可忽略不计；（5）假设将钻头看作质
5、点,20120806,福建师范大学福清分校数学与计算机科学系,问题描述：有 n个城市,其相互间距离d为已知, 求合理的路线使得每城市都访问一次,且总路径为最短。TSP的数学模型如下所示:,TSP(旅行商问题),20120806,福建师范大学福清分校数学与计算机科学系,解决TSP问题的方法,贪心算法模拟退火算法改进的蚁群算法CONCORDE软件,20120806,福建师范大学福清分校数学与计算机科学系,算法简介,模拟退火算法:是模拟物理的退火过程。退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷 却,最后分子以低能状态排列,固体达到某 种稳定状态。 蚁群算法:是模拟自然
6、界蚂蚁寻找食物时在所经过的路径上留下一种挥发性的物质 (称为信息素), 从而引导后续蚂蚁走最短路径提出的一种算法。,20120806,福建师范大学福清分校数学与计算机科学系,设最优转换方案的刀具集合:,最优作业路线的模型,每一个刀具所需打孔的个数:,各个刀具的最优路线的孔的坐标集:,总最优作业路线的最短路程：D,20120806,福建师范大学福清分校数学与计算机科学系,计算结果（单钻头）,20120806,福建师范大学福清分校数学与计算机科学系,结果分析（单钻头）,以上两种方法它们具有以下两个共同特点:该类方法都是从若干解出发,通过对其邻域的不断搜索和当前解的替换来实现优化,一次能够处理大量模
7、式,而且不受搜索空间连续性的限制;该类方法都是在全空间并行搜索,且设有跳出局部最优的机制,具有较强的全局搜索能力。不同点：蚁群算法的搜索能力比模拟退火算法强,20120806,福建师范大学福清分校数学与计算机科学系,双钻头孔群最优路径模型,假设两个钻头的最优路线的时间分别为T1和T2,则双钻头孔群加工路线优化的目标函数为: 约束条件: 任意一个待加工的孔必须包括在其中一条加工路径中,且加工过程中两个钻头不发生碰撞。,20120806,福建师范大学福清分校数学与计算机科学系,双钻头孔群的合作间距模型,20120806,福建师范大学福清分校数学与计算机科学系,双钻头的最优转换方案,刀具转换A方案：
8、3-3（由于cf与fc相互制约的关系3-3变成了4-3）,刀具转换B方案：4-3,注意：根据单钻头中得到结果可估计出B方案优于A方案，但以下双钻头的计算过程是根据A方案进行的一系列处理。,20120806,福建师范大学福清分校数学与计算机科学系,双钻头孔群加工的分析和计算过程分析步骤：确定哪个钻头的最优路线不变,哪个钻头的最优路线变化根据f1(J)与c2(J)之前的时间和的大小关系来判断。2. 处理e(D,I)- d(D,G) -c1(C,E,I)的最优路径问题。 因为f1(J)与c2(J)制约的关系,要使时间作业成本更小, 首先先确定f1(J)与c2(J)应保持的间隔才避免不碰撞。 接着考虑
9、 双钻头不互相干扰的基础上 e(D,I)- d(D,G) -c1(C,E,I)倒过来的最优化作业路线。 (因为cf与fc刀具相互制约的关系, 可以把f(E,G,J)分为f1(J)和f2(E,G), c(E,C,I,J)分为c1(C,E,I)和c2(J), 且要求f1(J)要先于c2(J)完成。),20120806,福建师范大学福清分校数学与计算机科学系,3. 处理 f1(J)与c2(J)的最优路径问题： 已知: f1(J)要先于c2(J)完成,且受合作间距的影响。 目标: 完成f1(J),c2(J)所花总时间最少即所间隔的 时间T(f1c2)最短 4. 总时间的计算:若更新后的e(D,I) -
10、d(D,G) - c1(C,E,I)的时间和小于a(C,A) -h(H,F)- g(G,F)的时间和,则: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning否则(此处先不作考虑)5. 生产效能的计算: 生产效能提高 =(单一钻头花费的时间-双钻头花费的时间)/单一钻头花费的时间6. 作业成本的计算 : 作业成本 = 移动成本 + 旋转成本,20120806,福建师范大学福清分校数学与计算机科学系,经计算得出由f1(j)与c2(j)之前的时间和分别为81.12s 和67.48s比较得知a(C,A) - h(H,F)-g(G,F) - f1(j)的最短路径不改变.e(
11、D,I) - d(D,G)-c1(C,E,I)的路线受双钻头的合作间距的影响而改变。2. 由图1可知,因为c2-d-e的路线与f1-g-h-a中旋转时间的重复部分很多,重新计算的优化路径只有c2,d与e中的一部分数据。其中c2与f1中的部分的点(由3中可知只有两个点的坐标)时间有可能重叠(计算得知c2的最优路径并没改变)。而d中需要优化的点从f1-g-h-a第二次旋转结束时间开始,e中的点从f1-g-h-a第3次旋转结束时间开始。,计算过程,20120806,福建师范大学福清分校数学与计算机科学系,图1:从J(f)处逆序开始双钻头路线各个刀具的路程图,可能产生碰撞的e与a区域,可能产生碰撞d与
12、h区域,红黑曲线是旋转时间所能移动的路程,20120806,福建师范大学福清分校数学与计算机科学系,并用邻近交换算法计算得到路径变化后的d和e如图2,3所示,图2 左图为单钻头作业d刀具在D,G孔型处的最优化路径图(需要变化部分) 右图为双钻头作业d刀具在D,G孔型处满足合作间距的新路径图,20120806,福建师范大学福清分校数学与计算机科学系,图3 左图为单钻头作业e刀具在D,I孔型处的最优化路径图(需要变化部分) 右图为双钻头作业e刀具在D,I孔型处满足合作间距的新路径图,20120806,福建师范大学福清分校数学与计算机科学系,3. 根据合作间距的限制求的f刀具与c刀具最小的间隔为15
13、3mm,即 在出发153/180s后再出发,可保证双钻头互相不干扰。4. 由以上计算可知,作业的总时间比没有随着d-e中路径的改变而发生变化。 Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning = 20.29+3.47+3.36+1097.48/180+153/180+18.19+4*18 =124.257s 5. 生产效能提高 = (单一钻头花费的时间-双钻头花费的时间)/单一钻头花费的时间 = (250.181-124.257)/250.181 = 0.4973= 49.73%,20120806,福建师范大学福清分校数学与计算机科学系,6. 作业成本作业成本
14、= 移动成本1 + 旋转成本+移动成本2(刀具旋转时移动） = (124.257-18*4)s*0.06元/mm*180mm/s+7/60元/s*18s*6+575.041mm*0.06元/mm = 611.47元其中e,d路径变更时并没有改变路径的开始孔与结束孔的坐标编号则最优路径中各刀具的开始孔与结束孔的坐标编号如下:(D145,d,D123,d),(E51,c,E40,c),(B740,b,B568,b),(C206,a,C166,a),(F14,h,H2,h),(G20,g,F27,g),(J24,f,E51,f),(D21,e, D135,e),(C177,c,C231,c),201
15、20806,福建师范大学福清分校数学与计算机科学系,A. 两钻头合作间距对作业路线的影响,合作间距 = 3cm :1. 对d中点的影响: d中受影响部分的点的路程共有226 mm从d40= 185.292mm变到d40 =249.085mm路程差d =d40 d40 = 53.8mm2. 对e中点的影响: e中受影响部分的点的路程共有452.8mm从 e87= 452.11mm变到e87 =519.03mm。路程差 e=e87 e87 = 66.90mm 由数据得知两变化的路径所花费的时间和不足1s.,20120806,福建师范大学福清分校数学与计算机科学系,合作间距的影响,20120806,
16、福建师范大学福清分校数学与计算机科学系,B. 两钻头合作间距对生产效能的影响生产效能提高 = (单一钻头花费的时间-双钻头花费的时间)/单一钻头花费的时间*100%双钻头的作业时间: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning 其中受合作间距影响的只有 Tf1c2,而Tf1c2由钻头在J处的最小间隔所决定且是一定的所以两钻头合作间距并没有对生产效能产生影响。,20120806,福建师范大学福清分校数学与计算机科学系,结论,解决TSP问题时，蚁群算法的搜索能力比模拟退火算法强。使用双钻头能大大提高生产效能将近五成(计算结果为49.73%)。合作间距对作业路线产生微小变化,对生产效能的提高影响不大。注：此次双钻头采取的并不是 最优刀具转化方案下得出的结果。,20120806,福建师范大学福清分校数学与计算机科学系,谢谢！,
