《东三省数模竞赛论文综述》由会员分享，可在线阅读，更多相关《东三省数模竞赛论文综述（34页珍藏版）》请在金锄头文库上搜索。
1、封一答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目： D打孔机生产效能的提高 组 别： 本科生 参赛队员信息(必填)： 姓 名学 号联系电话参赛队员1林双海222009078718941195310参赛队员2熊飞222009228315941614198参赛队员3孙建颂222009092018940927758 参赛学校： 大连海事大学 封二答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3. 评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛评阅3.打孔机生产效能的提高摘 要本问题中，打孔机打完一个孔
2、，不仅需要行进到下一个孔，还有可能需要转换刀具，使得打孔机打孔的成本受限制于行进成本和换刀具成本。若要求出最优解，可以通过枚举法，但由于数据量过大，显然枚举法行不通。经过分析，决定采用贪婪法来获得次优解，即以自顶向下的方式进行，以迭代的方式做出相应的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。我们选择贪婪算法的原因，是因为此问题满足贪婪算法能够获得最优解的两个条件：一、贪婪选择性质，所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到，从一点开始，每一次寻找距离此点最近的点，将两点连线，再以第二个点为基准，按这种思想寻找下一个点，依次将所有连起来，因为每一次都
3、是取最短距离，因而所有点的连线也是最短的。二、最优子结构性质，本题中每一点寻找与之距离最近的点都会受到上一个点的影响，因为只有确定了上一级的点，才可能确定下一个点。另外，由于八种刀具转换时候即可以顺时针旋转，也可以逆时针旋转，因此在刀具转换过程中，要选择正确的旋转方向，以减少加工成本。同时，由于刀具在行进过程中，可以同时进行刀具，但相应费用不减。因此，为了提高生产效率，我们选择刀具一边行进，一边进行刀具转换，如果行进过程的时间小于刀具转换所需时间，则当打孔机达到目标点的时候继续进行刀具转换。问题二:本问题中，打孔机在作业的时候，既要保证行进时间最短和作业成本最少，又要保证在过孔加工的任何时刻保
4、持两钻头不小于3cm。寻找一条最短路径相对容易些，但是要想时刻保证两钻头的距离不小于3cm则相对困难。为了保证打孔路线最优，经过研究，我们决定同样采用贪婪法解决双钻头打孔问题。同时，我们采用动态监测的方法，每隔一段时间（即钻头每行进1mm所对应的时间）检测每一个钻头在寻找下一个目标点的过程中与另外一个钻头的距离，以近似地满足两钻头合作间距。另外，为了避免两钻头相撞，我们假设两钻头同时寻找下一个目标点，即如果一个钻头先完成当前的作业，也必须等待另一个钻头完成作业后，才能够共同寻找各自的下一个目标点。当我们计算出两钻头作业时的最优作业线路、行进时间和作业成本，通过简单的数学计算，即可以得出双钻头和
5、单钻头作业的生产效能的差异。在求解双钻头作业时，由于需要时刻考虑作业间距，所以经过一定的分析，便可得出合作间距对作业路线和生产效能的影响。关键字：贪婪算法 生产效能 优化路径一、问题的提出过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是
6、单钻头作业，即一个钻头进行打孔。附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和
7、作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、 基本假设1、假定对于同一孔型钻孔作业时间都相同。2、假定钻头的行进速度是相同，始终为匀速运动。3、假设在刀具转换时始终采取最小的成本，即能通过正确选择旋转方向，使得旋转次数最少。4、假设行进的时间仅仅只是特指钻头移动时的时间，与刀具转换的时间严格区分开。5、假设双钻头作业中，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。6、假设双钻头作业中，钻头可以看作质点。7、假设两钻头同时寻找各自的下一个目标点，即如果一
8、个钻头先完成当前的作业，也必须等待另一个钻头完成作业后，才能够共同寻找各自的下一个目标点。三、符号的说明1、i、j:孔经过处理后的编号，i、j=1，2，32814；2、JULI(i，j)：编号为i的孔到编号为j的孔的距离。3、DAOJU(i、j)：编号为i的孔所用刀具转换到编号为j的孔所用刀具的转换次数。4、QUAN(i，j)：编号为i的孔与编号为j的孔之间的权。四、模型的建立与求解4.1模型分析4.1.1问题一：本问题中，打孔机打完一个孔，不仅需要行进到下一个孔，还有可能需要转换刀具，使得打孔机打孔的成本受限制于行进成本和换刀具成本。若要求出最优解，可以通过枚举法，但由于数据量过大，显然枚举
9、法行不通。经过分析，决定采用贪婪法来获得次优解，即以自顶向下的方式进行，以迭代的方式做出相应的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。我们选择贪婪算法的原因，是因为此问题满足贪婪算法能够获得最优解的两个条件：一、贪婪选择性质，所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到，从一点开始，每一次寻找距离此点最近的点，将两点连线，再以第二个点为基准，按这种思想寻找下一个点，依次将所有连起来，因为每一次都是取最短距离，因而所有点的连线也是最短的。二、最优子结构性质，本题中每一点寻找与之距离最近的点都会受到上一个点的影响，因为只有确定了上一级的点，才可能确定下
10、一个点。另外，由于八种刀具转换时候即可以顺时针旋转，也可以逆时针旋转，因此在刀具转换过程中，要选择正确的旋转方向，以减少加工成本。同时，由于刀具在行进过程中，可以同时进行刀具，但相应费用不减。因此，为了提高生产效率，我们选择刀具一边行进，一边进行刀具转换，如果行进过程的时间小于刀具转换所需时间，则当打孔机达到目标点的时候继续进行刀具转换。4.1.2问题二:本问题中，打孔机在作业的时候，既要保证行进时间最短和作业成本最少，又要保证在过孔加工的任何时刻保持两钻头不小于3cm。寻找一条最短路径相对容易些，但是要想时刻保证两钻头的距离不小于3cm则相对困难。为了保证打孔路线最优，经过研究，我们决定同样
11、采用贪婪法解决双钻头打孔问题。同时，我们采用动态监测的方法，每隔一段时间（即钻头每行进1mm所对应的时间）检测每一个钻头在寻找下一个目标点的过程中与另外一个钻头的距离，以近似地满足两钻头合作间距。另外，为了避免两钻头相撞，我们假设两钻头同时寻找下一个目标点，即如果一个钻头先完成当前的作业，也必须等待另一个钻头完成作业后，才能够共同寻找各自的下一个目标点。当我们计算出两钻头作业时的最优作业线路、行进时间和作业成本，通过简单的数学计算，即可以得出双钻头和单钻头作业的生产效能的差异。在求解双钻头作业时，由于需要时刻考虑作业间距，所以经过一定的分析，便可得出合作间距对作业路线和生产效能的影响。4.2.
12、模型的建立4.2.1对于问题一：首先，我们引进最短路问题中的“权”的概念，而这个权由以下两个部分构成，其一是钻头的行进成本，其二是刀具的转换成本。则任意两点间的权为：QUAN(i,j)=2.1*DAO(i,j)+60*JULI(i,j)其次，对孔进行处理。对于需要N（N1）把刀具以上才能加工完成的孔看成坐标重合但使用道具不同的N个单刀具加工点，这N个点之间的权则仅仅只是由道具转换的费用构成。通过这样的处理，可以将原来给定的孔拆分为2814个单刀具孔，具体的处理可见附件1：数据。最后，过程控制。任意选中其中的一个点进行打孔（本模型中，下文涉及到的孔均是指经过处理的单刀具孔），通过比较剩余未完成孔
13、到源点孔的权的大小，选择其中权最小的孔作为下一个要完成的孔。完成第二个孔后，以此点为源点，重复上述操作。对于需要一把刀具以上共同加工才能完成的孔型，在计算最小权的过程中，需要考虑刀具加工顺序问题。如果为D、F型孔，则对刀具加工次序没有要求，在求最小权的过程中，程序上不需要加任何限制，只需将孔进行处理。如果为C、E、G、I、J型孔，则对刀具的加工顺序有要求，可以用程序进行判断，例如某C型孔需要两把刀具完成（先使用a刀具，后使用c刀具），如果从上一孔到使用刀具a打该孔的权为W，从上一孔到使用刀具c打该孔的权为Q，从上一孔到除了该孔之外的孔最小权的为Z。如果WQZ，则使用刀具a进行打该孔；如果QWZ
14、,则还是使用刀具a进行打该孔，打完之后再以该孔为参照点，寻找下一个距离该孔权最小的点；如果QZW,则先打权为Z的孔，打完该孔之后，同样以该孔为参照点，寻找下一个距离该孔的权最小的点。由于我们每打一个点都是选择相对于该孔权最小的孔进行打孔，所以能够确保我们所打的所有孔，最终所需的成本最低，满足打孔机的经济性要求。4.2.2对于问题二：如下图：首先，我们随机选取两个相距3cm以上的点进行打孔，待两个孔都完成相应作业后，每一个钻头分别按照单钻头寻迹的方法(即贪婪法寻迹)寻找下一个目标点 然后，为了保证两钻头的合作间距，我们每隔一定时间对两钻头的距离进行动态检测来代替连续检测，程序实现见附录3。这种替
15、代是可行的，现证明如下：两钻头之间的距离主要有以下几种：始终不变，逐渐减小，逐渐增大，先减小后增大再减小。对于第一种情况，我们只需检测一次两点间距离即可。对于第二种情况，我们只需检测末端两点之间的距离即可。对于第三种情况，我们检测起始端两点之间的距离即可。对于第四种情况，主要有以下两种可能：图一：其中AB=BC,AD=BD,BE=CE,DF=HE=1mm图二：其中CD=1cm在图一中，容易证得DE为两钻头之间最短的距离，因为DF和HE均为1mm，所以在程序中，我们只要检测FH大于31mm,则DH必然大于30mm,又因为DE大于DH,所以DE大于30mm,故可以保证钻头行进过程中，两钻头之间的距离始终大于3cm。在图二中，在程序中，AD为两钻头之间最小距离，因此我们只需检测AC大于31mm,则可以根据三角形两边之差小于第三边的定理，得出AD大于30mm。从而保证钻头行进过
