优秀论文 提高打孔机生产效能.doc

JINGGANGSHAN UNIVERSITYD题提高打孔机生产效能本组成员:10数本一数学与应用数学俞子骏1807960325710数本一数学与应用数学林文涛1517081834510化工本二化学工程与工艺过武厚18970672042指导老师：杨云苏提高打孔机生产效能摘要过孔是卬刷线路板的重要组成部分之一，过孔的加工费用通常占制板费用的 30%到40%o木文对印刷线路板过孔的生产效益如何提高进行了探究为了提高 生产效能，我们可以通过缩短打孔机的作业、刀具转换、转头行进吋间来实行， 因此路径的优化问题是印刷电路板打孔机性能的重要指标我们将此最优化问题 分成两种情况讨论:一种是使刀具的转换次数最少，即确定刀具的最佳转换方案, 对和应的孔型进行打孔；另一•种是使刀具经过的总路程最小，即从一个给定的孔, 沿着刀具总的路程最短的轨迹，从第一个孔串联另一个孔，直到线路板上的全部 孔都被加工完毕因为蚁群算法是一种新型的模拟优化方法，且具有高效的有效 性和应用价值所以我们对以上两种情况均采用了蚁群算法最后我们应用 Mat lab对这两种情况分别进行了计算，得岀结果如下：对于情况一，其最短距 离为 1. 71279^+006,行进时间为 9.515530+003（s）,作业成本为 102788. 4（元）； 对于情况二，其最短距离为1. 3659819 e +007 （m/n）,行进吋间为4.40652幺+004（$）,作业成本为95651 （元）。

在本文改进处，我们还对作业成本 问题进行了最优化处理，使得对本文问题的分析更加全面关键词： 蚁群算法 Mat lab 最优化1 •问题重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工 费用通常占制板费用的30%到40%,打孔机主要用于在制造印刷线路板流程中的 打孔作业本问题旨在提高某类打孔机的生产效能打孔机的生产效能主要取决于以下儿方面：（1）单个过孔的钻孔作业时间， 这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业吋间都是 相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作 业时，刀具的转换吋间H前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔现有某种钻头，上面装有8种刀具8, b, c,・・・，h,依次排列呈圆环状,如图1所示r a0 b&hc合ogdf图1某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换在加工作业吋，一种刀具使用完毕后，可 以转换使用另一种刀具相邻两刀具的转换时间是18 s,例如，由刀具&转换 到刀具b所用的吋间是18s,其他情况以此类推作业时，可以采用顺时针旋转 的方式转换刀具，例如，从刀具8转换到刀具b；也可以采用逆时针的方式转换 刀具，例如，从刀具a转换到刀具h。

将任一刀具转换至其它刀具处，所需吋间 是相应转换吋间的累加，例如，从刀具a转换到刀具c,所需的吋间是36s （采 用顺时针方式）为了简化问题，假定钻头的行进速度是相同的，为180 mm/s, 行进成本为0. 06元/mni,刀具转换的时间成本为7元/mino钻头在行进过程中可 以同时进行刀具转换，但相应费用不减表1 10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, C一块线路板上的过孔全部加工完成后，再制作另一块线路板但在同一•块线 路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种 以上刀具加工的过孔，只要保证所需刀具加工次序正确即可请通过建立相应的数学模型，完成以下问题：附件提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔（mil） （密尔也称为毫英寸，1 inch=1000mil）,请给出单钻头作业的最优作业线路（色 括刀具转换方案）、行进吋间和作业成本2 •问题假设（1） 单个过孔的钻孔作业吋间，这是由生产工艺决定，为了简化问题，现假定 对于同一孔型钻孔作业时间都是相同的；（2） 为了计算行进费用，需要计算行进时间，为了简化问题，这里假定打孔机 的行进是匀速的运动。

3） 假定针对不同孔型加工作业吋，刀具的转换吋间相同；（4） 在计算两孔之间距离时，为简化问题，假设打孔机的钻头为一质点5） 为避免钻头间的触碰和干扰，假定保持两钻头间距不小于3伽3. 符号说明V：所用孔的集合J：集合中任意2个孔的距离行进总距离Allowed,:蚂蚁R下一步允许选择的城市过孔P：信息索挥发系数a :信息卅发因子0：期望启发因子Pg 在川寸刻蚂蚁£由兀素，转移到元素J的效率偽⑴：启发函数5⑴:残留信息量△殆（小 第£只蚂蚁在木次循环中留在路径（门）上的信息量Q:信息强度L”第K只蚂蚁在木次循环中所走的路径的长度d..:集合中i孔和/孔的距离Z：加工总费川Z,：钻头的行进费用乙：刀具的转换费川f屛打i孔需要种加种刀具 fjn:打丿•孔需要“种刀具4. 问题分析经分析，我们要解决的问题是提高打孔机的生产效能，而打孔机的生产效能 主要取决于以下三个方面：(1)单个过孔的钻孔作业吋间；(2)打孔机钻头的行 进时间；(3)针对不同孔型加工作业吋，刀具的转换吋间由于单个过孔的作业 时间是相同的，现要提高打孔机的生产效能，方法有两个:一•个是减少钻头的行 进时间，一个是减少刀具的转换时间，即可转换为路线的优化问题。

我们可以从 这两个方法入手，一•是先确定刀具的最佳转换方案，通过钻头的转换次序，对相 应的孔型进行打孔；一•是从一•个给定的孔，沿着刀具总的窄程最短的轨迹，从第 一个孔串联另一个孔，直到线路板上的全部孔都被加工完毕，且所经过的总路程 最小对于这种类型的最优化问题，我们可以运用蚁群算法來解决，进而确定行 进吋间和作业成本5. 模型的建立基于题意,我们可以把问题视为一个最优化线路问题，经过分析，我们可以从 两种情况入手，一-种是先确定刀具的最佳转换方案，通过钻头的转换次序，对相 应的孔型进行打孔;另一-种是对一-种指定的孔型沿着使刀具打孔的路程最短，直 到该类孔全都被加工完毕，再进行下一尺寸的孔的加工，如此循环5.1模型一的建立：(1)变量设计：设V = {vpv2,v3,……“}表示所用孔的集合，示集合中任意2个孔 的距离，则行进总距离M = 工心)⑵口标函数:1.. 约束条件：6.1. 加工路径从一•个孔岀发，历经每个孔，最后回到起点;6.2. 刀具转换次数最少，即最佳刀具转换方案2.. 步骤：6.1. 化蚁群：初始化蚁群参数，设置蚂蚁数量，初始化信息素，设q(o)=c (C为 常数)；6.2. 蚂蚁移动：蚂蚁依据前面蚂蚁所留下的信息素和自己的判断选择路径，完成 一次循环；6.3. 释放信息素：对蚂蚁所经过的路径按一•定的比例释放信息素；6.4. 蚁群：根据口标函数对每蚂蚁的适应度做出评价；6.5. 终止条件，即最短路径，输出最优解。

否则，算法继续进行；6.6. 素的挥发：信息素会随着时间的延迟而不断消散6.1. 2模型二的建立:(1)变量设计:设卩=仏宀宀，……"}表示所用孔的集合，〃伉R)表示集合中任意两个孔 的距离⑵口标函数：在孔集合v中，找一-个不重复的全排列r = {r1,r2,...rj,令minM =h， 求M的最小值jj>o且心丿‘6.1. 约束条件：加工路径从-个孔出发，对每一个孔只加工一次遍历每一个孔，最后冋到起 点，包括刀具转换再内6.2. 步骤：6.1. 初始化问题的集合规模〃，蚂蚁的数量加，并将加只蚂蚁放到"个过孔上；6.2. 程序执行需要循环m = m + l；6.3. 执行循吋蚂蚁的个数k = k + \；6.4. 对其中第£只蚂蚁，根据下面公式(1)选择过孔八 并继续进行前进;6.5. 把蚂蚁选择的过孔./•加入到底£只蚂蚁的中，并修改表Allowed ；6.6. 对于第k只蚂蚁如果没有行走玩所有〃个过孔，则转到第四步，若所有过孔 均已走完，则继续往下执行；6.7. 如果蚂蚁数R小于蚂蚁总数加，则转到第三步，直到加只蚂蚁都走完"个过 孑L,继续往下执行；6.8. 由②、③随吋更新蚂蚁行走的信息量，且找出税只蚂蚁中，所走路径最短的 值，并保存；6.9. 若循环的总次数没有达到最人的循环次数，则将继续转到第二步进行执行， 若满足结束条件循环将结束，同时输出结果数据。

1 3蚁群算法5. 3.1算法简介:蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法，模拟蚂蚁群体智能的人工蚁群算法具有分布计 算、信息正反馈和启发式搜索的特点，在求解组合优化问题中获得广泛应川满足结束条件输出程序计算结果结束5. 3. 3算法实现：、s e allow,s 电 allowk(1)(1)状态转移规则:用=工氐⑴『•阮⑴］"seallowk0tabuk (k = 1,2,・.・,〃)用以记录蚂蚁k当前的过孔为记忆列表，式中硝⑴表示在r 时刻蚂蚁R由元素『转移到元素j的效率；Allowed,表示蚂蚁R下一步允许选择 的过孔；Q表示信息启发因子，表示轨迹的相对重要性；0表示期望启发因子， 表示能见度的相对重要性；％(/)表示启发函数，為⑴=1/心；©表示残留信息 量2)全局规划规则:©(/ + 〃)= (1 + /7)XT..(f) + Ar..(r)(2)k(3)d,若第£只在本次循环中(/../•)Lk0, elseJ(4)式中卩表示信息素挥发系数；表示第k只蚂蚁在本次循环中留在路径a,力上的信息量；Q表示信息强度，设为常数；S表示第K只蚂蚁在本次循环中所 走的路径的长度。

1 模型的求解6.1模型一的求解 6.1.1刀具的最佳转换方案我们首先确定刀具的最佳转换方案，有题口所知，刀具的旋转可以有顺时针旋转和逆吋针旋转，我们把其全部列出:顺时针:方案 1： a—〃一>€—>〃一>g—>/?TgT/—>«T〃一>C'方 3: c - d - c -» J - g - h ―» ci - b ―» c -» cl - e - j力•案 4： dfeif TgihiaibTcidTeif方案 5： et /-»gT/?T a Tb—>c-»〃一»€—>/—>gT/方案 6： fTg—>/?―>a—>/?—>(?-»〃一>£—> >£—>〃一>/?TQTb—>C-> T〃一>C方 8 ： h - ci - b —c ―》cl - c - f ―g _》h -》c - d -》c逆时针：方案 9： a—〃一>cTZ2-»a-»/?->gTjf方案 10： b—>g—>/z-»g—>/—>•幺一>〃tc—>Z?tgt/z—>g—>/力•案 11： c T b —> a —> h —> g t f ->«—>〃 tc—>bTaT/?-»g if案 12： d ―> c ―> b ―> ci ―> h —> g —> j ―> € ―> cl —> c ―> b —> ci。