一、问题重述
过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，打孔机主要用于在制造印刷线路板流程中的打孔作业。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。本问题旨在解决某类打孔机的生产效能问题。
打孔机的生产效能主要取决于：（1）单个过孔的钻孔作业时间，由生产工艺决定；（2）打孔机加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。
某种钻头装有8种刀具，8种刀具的顺序固定，不能调换。加工作业时，一种刀具使用完毕后，可转换使用另一种刀具。相邻两刀具的转换时间是18s。作业时，可顺时针旋转转换刀具，如刀具a刀具b；也可逆时针旋转转换刀具，如刀具a刀具h。将任两个刀具转换，所需时间是相应转换时间的累加。假定钻头的行进速度相同，为180mms，行进成本为006元mm，刀具转换的时间成本为7元mi
。刀具行进过程中可同时转换刀具，但相应费用不减。
不同的刀具加工不同的孔型，有的只需一种刀具来完成，有的需要多种刀具及规定的加工次序来完成。表1为10种孔型所需加工刀具及加工次序（表示该孔型不限制加工次序）。
表1：10种孔型所需加工刀具及加工次序
孔型
A
B
C
D
E
F
G
H
I
J
所需刀具
a
bacdecfghdgfhecfc
同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用多种刀具加工的过孔，只要保证所需刀具加工次序正确即可。
建立相应的数学模型，并完成以下问题：（1）由附件1提供的某块印刷线路板过孔中心坐标的数据，请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。（2）为提高打孔机效能，现在设计一种双钻头的打孔机（钻头形状与单钻头相同），两钻头可以同时作业，也可一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm的合作间距。（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。
f二、问题分析
21问题1分析：本问题可看作为动态规划与图论的组合问题，即求取由起始状态到终点状态的最优单向
路径问题，主要是运用运筹学的排序理论、图论中的Hamilto
路径的相关理论知识解决问
题。经分析，T1钻头的行进时间、T2加工不同孔型的刀具的转换时间，是本题的目标r