打孔机生产效能的提高.ppt

打孔机生产效能的提高,目录,问题关键,印刷线路板过孔加工费用占制版费用30%到40%，打孔机主要用于线路板打孔作业，提高打孔机生产效能可以降低制版费用，时间。,钻头上安有八种刀具，有些过孔需要多个工序且有次序要求。,分别给出单钻头和双钻头最优加工作业线路，时间，成本， 研究双钻头合作间距对加工路线和效率影响,问题重述,某些孔需多把刀具加工； 某些孔加工时刀具有次序限制； 钻头上有八把刀具，可顺逆旋转； 共十种孔型，但孔数量大； 不仅要研究单钻头打孔，还要研究双钻头打孔； 综上分析可知：这道题与TSP问题类似，但不同之处是某些孔 需多把刀具加工且加工有次序限制。因此我们要想办法把本 题转化为TSP问题求解。,问题分析,问题特点,本文框架,流程图：,成本 矩阵,蚁群 算法,方案一,不考虑单个过孔钻孔作业成本。 不考虑单个过孔钻孔作业时间。 钻头无损耗，不损坏。 钻头移动速度恒定。 钻头视为质点。,模型假设,已知线路板上各类孔型如表所示：,我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的多个孔的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次序，就把换刀方案确定了。,模型建立与求解,过孔转换,上述10种孔型可转化为：,处理后孔的数量由2124个变为2814个单孔，分别对2814个孔坐标 进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具， 这样的话，我们转换成TSP问题进行求解。,模型建立与求解,转换后的孔型,对刀具进行编号，18,每个空为三维坐标，前两维是位置，第三维是刀具编号。,模型建立与求解,孔型三维坐标,总加工花费,从i孔到j孔换刀次数,总加工时间,模型建立与求解,符号约定、公式,刀具编号：1，2，38,目标函数,模型建立与求解,问题一：,其中：（f:总成本，H：换刀成本，L：行进成本，Xt：行进时间，Ht:换刀时间。）,目标函数,模型建立与求解,问题二：,其中：（f1：钻头一成本，f2：钻头二成本，T1 ：钻头一时间，T2: 钻头二时间。）,模型建立与求解,问题一：,1.蚁群算法：,随着时间的推进，路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时的便是待优化问题的最佳解。,模型建立与求解,问题一：,1.蚁群算法,(一)、将三维坐标形成成本矩阵，即孔孔之间的刀具转换成本和行进成本之和。 (二)、采用蚁群算法进行计算。,模型建立与求解,问题一：,1.蚁群算法,初始化,随机放置蚂蚁,以每一只蚂蚁所在孔，作为起始城市,选择选下一个城市,返回到初始城市,还有可选城市？,更新信息素矩阵，即更新每路径上的信息素的量,满足停止条件？,输出最好的路径,Yes,No,No,模型建立与求解,问题一：,1.蚁群算法,成本：1197.2元 时间：1382.2秒,模型建立与求解,问题一：,2.贪心算法,(一)、换刀方案：d,e,f,g,h,a,b,c,f (二)、换刀时间：180秒 (三)、权值：距离,模型建立与求解,问题一：,2.贪心算法,算法流程图,模型建立与求解,问题一：,2.贪心算法,作业时间：267.68秒 成本：932.19元,d刀具加工图(单位：mil),模型建立与求解,问题一：,2.贪心算法,537(465)-522-525-518-514-510-506-503-507 -511-515-516-512-508-504-523-528-531-533 -536-524-517-513-509-505-520-521-527-530 -532-535-534-529-526-519-498-492-497-485 -486-487-493-500-499-488-489-494-502-501 -490-484-491-496-495-483-换h刀具,g刀具走刀路线：,模型建立与求解,问题一：,2.贪心算法,最终选择cst=0.6,csf=0.4计算出总费用为965.12元，加工时间为214秒,模型建立与求解,问题一：,2.贪心算法,遗传算法流程图,遗传算法实质是通过种群搜索技术，根据适者生存原则逐代进化，最终得到最优解或准最优解。,输出结果,结束,1,模型建立与求解,问题一：,3.遗传结合贪心算法,改良圈算法：（以m=233）为例,改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群， 令i=1，第一步：随机生成初始圈（初始解）：,第二步：交换u，v之间的顺序，则得到新路径：,模型建立与求解,问题一：,3.遗传结合贪心算法,改良圈算法：,评判标准为两次相邻路径的差值：,若f0 ,则以新路径替换旧路径，直到不能修改为止。,第三步：令i=i+1，若i=POP（种群规模）,算法结束，否则转向第一步,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,编码策略采用十进制编码，用随机数列,作为染色体(个体)，其中为避免在交叉后产生的染色体出现重复的基因（孔编号），限定,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,（2）种群初始化： 本文利用改良圈算法得到一个规模为50的种群。 （3）交叉 根据孔数的规模，本文采用单点交叉方案，取交叉概率pc=1。先从种群中随机选取两个父代（两个初始解）1和2：,用Logistic 混沌序列产生一个2到232之间的正整数，例如得到随机数21，则对相应基因进行交叉得到新染色体。,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,(4)变异 是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型中具体变异算子设计如下，首先根据给定的变异率(本模型选为 0.02)，随机地取两个在2 到232之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为初值利用Logistic混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新的染色体。,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,（5）选择 本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数最小的50个个体作为下一代个体。,采用圆盘赌法： 计算适应度函数值Fitness,模型建立与求解,问题一：,3.遗传结合贪心算法,模型建立与求解,问题一：,3.遗传结合贪心算法,(一)、换刀方案：d.c.b.a.b.g.f.e.d.c (二)、换刀时间：162秒 (三)、权值：距离,（1）用遗传算法进行计算。 （2）采用贪心算法进行搜索。,模型建立与求解,问题一：,3.遗传结合贪心算法,成本： 892.97元； 时间： 242.9s,换刀路径图,打孔路径图,模型建立与求解,问题一：,3.遗传结合贪心算法,成本：892.97元；时间：242.9s,成本：1197.2元，时间为1382.2秒,蚁群算法：,贪心算法：,成本：932.19元；成本：267.6754秒,遗传结合贪心算法：,模型建立与求解,问题一：,结论：,模型建立与求解,问题二：,钻头一：642.3 秒 成本：450.83 元 钻头二：1021.5 秒 成本：738.32 元,1.蚁群算法,总成本：1189.2 元 时间：1021.5 秒,模型建立与求解,问题二：,2.贪心算法,钻头一钻头二，d刀具的加工图,模型建立与求解,问题二：,钻头一： 总时间：213.909秒，总花费：360.66元 (其中换刀时间为：180秒, 行进时间：33.91秒) 钻头二： 总时间：234.28秒，总花费：577.26元 (其中换刀时间为：180秒，行进时间：54.28秒) 则双钻头： 总时间：234.28秒 总花费：937.92元,2.贪心算法,模型建立与求解,问题二：,2.贪心算法,可能冲突的点形成的距离矩阵 （以x=-50000mil划分）,模型建立与求解,问题二：,2.贪心算法,双钻头和钻间距与加工费用和时间的关系,模型建立与求解,问题二：,2.贪心算法,x:是合作间距,y:是加工费用,合作间距函数：,x:是合作间距 y:是加工时间,费用函数：,钻头同时工作时的生产效能，提出以下两种分配方案： 首先采用K-means聚类分析方法，以合作间距为依据将所有孔分为两大类，采用遗传结合贪心算法对两大类分别计算得到最优路径。 第一类初始类中心为：（-325400,554800） 第二类初始类中心为：（88800,919800）,模型建立与求解,问题二：,聚类分析,3.遗传结合贪心算法,模型建立与求解,问题二：,3.遗传结合贪心算法,聚类结果：,双钻头打孔算法流程图,开始,聚类为两类,输出下一起点,结束,按方案三，对两类分别计算,模型建立与求解,问题二：,3.遗传结合贪心算法,其中第一个钻头路径图,模型建立与求解,问题二：,3.遗传结合贪心算法,钻头一：,钻头二：,总时间：207.5s 作业成本：942.392元,模型建立与求解,问题二：,3.遗传结合贪心算法,单钻头： 总加工时间：242.9s 总加工费用：892.97元,双钻头： 总时间：207.5s 作业成本：942.392元,结论： 与单钻头相比，双钻头加工可以明显缩短加工时间，提高效率14.5%，但费用有增加5.5%。,模型建立与求解,模型评价及改进,本文亮点： 1.结合作业孔的作业要求，以目标权重（时间，成本或时间成本的加权和）为“距离”构造一个非对称的图，进一步建立了一个理论上相对完备的数学模型（TSP模型），理论上该模型的最优解就是全局最优解。 2.本文采用了改进的贪心算法以减少换刀次数为原则分别对问题