产品的零件安装程序设计.doc

No.1 韶关学院学生数学建模论文集 第一期（2002年10月） 第一期（2002年10月） 韶关学院学生数学建模论文集 No.1  PAGE 72  PAGE 73 产品的零件安装程序设计 柯文锋，赖金花，欧杰泉 （1）2000级数学系与应用数学本科1班 （2）2000级计算机系科学与技术本科1班 （3）2000级数学系与计算机教育6班 摘要:本文以零件的安装次序为着眼点，通过一些合理的假设，对具体的每一个问题，运用运筹学、图论及数据结构等的知识得到相应的数学规划模型，运用数学软件（Matlab、Maple等）进行求解，得出零件安装完需要的最少时间及相应的安装次序． 关键词： 整数规划；时间落差；回溯；递归调用 1 问题的提出 韶关市西郊某机械厂的零件安装部门要对零件生产部门生产出来的15个零件进行组装，最终成为一个产品，并推出市场．这15个零件分别用表示，一个熟练工人安装需要时间为 （单位：分钟）． 此产品的15个零件正等待工人来安装． 由于生产的工序要求工人在安装零件时，安装某些零件必须在另一些零件安装完成后才能进行安装，各零件需先前安装的零件如下表： 先前安装的零件—— 先前安装的零件—（1）（此产品的零件由两个工人来安装时，完成任务的最少时间是多少？并为此两工人设计出安装方案．如果工人足够多，那么完成产品的零件安装任务的最少时间又是如何？ 由于大部分产品都要求在零件安装时，不能有两个以上的工人同时一起组装该产品，只能由一个工人单独完成，在这种情况下，我们对以下问题进行讨论： （2）请为产品的组装过程设计一个满足要求的安装次序，使各零件安装完的时间（包括等待安装时间）之和最少． （3）假若第个零件紧接着第个零件完工后开工，且生产产品需要花费的准备时间满足： 试设计一个满足条件的加工顺序，使机床花费的总时间最少． （4）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限，则需支付一定的补偿费用，其数值等于超时间与费率的乘积（各工件的补偿费率见下表）． 1234567891011121314151210151610111085410108129试在及各的情况下安排一个加工顺序，使花费的总补偿费用最小． 2 符号约定 零件号为的零件． 零件个数． 　　零件中的安装次序中为的零件号． 　　零件、的安装次序的一个布尔变量，为１时表示在做零件之前，必须先做零件． 　　　零件的安装时间． 　　　第个零件紧接着第个零件完工后开工，所需要的准备时间． 　　　第个零件的安装时间（包括等待安装时间）． 　　　第个零件的补偿费用． ３　模型的建立与求解 3.1　假设用圆圈表示要加工的零件，用箭头表示加工的次序要求，即指向的圆圈内的零件必须在箭尾圆圈内的零件所需的加工时间．这样我们就可以构造出（如图一）的一个顶点带权的有向无环图．这张图十分明显地表示了工艺加工次序约束． 由于原图有两个入口，一个出口及一个独立点，为了方便我们考虑及研究问题，增设了两个权值为0的顶点．这样并不会影响或改变原图，则在工人足够多时，完成产品的零件安装任务的最少时间的问题就转化为求（如图二）从源点汇点的最长路（也叫关键路径）问题． 当工人只有两个，从图中观察，我们知道如果由一个工人负责最长路径中的各零件那么剩下的四个零件就由第二个工人负责． 由最长路算法，得到有向图D中和的最长有向路为： 我们也可以用拓扑排序及逆拓扑排序算法用C语言编程求出结果． 且． 两个工人安装的最少时间是123分钟，安装方案为： 第一个工人安装： 第二个工人安装： 两个工人的工作时间分别为：123分钟和48分钟． 当第一个工人安装完时，第二个工人也同时安装完了，这样第二个工人就可以紧接着后连续对零件的安装，他们开始作业的时间是第二个工人在第一个工人开始作业分钟后进行连续的作业． 安装方案是多样，但是上一方案的优点是两个工人在固定时间落差的情况下开始连续的作业，故两个工人都无须在作业的过程中等待．当安装零件的工人足够时，安装的总时间是等于其中一个工人安装最长路径中的所有零件的时间（因为它是所有工人中唯一一个从零件安装开始到结束没有停息的工人的安装零件时间），即为123分钟． 3.2　对于第二个问：若这n个零件由一个工人来安装，但是各零件的安装次序必须在满足题目表格中所给出的数据，求出令各零件安装完的时间（包括等待安装时间）之和最少的安装次序． 假设零件的安装先后次序为 则零件的安装次序流程为． 假设在做零件之前，必须先做零件的这一个先后