提高打孔机工作生产效能的数学模型
摘要
本文主要解决了提高打孔机生产效能的问题。路径的优化程度是印刷电路板
打孔机性能的重要指标。欲提高打孔机的生产效率可通过优化孔群加工路径，缩短刀具转换时间来实现，本文建立了空群加工路径规划的数学模型，并将其归纳为多目标组合优化问题。
孔群加工路径优化问题为典型的旅行商问题，简称为TSP。对于单钻头的孔群路径优化问题多利用蚁群算法，但由于线路板孔数过多，单一的蚁群算法会在程序运算求解时面临很大的困难，而我们用matlab作出过孔中心散点图后发现，很多
同种类型的孔分布相对集中在不同的区域，有的甚至呈完美的直线排列，因此，
我们先把大规模孔点分成若干个子分区，并且分区时尽量将同类型相对集中的孔分在同一区域，从而减少换刀次数。当得到大规模孔点的子分区后，我们对呈直线排
列的孔群区域采用正交路径法，其余子分区采用蚁群算法求取局部最优解，最后
把每个子区域的中心用蚁群算法求取它们之间的最优路线，从而得到整个TSP问题的满意解。
对于双钻头进行孔群加工，我们通过修改用于单钻头孔群加工路径优化的遗传算法中染色体的表达方式和适应度函数的计算方法, 得到基于双钻头的孔群加工路径优化算法。实验结果表明, 与单钻头的最优加工路径相比, 在不同钻孔速度下使用双钻头同时加工的新算法都能节省近一半的加工时间, 有效提高了孔群加工的效率
关键词：路径优化 正交路径法 蚁群算法 遗传算法
问题重述
在印刷线路板的制造过程中，由打孔机完成的过孔所需要的加工费用占制板费用的30%到40%，本文旨在通过建立数学模型来提高打孔机的生产效能。我们主要研究并解决的是如下两个问题：
1. 由于打孔机的生产效能主要取决于钻头的行进时间和道具的转换时间，因此
我们要根据已知线路板上过孔中心的坐标数据，建立数学模型求解单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。
2. 建立数学模型，针对同一线路板，研究在双钻孔作业下的最优作业线路、行
进时间和作业成本，计算相对于单钻头作业其生产效能提高的幅度，并研究两钻头间距对作业路线和生产效能的影响。
模型假设：
1. 对于同一孔型钻孔作业时间相同且不计单个过孔的钻孔作业时间 2. 钻头的行进速度是相同 3. 将钻头看作质点。
4. 刀具在行进过程中可以同时进行刀具转换，但相应费用不减。
符号说明
α: 启发因子，信息素的重要程度，一般取值1.0。 β：期望因子，城市间距离的重要程度，一般取值2.0。
θ：信息素挥发系数，一般取值0.5。 m: 蚂蚁数量。 n: 孔的个数。
问题分析
背景分析：
在印刷线路板的制造过程中，由打孔机完成的过孔所需要的加工费用占制板费用的30%到40%，孔群加工路径规划对于提高多孔类零件的加工效率和质量具有重要意义。而如何事先规划孔群的加工路径,以达到缩短刀具移动路径、减少换刀次数等, 是孔群加工的关键问题。这类问题在本质上属于多目标优化问题。
问题一分析：
问题二分析
模型建立
模型一
问题一位路径与时间的多目标组合优化问题，目前求解多目标优化问题很多方法，如多目标加权法、分层序列法、约束法和目标规划法等，均需事先由决策人员给出目标权值向量，而将具有不同的物理意义和量纲的路径与时间给出合理的权值向量本身就很困难，因而我们将该多目标问题转化为成本这一但目标问题，因为路径越短，行进成本与行进时间就会越少，换刀时间越少，换刀成本也会越
少，从而在成本最优条件下求出的孔群加工路径能够很好的综合出路径与时间的联合最优解。因此，我们将问题转化为求最小化成本的孔群加工路径规划问题。 总加工成本包括刀具行进成本与换刀成本
1) 刀具行进成本
从先前位置移动到当前位置的成本。设两个位置之间的距离为Dij, 单位长度的刀具行进成本为a,则完成N个孔加工的刀具行进成本为:
N
N
f1=
i=1
a?Dij?eij
j=1,j≠i
其中eij∈{0,1},eij=1表示边(i,j)在得到的优化路径上。
2) 换刀成本
如果加工孔i使用的刀具在加工孔j时不再使用, 那么必须执行换刀操作 I j 以得到所需刀具。设p ij 为加工孔i 后再加工孔j 所需的换刀时间, b 为单位时间的换刀成本, 则完成N 个孔加工的换刀成本为:
N
N
f2=
i=1
b?pij?eij
j=1,j≠i
从而目标函数（最小化总生产成本）为
min(f1+f2)
在上述问题中, 如果将对同一孔进行不同加工操作(有的孔型需要多种刀具) 看作是对不同孔的遍历, 则原问题转化为找到N个孔的某一种排列,使得目标函
数( f 1 +f 2 ) 的值最小, 约束条件是加工路径从一个孔出发，对每一个孔只加工一
次，且遍历每一个孔，最后回到起点，包括刀具转换在内。有些孔的加工有先后次
序(如对某些孔加工时有刀具顺序)，这是一个单目标组合优化问题。
模型二
引入双钻头对孔群同时加工是提高钻孔效率的有效途径。而孔加工过程所耗时间主要包括钻头移动和换刀的时间，对于双钻头我们用时间作为目标函数来求其加工路径。
在双钻头孔群加工中, 两个钻头同时加工,每个钻头加工时间并不确定,那么孔群的加工时间由耗{{{时较长的钻头确定。假设两个钻头的对刀点分别为S1和S2,A1i和A2j分别表示第1个钻头加工的第i个孔和第2个 钻头加工的第j个孔, 则两条加工路径U1、U2 分别为{ S1—A11—A1i—S1 } , { S2—A21—A2j—S2}。 若相应的加工时间分别为T1 和T2, 则双钻头孔群加工路径优化的目标函数为:
T T1 >??2min T= 1 (1)
T2 T1≤T2
约束条件为任意一个待加工的孔必须包括在其中一条加工路径中, 且加工过程中两个钻头间距不小于3厘米。