外文翻译--并联机床的操作安排.doc

附录1并联机床的操作安排我们引进独特的排序问题，来改进多主轴机床。这些机器同时对一个以上的部分执行操作的能力造成了约束，这在传统预定的文学中是找不到的。为这个问题引进了两种类型的解决程序。第一利用优先分配规则和延迟因素概念，而第二是利用随机码编写的遗传运算法则。这些方法的有效性是在测试问题时与下界对比中被证明的。1介绍并联机床在计算机辅助工艺设计(CAPP)设备系统中，驱动加工硬件有了改进。在硬件改善方面为了获得最大的利益，CAPP软件能够最大限度地发挥这些改进加以开发。并联机床和传统数控机床的最关键的区别是，前者包含了多个主轴以及它可以同时加工多个工件。结果，PMT的一次加工可以加工多于一个工件或者一次可以执行多于一个操作。这违背了最基本的假设或传统工艺规划调度。2排序问题的定义排序问题牵涉到对既定的工作，其工件加工时间最小化的操作顺序。一个工作有一个或多个工件组成，每个工件在其上都有很多执行操作。已经给出了每个操作所需的时间、每个操作模式（如下所述）和各个操作之间的优先关系。我们的目的是决定一个操作顺序，这个操作顺序将把处理这一系列操作所需的总时间最少化。一个并行车床上使得操作顺序复杂化的四个问题描述有：（i）操作之间的优先约束关系；（ii）约束形式；（iii）对零件加工位置的操作选择和（iv）对加工单元的刀具选择。现在，这些描述已经更详细了！优先约束的提出有三个原因。首先，涉及到几何考量。因为加工操作改变材料的体积，有些操作必须先于其它操作。第二个原因是公差。公差可能是一个工件与另一个工件尺寸配合特点所需要的。第三种优先形式由需要保证精度的制造实践产生的。在并行车床上所进行的操作根据工件在零件加工位置的运动和加工单元的运动可以分为三种模式，加工单元执行加工工件的操作。在LevinandDutta中，这三种模型被定义为：转削工件旋转而加工单元固定；磨削工件固定而加工单元运动，比如钻削或者铣削；轮廓铣工件和刀具都运动，比如轮廓铣。现在，由于技术的局限，不同模式的操作不能在同一零件加工位置进行。约束模式的增加添加了复杂性。由于一个并行车床有多样的零件加工位置，所以我们必须决定要在每个零件加工位置完成的一系列操作。这些决定将对完成加工零件所需的时间起很大作用。例如，为了使得物流顺畅，一个工件代表性地访问没个零件加工位置一次。我们假设零件不能反向访问一个给定的零件加工位置。因此，一个零件加工位置所安排的操作不能先于工件已访问过的其它零件加工位置所安排的操作。加工单元所使用的刀具也对加工周期起作用。只有在不同的加工单元使用不用的刀具才可能并行进行。这个问题复杂的是，不是每个加工单元都可以达到每个零件加工位置。刀具是一个困难的问题，将在未来的研究中被解决掉。在一个指令中可能存在不同零件之间的相互作用。假设一个零件访问两个零件加工位置。假如在指令中只有一个零件，那么，目的就是要使得零件尽可能快的通过这两个零件加工位置。但是，假如有很多工件在一次命令中，当一个工件转到第二个零件加工位置时，新的工件就会被放置在第一个加工位置。现在的目标是尽可能快的完成两个零件的操作在平衡方式下。谨慎执行这些先后顺序，使得并联机床可以在一次进程中同时执行一些操作，从而缩短了总的时间。因此，这个先后顺序问题的目标是最小化加工次序的总的时间，考虑了一系列相关问题：工具分配，操作任务以及操作的先后顺序。理想的说，所有的三个问题都必需同时解决。我们首先要解决的是，由已知刀具和运行任务产生的排序问题。在今后的工作中,我们将建立模块来处理分配问题.关于这个问题的数据见表1。最佳操作顺序有一个45的制造时间的跨度见图1。我们提供一个关于并联机床上出现的排序问题的详细描述。参数设置n=流程图上运行任务的数量，1，2，；i=任务标号，1，2，n；mi=运作模式i，1，2，3；pi；j=第i个运行任务的第j个当前步骤，1，2，n；Pi=第i个运行任务的所有当前步骤的设置，1，2，n；ti=第i个任务的运行时间，；MUmax=MU（机组）在一个问题中的数目，1，2，；PMLmax=PML在一个工序中的数目，1，2，；M=大正数；MUi=第i个操作的MU，1，2，MUmax；PMLi=第i个操作的PML，1，2，PMLmax；决定问题的变量Ci=第i个操作完成的时间，；Cmax=完成全部n个操作的最大时间，；附加符号ij表示在第j个操作开始时，必须完成第i个操作；ij在最后的时间表上，第i个操作完成在第j个操作之前；xij=如果ij的话，那么一个指示变量就是1。我们进行六个假设；（i）机组连续不断；（ii）没有操作优先权；（iii）事先知道操作时间；（iv）操作已分配给PML；（v）刀具已分配给MU，没有副加工；（vi）我们的目标是最小化制造时间跨度（即尽可能快完成这项工作）。假设MUs是持续用来做为消除MU崩溃的需要。在第3部分给出的解决方案，可以用来改进解决这些崩溃问题。然而，数据设置测试没有包括MU的崩溃信息。不允许优先响应金属切割作业的技术约束。假设已知每步操作的加工时间，这个时间必须扣除掉共用加工参数而同时进行的预定操作的重叠部分。假定刀具已经分配给刀架，并且没有副刀具，也就意味着每步操作都必须由一个特定的MU来完成。在今后的工作中我们将忽略掉假设(iii),(iv)和(v)。假设(iv)和(v)定义了分等级设计问题的部分。今后的工作将利用在本文中提到的算法，为全部问题建立一个决策支持系统。对PMT排定问题来说，制造时间跨度（假设（vi）目标是合理的，就像完全发生在单个机床中一样。我们假设当决定解除定单时，应在更高的决策层次上考虑库存和交货期。在PMT上定义加工计划的目标是，尽快完成定单上的工件生产。制造时间跨度是这个目标的合理措施。如果没有模式冲突，我们将得到由P1表示的一个简单问题，这是加工车间排序的普遍问题，也就是我们所说的NP-hard6。它与资源约束项目排序问题(RCPSP)有相同的结构。P1中的每个步骤与RCPSP中的行为相适应，要求一个包含所有可用性的资源回收单元。在P1中的MU符合在RCPSP问题中的资源。优先约束对两个问题来说是一致的。在过去的30年中RCPSP已被广泛的研究过7-10。我们将建立这些方法中的一部分，来发展处理更复杂多变问题的算法。虽然P1相当于在先前文献中所研究过的问题，但它对在PMT中更复杂问题的多变性来说是不正确的。把模式制约引进到这个问题中来，产生了这么个说法，据我们所知，这个说法以前的Levin、Yip-Hoi、Dutta等人已经提及了。这个问题可以用以下的数学式来表示。数学公式P2约束（2）保证了每步操作不会在先前一步操作完成之前开始。分离性的约束（3）和（4），保证了每个MU在任何时候最多只执行一个任务。这些分离性的约束和在加工车间所陈述的排定问题是类似的。分离性的约束（6）和（7），确保了一个操作可以同时预定一样的机器模式。这些约束把P1和P2区分开了。我们现在对P2建立了启发式的解决方法。3.启发式程序解决方法论我们限制为这个问题所建议的启发式方法解决方案有两个原因。首先，约束（6）和（7）的附加条件，相对于P1增加了P2中（0，1）变量的数目。我们测试的问题有成百上千个0-1变量和约束。大量的0-1变量使得直接数学公式解决方法失效。实验结果表明，包括25项任务的实例问题需要大约40小时的时间来解决CPLEX在SunSparc20中应用。包含50个任务的实例问题不可能在200个小时内解决。其次，为问题P2发展的启发式规则可以被扩展，在往后的工作中，包含由放宽假设(iii),(iv)和(v)而产生的附加复杂性。我们研究两种类型的启发式程序。第一运用改良的优先调度规则，解决了P2中的结构问题。第二是利用随机码编码的遗传算法。3.1启发式的优先规则优先分配规则已被运用到许多不同的排定问题上，包括P1。因为P2类似于P1，来自OlaguibelandGoerlich13的16个优先规则已作用于P1，在P2中被挑选来用做测试。检验规则包括最短的加工时间、最长的加工时间、最直接的后续事物、最不直接的后续事物、最大的总的后续事物、最少的总的后续事物、最长的跟随路线、最大的位置重力、最少的位置重力、最大的平衡位置重力、最早的完成时间、最早的开始时间、最迟的完成时间、最小的减落时间、每个后续事物的最小浮动。关于细节和定义看OlaguibelandGoerlich.对于一个给定的问题实例，每个优先规则都被用来建立一个时间表以及据说最好的16个进度表。16个优先规则在P2型问题中被检验，并且讨论它的结果在第5部分。一般来说，不能很好的执行分配规则，这点并不令人惊讶，因为他们不考虑概念模式。为了改善性能，这些规则被改良来解决P2中的结构问题。在P2中只有一个操作可以平行的预定一样的模式。这是用一种利用延迟类似记数来完成的，在Norman14中用于车间加工排定。在优先运算法则的清单上的关键因素是切实可行的，操作位置给出了三个不同的机床模式。举例来说，假设有一个零件在时间10至26一直在运转。另一个旋转操作要求一个刀具，刀具可利用的时间直到20才需要10个时间单位。这个操作的排定将会扩大旋转的时间。无论我们是否应该确定新任务的时间确定，是关于它的危险系数相对于其他没有预定的功能。延迟因素是这个危险系数的度量标准。五个延迟因素，如果延误了5个单位或更少的模式转变，也就意味着我们将要确定钻孔操作的时间。因此，更高的延迟因素，使得操作变得更加紧急。每个操作中设立的合理的延迟因素，是通过研究一系列可能产生的因素而来的。下列运算法则是描述如何改良规则1至16来合并延迟数目的概念。让j代表一系列的排定操作（没排定的操作关于没有排定原有事物），一系列的k操作是包含了不定期和未排定两个，在操作i中，pi代表优先规则的价值。步骤1.初始化。选择优先规则和估算pi的价值（每个优先规则只能做一次）。初始化J和K。步骤2.确定第一步操作的时间。重新考虑的实例数据问题已在表一中给出。如果最短加工时间规则是实用的，那么部分操作将在两个操作之后，此操作包含1和4。现在，在接下来的排定操作2中直接运用SPT结果，和在PML1的总时间要求将会是41。然而，若延迟时间足够的话，操作