东三省数模竞赛论文.doc

封一 答卷编号（参赛学校填写）： 答卷编号（竞赛组委会填写）： 论文题目： D打孔机生产效能的提高 组 别： 本科生 参赛队员信息(必填)： 姓 名 学 号 联系电话 参赛队员1 林双海 2220090787 参赛队员2 熊飞 2220092283 参赛队员3 孙建颂 2220090920 参赛学校： 大连海事大学 封二 答卷编号（参赛学校填写）： 答卷编号（竞赛组委会填写）： 评阅情况（学校评阅专家填写）： 学校评阅1. 学校评阅2. 学校评阅3. 评阅情况（联赛评阅专家填写）： 联赛评阅1. 联赛评阅2. 联赛评阅3. 打孔机生产效能的提高 摘 要 本问题中，打孔机打完一个孔，不仅需要行进到下一个孔，还有可能需要转换刀具，使得打孔机打孔的成本受限制于行进成本和换刀具成本。若要求出最优解，可以通过枚举法，但由于数据量过大，显然枚举法行不通。经过分析，决定采用贪婪法来获得次优解，即以自顶向下的方式进行，以迭代的方式做出相应的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。我们选择贪婪算法的原因，是因为此问题满足贪婪算法能够获得最优解的两个条件：一、贪婪选择性质，所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到，从一点开始，每一次寻找距离此点最近的点，将两点连线，再以第二个点为基准，按这种思想寻找下一个点，依次将所有连起来，因为每一次都是取最短距离，因而所有点的连线也是最短的。二、最优子结构性质，本题中每一点寻找与之距离最近的点都会受到上一个点的影响，因为只有确定了上一级的点，才可能确定下一个点。 另外，由于八种刀具转换时候即可以顺时针旋转，也可以逆时针旋转，因此在刀具转换过程中，要选择正确的旋转方向，以减少加工成本。同时，由于刀具在行进过程中，可以同时进行刀具，但相应费用不减。因此，为了提高生产效率，我们选择刀具一边行进，一边进行刀具转换，如果行进过程的时间小于刀具转换所需时间，则当打孔机达到目标点的时候继续进行刀具转换。 问题二: 本问题中，打孔机在作业的时候，既要保证行进时间最短和作业成本最少，又要保证在过孔加工的任何时刻保持两钻头不小于3cm。寻找一条最短路径相对容易些，但是要想时刻保证两钻头的距离不小于3cm则相对困难。为了保证打孔路线最优，经过研究，我们决定同样采用贪婪法解决双钻头打孔问题。同时，我们采用动态监测的方法，每隔一段时间（即钻头每行进1mm所对应的时间）检测每一个钻头在寻找下一个目标点的过程中与另外一个钻头的距离，以近似地满足两钻头合作间距。另外，为了避免两钻头相撞，我们假设两钻头同时寻找下一个目标点，即如果一个钻头先完成当前的作业，也必须等待另一个钻头完成作业后，才能够共同寻找各自的下一个目标点。 当我们计算出两钻头作业时的最优作业线路、行进时间和作业成本，通过简单的数学计算，即可以得出双钻头和单钻头作业的生产效能的差异。在求解双钻头作业时，由于需要时刻考虑作业间距，所以经过一定的分析，便可得出合作间距对作业路线和生产效能的影响。 关键字：贪婪算法 生产效能 优化路径 一、问题的提出 过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。 附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。 为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。 针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和