东三省数模竞赛论文

《东三省数模竞赛论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、封一答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目：D打孔机生产效能的提高组别：本科生参赛队员信息(必填)：姓名学号联系电话参赛队员1林双海222009078718941195310参赛队员2熊飞222009228315941614198参赛队员3孙建颂222009092018940927758参赛学校：大连海事大学封二答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3.评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛

2、评阅3.打孔机生产效能的提高摘要本问题中，打孔机打完一个孔，不仅需要行进到下一个孔，还有可能需要转换刀具，使得打孔机打孔的成本受限制于行进成本和换刀具成本。若要求出最优解，可以通过枚举法，但由于数据量过大，显然枚举法行不通。经过分析，决定采用贪婪法来获得次优解，即以自顶向下的方式进行，以迭代的方式做出相应的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。我们选择贪婪算法的原因，是因为此问题满足贪婪算法能够获得最优解的两个条件：一、贪婪选择性质，所求问题的整体最优解可以通过一系列局部最优解的选择，即

3、贪心选择来达到，从一点开始，每一次寻找距离此点最近的点，将两点连线，再以第二个点为基准，按这种思想寻找下一个点，依次将所有连起来，因为每一次都是取最短距离，因而所有点的连线也是最短的。二、最优子结构性质，本题中每一点寻找与之距离最近的点都会受到上一个点的影响，因为只有确定了上一级的点，才可能确定下一个点。另外，由于八种刀具转换时候即可以顺时针旋转，也可以逆时针旋转，因此在刀具转换过程中，要选择正确的旋转方向，以减少加工成本。同时，由于刀具在行进过程中，可以同时进行刀具，但相应费用不减。因此，为了提高生产效率，我

4、们选择刀具一边行进，一边进行刀具转换，如果行进过程的时间小于刀具转换所需时间，则当打孔机达到目标点的时候继续进行刀具转换。问题二:本问题中，打孔机在作业的时候，既要保证行进时间最短和作业成本最少，又要保证在过孔加工的任何时刻保持两钻头不小于3cm。寻找一条最短路径相对容易些，但是要想时刻保证两钻头的距离不小于3cm则相对困难。为了保证打孔路线最优，经过研究，我们决定同样采用贪婪法解决双钻头打孔问题。同时，我们采用动态监测的方法，每隔一段时间（即钻头每行进1mm所对应的时间）检测每一个钻头在寻找下一个目标点的过程

5、中与另外一个钻头的距离，以近似地满足两钻头合作间距。另外，为了避免两钻头相撞，我们假设两钻头同时寻找下一个目标点，即如果一个钻头先完成当前的作业，也必须等待另一个钻头完成作业后，才能够共同寻找各自的下一个目标点。当我们计算出两钻头作业时的最优作业线路、行进时间和作业成本，通过简单的数学计算，即可以得出双钻头和单钻头作业的生产效能的差异。在求解双钻头作业时，由于需要时刻考虑作业间距，所以经过一定的分析，便可得出合作间距对作业路线和生产效能的影响。关键字：贪婪算法生产效能优化路径一、问题的提出过孔是印刷线路板（也称

6、为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1inch=

7、1000mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产

8、效能提高多少？研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、基本假设1、假定对于同一孔型钻孔作业时间都相同。2、假定钻头的行进速度是相同，始终为匀速运动。3、假设在刀具转换时始终采取最小的成本，即能通过正确选择旋转方向，使得旋转次数最少。4、假设行进的时间仅仅只是特指钻头移动时的时间，与刀具转换的时间严格区分开。5、假设双钻头作业中，两钻头可以同时作业，且作业是独立的，