打孔机生产效能的提高

中文摘要：

基于过孔是印刷线路板<也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机在加工作业时，钻头的行进时间和刀具的转换时间是影响生产效益的两个因素。因此在完成一个电路板的过孔加工时，钻头行进时间和刀具转换总时间越短，生产效益就越高。钻头行进总时间由钻头进行路线决定，而刀具转换总时间由线路板上由各孔的位置以及钻头行进方案决定。首先对刀具行进路径进行建模，应用蚁群算法对行进的最优线路进行求解，并得出刀具行进时间。考虑刀具转换一次的时间均大于一块电路板上任意某个孔型的打孔总时间，而若对所有的孔求最优路线，刀具转换的总时间将非常大<不符合实际生产），故采用刀具转换次数最少的方案作为刀具转换方案，通过刀具转换方案求的最优行进路经的总和，同时求得刀具转换的最优时间。再根据钻头行进总成本和刀具转换总成本，可得单钻头作业成本。b5E2RGbCAP

当打孔机设计成双钻头时，由于作业时各钻头相互独立，且有合作间距的限制，因此在解决双钻头最优作业方案时，我们在单钻头作业的基础上，对双钻头的孔群加工优化路径进行数学建模，采用遗传算法双质点操作对行进的最优线路进行求解，得出双转头行进的最优时间，同时保证两转头行进间距在要求范围之内。利用分析单钻头的行进时间和作业成本的方法，得出双钻头的在最优作业路线条件下的行进时间和作业成本。p1EanqFDPw

关键字：打孔机 生产效能 蚁群算法 最短路径

问题重述：

1. 附件1提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔<mil）<也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路<包括刀具转换方案）、行进时间和作业成本。DXDiTa9E3d

2. 为提高打孔机效能，现在设计一种双钻头的打孔机<每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm<称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。RTCrpUDGiT

）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？5PCzVD7HxA

<ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。

打孔机生产效能的提高

1. 问题分析

本文就提高某打孔机的生产效能而做出分析，所谓生产效能就是指单位时间内的生产能力、加工效率。所以要提高打孔机的生产效能，我们可以使钻头行进时间和刀具转换总时间尽量短，所得到的生产效益会更高。jLBHrnAILg

对于单钻头，我们首先画出所有点的分布图，确定该电路板的对角线大概是，而且行进速度是，粗略估计行进的时间不会很长。对行进的速度和刀具的转换时间考虑，发现刀具的转换时间要比行进时间大得多，所以我们便想做到刀具的转换时间最短，才是最优的方法。所以我们使用蚁群算法，计算出所有点的最短距离和刀具转换次数最少所要走的最短距离，将两者进行比较，得到最优结果。xHAQX74J0X

对于双钻头，因为两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，现假设在过孔加工的任何时刻必须保持两钻头间距等于<称为两钻头合作间距），我们运用遗传算法做出最优作业线路图，计算得出最优结果。LDAYtRyKfE

2. 模型假设

1) 单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，现假定对于同一孔型钻孔作业时间都是相同的；

2) 为了计算行进费用，需要计算行进时间，为了简化问题，这里假定打孔机的行进是匀速的运动。

3) 假定针对不同孔型加工作业时，刀具的转换时间相同；

4) 在计算两孔之间距离时，为简化问题，假设打孔机的钻头为一质点。

5) 为避免钻头间的触碰和干扰，假定保持两钻头间距不小于

3. 模型建立

1、单钻头模型：对于其一给定尺寸的孔，调整好对应的刀具后，从下刀点开始沿着使该刀具总路程最短的轨迹，从一个孔移动到另一个孔，直到该类孔中的所有对象都被加工完毕，再转换刀具进行下一尺寸的其它孔的加工，如此安排。把问题描述成以下优化模型：Zzz6ZB2Ltk

1) 变量设计。设有n个孔的集合……，设表示集合中任意两孔、表示集合中两孔之间的距离、M为行进总路程。

2) 目标函数。需要在孔集合中，找到一个不重复的全排列，令，求M的最小值。

3) 约束条件：加工路径从一个孔出发，对每一个孔只加工一次遍历每一个孔，最后回到起点，包括刀具转换在内。

4) 优化算法：蚁群算法。

图一：刀具的转换流程及刀具对应的打孔孔型

2、双钻头模型：双钻头在孔群加工中，两个钻头同时加工，每个钻头加工时间并不确定，那么单一工间的加工时间由耗时较长的钻头决定。dvzfvkwMI1

假设两个钻头的对刀点分别为和，和分别表示第一个钻头加工的第i 个孔和第2 个钻头加工的第j 个孔，则两条加工路径、分别为rqyn14ZNXI

约束条件：任意一个待加工的孔必须包括在其中一条加工路径中，且加工过程中两个钻头不发生碰撞。

4. 模型求解

4.1单钻头问题结果分析

对于单钻头生产方式，钻孔方式上采用一种刀具钻完对应的全部孔在转换刀具进行下一种刀具对其对应孔型的钻取方式，工作路线采用蚁群算法，通过MATLAB进行数据处理，得出相应路径最优图形如下<按顺序依次为EmxvxOtOco

刀具:defghabcf

孔型:DGDIJFGHFACBCEIJEG）。

word/media/image29_1.png

word/media/image30_1.png

下表为各刀具的行程<单位： mil）

依上表可知，在单钻头作业的最优线路条件下，可得各种刀具作业路程总和

为：62.989e+004 mil。以下为我们为各刀具设定的始终点<1/100mil）：

上表各点距离和为选取转换前进的路程1.2471e+004mil，则加上前进的路程，可知该路线总路程为

Shortest_Length= 64.2361e+004(mil>=16315.97）

所有钻头的行进速度都是相同的，为，且所有钻头的刀具钻换时间为

12*18=216）

时间方面：作业行进时间=最短距离/钻头行进速度=90.64427）

作业总时间=钻头行进时间+钻头转换时间=306.64）

成本方面：行进成本=行进时间*行进成本=978.9594(元>

作业转换成本=转换次数*转换成本=25.2<元）

作业总成本=行进成本+作业转换成本=1004.159<元）

即：此法生产，需用时306.64），耗费1004.159<元）。

4.2双钻头问题结果分析

我们现在在模型建立上有一些想法，但是在利用算法实现想法的过程中遇到一些困难，因此并没有成功通过算法把更优的解算出。SixE2yXPq5

5. 模型评价与改进

该模型的分析过程清晰、简单易行，且经得住实践的考验。在单钻头问题上，此模型采取了单刀具对应孔型完成再进入下一道具的方式，即任一种刀具，先完成其所能钻取的孔型后，再进入下一孔型的钻取，而每种刀具的工作路线都是通过蚁群算法方式得出的最优解。如此操作，既减少了道具不断转换带来的时间损耗，提高了作业效率，又可以尽可能降低作业的成本。本模型是一比较高效率的生产模型，却不是一个十分省钱的生产模型，1000多元的生产成本确实是高了些。而对于双钻头模型问题，此模型采用遗传算法，以遗传算法双质点操作优化的优势，取代了单钻头问题中蚁群算法只能单质点优化路线的缺陷，是较为优化的。本文只通过一组实验数据分析得出结果，会有误差，所以在此基础上，用多组数据分析，会更好的减小误差，也可以对做模型进行进检验。总的来说该模型还是能比较完整的解决问题的！6ewMyirQFL

参考文献

【1】 姜启源等，数学模型<第四版），北京：高等教育出版社，2018

【2】 韩明，王家宝等，数学实验，上海：同济大学出版社，2009

【3】 罗万成，大学生数学建模案例精选，成都：西南交通大学出版社，2007

【4】 周明, 孙树栋，遗传算法原理及应用，北京：国防工业出版社，2005

【5】 李士勇，陈永强，蚁群算法及其应用，哈尔滨：哈尔滨工业大学出版社，2004

【6】 曾峰等，印刷电路板）设计与制作，北京：电子工业出版社，2002

附录：

m=10。Alpha=1。Beta=5。Rho=0.1。NC_max=200。Q=100。%为使程序运行速度更快，取蚂蚁数为10kavU42VRUs

c=[x,y]。

n=size(c,1>。 %n表示问题的规模<电路板上孔的个数）y6v3ALoS89

D=zeros(n,n>。 %D表示完全图的赋权邻接矩阵M2ub6vSTnP

for i=1:n

for j=1:n

if i~=j

D(i,j>=((c(i,1>-c(j,1>>^2+(c(i,2>-c(j,2>>^2>^0.5。

else

D(i,j>=eps。 %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps<浮点相对精度）表示0YujCfmUCw

end

D(j,i>=D(i,j>。 %对称矩阵

end

end

Eta=1./D。 %Eta为启发因子，这里设为距离的倒数eUts8ZQVRd

Tau=ones(n,n>。 %Tau为信息素矩阵sQsAEJkW5T

Tabu=zeros(m,n>。 %存储并记录路径的生成GMsIasNXkA

NC=1。 %迭代计数器，记录迭代次数TIrRGchYzg

R_best=zeros(NC_max,n>。 %各代最佳路线7EqZcWLZNX

L_best=inf.*ones(NC_max,1>。 %各代最佳路线的长度lzq7IGf02E

L_ave=zeros(NC_max,1>。 %各代路线的平均长度zvpgeqJ1hk

while NC<=NC_max %停止条件之一：达到最大迭代次数，停止NrpoJac3v1

%% 蚁群算法MATLAB程序第二步：将m只蚂蚁放到n个孔上

Randpos=[]。 %随即存取

for i=1:(ceil(m/n>>

Randpos=[Randpos,randperm(n>]。

end

Tabu(:,1>=(Randpos(1,1:m>>'。

%% 蚁群算法MATLAB程序第三步：m只蚂蚁按概率函数选择下一个孔，完成各自的周游

for j=2:n %所在孔不计算

for i=1:m

visited=Tabu(i,1:(j-1>>。 %记录已打过的孔，避免重复访问

J=zeros(1,(n-j+1>>。 %待打的孔

P=J。 %待打孔的选择概率分布

Jc=1。

for k=1:n

if length(find(visited==k>>==0 %开始时置0

J(Jc>=k。

Jc=Jc+1。 %打过的孔个数自加1

end

end

%% 下面计算蚁群算法MATLAB程序待打孔的概率分布

for k=1:length(J>

P(k>=(Tau(visited(end>,J(k>>^Alpha>*(Eta(visited(end>,J(k>>^Beta>。 1nowfTG4KI

end

P=P/(sum(P>>。

%% 按概率原则选取下一个孔

Pcum=cumsum(P>。 %cumsum，元素累加即求和

Select=find(Pcum>=rand>。 %若计算的概率大于原来的就选择这条路线fjnFLDa5Zo

to_visit=J(Select(1>>。

Tabu(i,j>=to_visit。

end

end

if NC>=2

Tabu(1,:>=R_best(NC-1,:>。

end

%% 蚁群算法MATLAB程序第四步：记录本次迭代最佳路线

L=zeros(m,1>。 %开始距离为0，m*1的列向量tfnNhnE6e5

for i=1:m

R=Tabu(i,:>。

for j=1:(n-1>

L(i>=L(i>+D(R(j>,R(j+1>>。 %原距离加上第j个孔到第j+1个孔的距离HbmVN777sL

end

L(i>=L(i>+D(R(1>,R(n>>。 %一轮下来后走过的距离

end

L_best(NC>=min(L>。 %最佳距离取最小

pos=find(L==L_best(NC>>。

R_best(NC,:>=Tabu(pos(1>,:>。 %此轮迭代后的最佳路线V7l4jRB8Hs

L_ave(NC>=mean(L>。 %此轮迭代后的平均距离83lcPA59W9

NC=NC+1 %迭代继续

%% 蚁群算法MATLAB程序第五步：更新信息素

Delta_Tau=zeros(n,n>。 %开始时信息素为n*n的0矩阵mZkklkzaaP

for i=1:m

for j=1:(n-1>

Delta_Tau(Tabu(i,j>,Tabu(i,j+1>>=Delta_Tau(Tabu(i,j>,Tabu(i,j+1>>+Q/L(i>。 %此次循环在路径，j>上的信息素增量AVktR43bpw

end

Delta_Tau(Tabu(i,n>,Tabu(i,1>>=Delta_Tau(Tabu(i,n>,Tabu(i,1>>+Q/L(i>。 %此次循环在整个路径上的信息素增量ORjBnOwcEd

end

Tau=(1-Rho>.*Tau+Delta_Tau。 %考虑信息素挥发，更新后的信息素2MiJTy0dTT

%% 蚁群算法MATLAB程序第六步：禁忌表清零

Tabu=zeros(m,n>。 %直到最大迭代次数

end

%% 蚁群算法MATLAB程序第七步：输出结果

Pos=find(L_best==min(L_best>>。 %找到最佳路径<非0为真）gIiSpiue7A

Shortest_Route=R_best(Pos(1>,:> %最大迭代次数后最佳路径uEh0U1Yfmh

Shortest_Length=L_best(Pos(1>> %最大迭代次数后最短距离IAg9qLsgBX

subplot(1,2,1> %绘制第一个子图形WwghWvVhPE

DrawRoute(c,Shortest_Route> %画路线图的子函数asfpsfpi4k

subplot(1,2,2> %绘制第二个子图形ooeyYZTjj1

plot(L_best>

hold on。

plot(L_ave,'r'>

title('平均距离和最短距离'> %标题

% 蚁群算法MATLAB程序子函数

function DrawRoute(c,R>

N=length(R>。

scatter(c(:,1>,c(:,2>>。

hold on

plot([c(R(1>,1>,c(R(N>,1>],[c(R(1>,2>,c(R(N>,2>],'g'>BkeGuInkxI

hold on

for ii=2:N

plot([c(R(ii-1>,1>,c(R(ii>,1>],[c(R(ii-1>,2>,c(R(ii>,2>],'g'>PgdO0sRlMo

hold on

end

title('旅行商问题优化结果 '>

“深圳杯”全国大学生数学建模D题答案