提高打孔机生产效能

提高打孔机生产效能摘要提高生产效能是各个企业面临的一个很实际的问题，因为这关系到企业的生存和发展。过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，因此提高过孔的生产效能在一定程度上影响到作业成本和作业时间，提高钻孔加工效能已成为该行业中急需解决的重要问题。提高孔加工的效率，就务必要找到最优的打孔路径。因此，要结合实际问题，应用理论知识进行打孔路径的优化，以实现加工的高效率和低成本。当把所有的孔看做质点后，孔之间的连线看做边，则过孔加工就可以看作是典型的TSP问题。即遍历所有的孔后，路径最短。为了计算上的方便，该模型先利用枚举法求出刀具的所有转换方案，并确定出最佳刀具转换方案（转换次数最少即最佳），然后确定出10种孔型的先后加工次序，再对每个孔型建立模型，得到每个模型的最优路径，最后求得最短距离、行进时间和作业成本。求解TSP问题的方法有很多种，如遗传算法、模拟退火算法等，本文采用的求解方法是蚁群算法，因为对该模型的数据，蚁群算法能得到更优的结果。通过matlab实现蚁群算法，得出最终的最短距离Shortest-Length为1.6129e+006(mm)，行进时间T-move为8.9606e+003(s)，作业成本C为96795(元)。关键字：生产效能，TSP问题，蚁群算法，最短距离1一、问题重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。现有某种钻头，上面装有8种刀具a，b，c，…,h，依次排列呈圆环状，如图1所示。图1某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。钻头在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表110种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c一块线路板上的过孔全部加工完成后，再制作另一块线路板。但在同一块线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。请通过建立相应的数学模型，完成以下问题：B题附件提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔bcdefgha2（mil）（密尔也称为毫英寸，1inch=1000mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。二、问题分析本次建模的目的是提高打孔机的生产效能，影响打孔机生产效能的因素主要有三个：1、单个过孔的作业时间；2、打孔机加工作业时，钻头的行进时间；3、对不同孔型加工作业时，刀具的转换时间。因此，要提高打孔机的生产效能，可以通过减少单个过孔的作业时间、钻头的行进时间及刀具的转换时间。现已假定同一孔型钻孔作业时间都是相同的且钻头的行进速度也是相同的且匀速。所以要求打孔机的生产效能等价于求钻头遍历所用孔的最短路径且满足刀具的转换次数最少。可以先通过枚举法求出刀具的所有转换方案，从而确定出最佳的刀具转换方案，然后根据刀具的转换次序依次对相应的孔型进行打孔，在打孔的过程中确定最优的打孔路径。当把所有的孔都看做是质点后，确定最优的打孔路径就是典型的旅行商问题，即TSP问题。TSP问题常用模拟进化算法来解决，如蚁群算法、模拟退火算法、遗传算法等。行进时间等于作业最短路径距离除以钻头行进速度。作业成本可以根据行进时间和相应的时间成本求得。三、模型假设1.假设对于同一孔型钻孔作业时间都是相同的2.假设钻头的行进速度是相同的且钻头移动是匀速的3.忽略各个孔型的大小，将孔型视为质点4.将钻头视为质点四、符号说明Shortest-Length：最短路径距离T-move：钻头行进时间T-trans：刀具转换时间t：相邻刀具转换时间V：钻头行进速度P-move：钻头行进1mm成本P-trans：刀具每分钟转换时间成本M：行进总距离C-move：行进成本C-trans：刀具转换成本C：作业成本五、模型建立5.1最优作业线路模型该问题可以直接将所有的数据直接利用蚁群算法，求得最短路径距离。但是这样算，需要运行很长的时间才能得出结果。因此，本文采用先确定刀具的最佳转换方案，通过转头的转换次序，对相应的孔型进行打孔。这样就可以大大缩短程序的运行时间。设集合V={v1,v2,v3,……,vn}表示所用孔的集合，d(vi,vj)表示集合中任意2个孔vi,vj的距离，则行进总距离vi,,M=(,)vjVvivjdvivj,因此该问题对应的模型为：目标函数：vi,,Shortest-Length=minM=(,)vjVvivjdvivj约束条件：1、加工路径从一个孔出发，遍历每一个孔，最后回到起点；32、刀具转换次数最少，即最佳刀具转化方案。5.2行进时间模型钻头的行进时间与钻头的行进距离和钻头的行进速度有关，因此行进时间模型为：T-move=Shortest-Length/V5.3作业成本模型作业成本由行进成本和刀具转换成本组成。行进成本可由钻头行进1mm的成本和转头的行进距离求得，而刀具转换成本可由刀具每分钟转换时间成本和刀具总的转换时间求得。因此作业成本模型为C=C-move+C-trans其中C-move=P-move*Shortest-LengthC-trans=T-trans*P-trans5.4蚁群算法简介蚁群算法是受真实的蚂蚁的群体合作行为而提出的一种随机搜索算法，与其他进化算法相似，通过对候选解成的群体进化来寻求最优解。算法由许多蚂蚁共同完成,每只蚂蚁在候选解的空间中独立搜索解,并在所寻得的解上留下一定的信息素.解的性能越好,蚂蚁留在其上的信息素就越多,信息素越多的解被选择的可能性也越大.在算法的最初阶段所有解上的信息素是相同的,随着算法的推进,较优解上的信息素将逐渐增多,算法渐渐趋于收敛.作为一种随机优化方法，蚁群算法不需要任何先验知识，最初只是随机地选择搜索路径，随着对空间的了解，搜索更加具有规律性，并逐渐得到全局最优解。5.4.1算法的常见符号：（1）qti：t时刻位于点i的蚂蚁个数；（2）m：蚁群中的全部蚂蚁个数，t1nmqii（3）ij：边,ij上的信息素强度；（4）ij：边,ij上的能见度；（5）dij：点i和点j之间的距离；（6）kPij：蚂蚁k由点i向点j转移的概率。5.4.2每只蚂蚁具有的特征（1）蚂蚁根据点之间的距离和连接边上信息素的数量为变量的概率函数选择下一个将要访问的点；（2）规定蚂蚁在完成一次循环以前，不允许转到已到过的点；（3）蚂蚁在完成一次循环时，在每一条访问的边,ij上释放信息素。5.4.3算法流程4（1）初始化蚁群：初始化蚁群参数，设置蚂蚁数量，初始化信息素，设0Cij(C为常数)；（2）蚂蚁移动：蚂蚁依据前面蚂蚁所留下的信息素和自己的判断选择路径，完成一次循环；（3）释放信息素：对蚂蚁所经过的路径按一定的比例释放信息素；（4）评价蚁群：根据目标函数对每只蚂蚁的适应度做出评价；（5）若满足终止条件，即最短路径，输出最优解。否则，算法继续进行；（6）信息素的挥发：信息素会随着时间延续不断消散。在算法中用到的规则（1）状态转移规则,0,ttijijjallowedkkttPtisisijsallowedkelseallowedk：蚂蚁k下一步允许选择的点；：信息启发式因子，表示轨迹的相对重要性；：期望启发式因子，表示能见度的相对重要性。（2）全局调整规则经过n个时刻，蚂蚁完成一次循环，各路径上信息素根据下式调整：1tntijijij1mkijijk,,k0,kijQkLij若第只蚂蚁在本次循环中经过路径否则kij：第k只蚂蚁在本次循环中留在路径,ij上的信息素量；：信息素轨迹的衰减系数，通常设置1。5.5TSP问题简介又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后5再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。旅行商问题就是求解巡回线路的耗费的最小值。数学模型描述如下：六、模型求解6.1刀具的最佳转换方案作业时，钻头的转换可以是顺时针旋转，也可以是逆时针旋转。根据这2钟方向，可以枚举出钻头的所有转换方案，具体方案见表6-1表6-1序号刀具转换方案转换次数顺时针1a-b-c-d-e-f-g-h-g-f-e-d-c122b-c-d-e-f-g-h-a-b-c-d-e-f123c-d-e-f-g-h-a-b-c-d-e-f114d-e-f-g-h-a-b-c-d-e-f105e-f-g-h-a-b-c-d-e-f-g-f116f-g-h-a-b-c-d-e-f-g-h-e-d-c137g-h-a-b-c-d-e-f-g-f-e-d-c128h-a-b-c-d-e-f-g-h-f-e-d-c12逆时针9a-h-g-f-e-d-c-b-a-h-g-f1110b-a-h-g-f-e-d-c-b-a-h-g-f1211c-b-a-h-g-f-e-d-c-b-a-h-g-f1312d-c-b-a-h-g-f-e-d-c-b-a-h-g-f1413e-d-c-b-a-h-g-f-e-d-c1014f-e-d-c-b-a-h-g-f-e-d-c1115g-f-e-d-c-b-a-h-g-f-e-d-c1216h-g-f-e-d-c-b-a-h-g-f-e-d-c13从上表可以发现，最佳的刀具转换方案，也就是转换次数最小的方案，有2个，分别是方案4:d-e-f-g-h-a-b-c-d-e-f和方案13:e-d-c-b-a-h-g-f-e-d-c。随便选择一种转换方案，得到的最短距离结果都是一样的。本文选择方案4的转换方案作为最佳刀具转换方案。根据方案4，可以求得每种刀具所能打的孔型的最佳路径。针对方案4，每次转化钻头所需打的孔型见表6-2：6:表