1 问题重述
过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本问题旨在提高某类打孔机的生产效能。
打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。
现有某种钻头，上面装有8种刀具a，b，c，? , h，依次排列呈圆环状，如图1所示。
a h g
f
e b
c d
图1：某种钻头上8种刀具的分布情况
而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18 s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。
不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。
2
表1：10种孔型所需加工刀具及加工次序
孔型 所需刀具
A a
B b
C a, c
D d, e*
E c, f
F G H h
I e, c
J f, c
g, h* d, g, f
一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。
请建立相应的数学模型，并完成以下问题：
（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。
（2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。
(i)针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？
(ii)研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。 2 问题分析
对于问题一（即单钻头作业时）,要求最优作业路线，钻头行进时间及最优作业的成本。因为有10种孔型，多种次序加工完成。所有我们先确定刀具的最优转换路线，再运用模型计算出最优路径和最短路线。由于打孔机是打完一个电板之后再按照原来的最优线路进行下一个电板，所以在打完一个电板的最后一个点之后，钻头应回到起始点，对于每种刀具而言，每个孔型的每个坐标只需加工一次，然后返回到出发点即可。而这与旅行商问题（Traveling Salesman Problem，TSP）相似，那么我们可以模拟蚁群算法、遗传算法或退火算法来进行求解。由于本题的数据比较小（单位转换之后），而蚁群算法又具有局部搜索速度快、收敛性良好的优点，所以我们通过模拟蚁群算法对本问题的最优线路和最短路径进行求解，用遗传算法对蚁群算法进行优化和检验。
对于问题二（即双钻头作业时），因为两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，现假设在过孔加工的任何时刻必须保持两钻头间距等于3cm（称为两钻头合作间距），我们运用遗传算法做出最优作业线路图，计算得出最优结果。
3
3 模型假设
(1)假定不考虑单个过孔的钻孔作业时间 (2)钻头作业中，将钻头看出一个质点 (3)刀具的转换时间相同
(4)假定钻头的行进速度匀速的，且都是相同的 (5)假定双钻头作业时，两钻头间的距离不小于3cm 4 符号约定
符号
符号说明
di,j
W
i孔和j孔之间的距离
钻孔作业的总成本
W1 W2
R
刀具行进所用的成本 刀具转换所用的成本 刀具行进的总路程
R1
刀具作业行进的路程 刀具转换行进的路程 n个孔构成的集合
R2
{V1,V2,V3????Vn} {T1,T2T3???Tn}
s1 s2
孔型集V的一个不重复的排列
钻头1的对刀点 钻头2的对刀点
A1i
第1钻头加工第i个孔
A2j U1
第2钻头加工第j个孔
钻头1的加工路径
4
续表 符号约定
符号
符号说明
m
?ij
蚂蚁中蚁群的数量
路径(i,j)的能见度 t时刻路径(i,j)上的信息量
?ij
?kij
kpij(k)
蚂蚁k在本次循环中留在路径(i,j)上的信息量 蚂蚁k在t时刻由位置i转移到位置j的概率
能见度的重要性(??0)
? ?
信息素的持久性(0???1)
信息素的衰减度
蚂蚁循环一周所释放的总信息量 第k只蚂蚁在本次循环中所走的路径长度
1??
Q
Lk
eij T1
点(i,j)是否在得到的最优路径上
钻头1的行进时间 钻头2的行进时间 染色体的适应度 钻头2的加工路径
T2
F(T)
U2
5