工件排序问题的有关解决论文

题目 工件加工优化方案摘要本文根据已知数据，结合相关问题要求，对多种工件加工问题进行了研究，建立线性规划模型得出了工件加工时间最短和优化加工顺序。模型通过对工件加工时间的分析以及各工件等待时间，得出工件加工总时间最短的解决方案。而后在满足总等待时间最小化的条件下，优先加工时间最短工件，使条件下的加工时间最短。最后验证方案的有效性和实用性。针对问题 1，通过引入 0/1 变量，建立相关变量函数式。根据题目的约束条件，运用 Lingo 软件得出总加工时间最短的加工顺序。针对问题 2，结合 1 题的相应结果，再次运用 Lingo 软件，计算得出各机床的等待时间和工件的起止时间表。针对问题 3，根据问题要求和所建立的数学模型，运用 C+软件进行模型求解。关键词：0/1 变量 Lingo 软件 C+软件1问题的重述某车间上午 8:00 开始加工十个零件，这些零件必须通过机床 M1，M2，M3加工，考虑如下的工件加工的排序问题和等待时间问题：（1）不考虑工件的完工时间和等待时间的长短，为该工厂安排工件加工的次序，怎样安排 10 个工件的顺序使得工件加工的总时间最短？（2）如何根据问题 1 的结果，求出各机床的等待时间？（3）在满足题中问题 3 的条件下，如何结合题中问题 1、2 的已知数据和模型结果得出问题 3 的解决方案？2.问题的分析已知零件在每个机床的加工时间以及加工顺序固定，容易得出工件会在机床 M2、M3 上会出现等待时间。若使总加工时间最短，则需要尽可能的缩短工件在机床 M2、M3 总的等待时间，进而得出工件加工总时间最短的最优工件加工顺序。然后通过计算得出工件加工的等待时间。3.模型的假设与符号说明3.1 模型的假设（1）每个工件在加工过程中是连续的，没有其他外部工件及工序的介入。（2）零件之间相互独立，加工过程中零件间没有相互影响。（3）每个工件在每台机床的加工时间固定，且不受偶然事件和操作水平的影响。（4）忽略转换工序时的运输时间。3.2 符号说明:i 工件在机床 M1 加工所需时间(1):i 工件在机床 M2 加工所需时间(2):i 工件在机床 M3 加工所需时间(3):i 工件完成在机床 M1 加工的总时间(1):i 工件完成在机床 M2 加工的总时间(2):i 工件完成在机床 M3 加工的总时间(3):（i-1）工件完成在机床 M2 加工的总时间（ i1）(2)1:（i-1）工件完成在机床 M3 加工的总时间（ i1）(3)1M：加工十个工件模型的总时间Ai0:工件在机床 M1 开始加工时间Ai1:工件在机床 M1 加工结束时间Bi0:工件在机床 M2 开始加工时间Bi1:工件在机床 M2 加工结束时间Ci0:工件在机床 M3 开始加工时间Ci1:工件在机床 M3 加工结束时间A- J 工件加工顺序，A-J 分别用 0-9 表示Z10：Z10为 0-9 一种排序，即 A-J 工件的加工顺序4.模型的建立与求解41 问题一的模型建立与求解411 问题一的模型建立由问题分析可知工件 i 在 M1 工序完成的时间为：= + （ 1）(1) (2)-1(2)由于各工件的总时间等于加工时间和各工件的等待时间之和，则对于工件i 在 M1 工序完成的时间 与（ i-1）工件完成在 M2 加工的总时间， 要(1) (1)-1分两种情况分析：（1）当 时，即 i 工件完成 M1 工序所需要的总时间大于或等(1) (2)-1于（i-1）工件完成 M2 工序的总时间，此时 i 工件不需要等待（i-1）工件而立即进入 M2 工序，因此 i 工件完成 M2 工序的总时间的表达式为：= + 。(1) (2) (2)（2）当 时，即 i 工件完成 M1 工序所需要的总时间小于或等(1) (2)-1于（i-1）工件完成 M2 工序的总时间，此时 i 工件需要等待（i-1）工件而立即进入 M2 工序，因此 i 工件完成 M2 工序的总时间的表达式为：= + 。(1) (2)-1(2)综合以上两种情况，得到 i 工件完成 M2 工序的总时间计算公式为：=Max（ ， ）+ （i1）(2) (1) (2)-1 (2)同理，对于 M3 工序，同样可以得到类似的公式，将此公式推广到 i 工件在M3 工序的应用公式为：=Max（ ， ）+(3) (2) (3)-1 (3)由上可知 i 工件从任务时刻开始起到完成 (j=1,2,3)道工序止所需要的()总时间 见下表 4.1.1-1：表 4.1.1-1工序顺序工件顺序 M1-（ 1） M2-（ 2） M3-（ 3）10+(1)1+(1)1(2)1+(2)1(3)12+(1)1(1)2Max（ ， ）+(1)2 (2)1 (2)2Max（ ， ）+(2)2 (3)1 (3)23+(1)2(1)3Max（ ， ）+(1)3 (2)2 (2)3Max（ ， ）+(2)3 (3)2 (3)3 i+(1)1(1)Max（ ， ）+(1) (2)1(2)Max（ ， ）+(2) (3)1 (3)根据表 4.1.1-1，问题一中要求的完成加工任务的最省总时间即为在最优排序下各工作完成 M1，M2，M3 的总时间之和。则建立问题一的数学模型为Max= + （1i10 ） ；其中 = + 。(3)110=2(2， 31)+(3) (3)1(2)1(3)1412 问题一的模型求解根据所建立的数学模型，运用 Lingo 软件进行编程参考附录一，模型运行结果见附录二得表 4.1.2-1,表 4.1.2-2，表 4.1.2-3：表 4.1.2-1 工件加工时间表工件号M1 加工时间（分钟）(1) M2 加工时间（分钟）(2) M3 加工时间（分钟）(3)D 8 10 6E 9 14 13J 13 7 9G 11 16 12H 16 9 18A 13 15 20I 15 12 7B 10 20 18F 19 20 14C 20 16 15表 4.1.2-2 工件加工等待时间表工序号等待时间零件号M1 M2 M3D 0 0 0E 0 1 0J 0 1 6G 0 0 0H 0 0 3A 0 0 3I 0 0 8B 0 2 0F 0 1 0C 0 0 0表 4.1.2-3 工件加工总时间表工件号完成 M1 工序总时间 （分钟）(1) 完成 M2 工序总时间 （分钟）(2) 完成 M3 工序总时间 （分钟）(3)D 8 18 24E 17 32 45J 30 39 54G 41 57 69H 57 66 87A 70 85 107I 85 97 114B 95 117 135F 114 137 151C 134 153 168总时间：437由上表可知最优排序为 D-E-J-G-H-A-I-B-F-C。完成这批工件加工任务所需的最省时间为 437 分钟。42 问题二的模型建立与求解421 问题二的模型建立已知加工工件的初始时间为上午 8:00。（1）各个工件的加工起始时间为上一个工件在机床 M1 的完工时间，其中第一个工件的加工起始时间为上午 8:00；各个工件的加工停止时间为各个工件在工序 M1、M2、M3 的加工时间与加上该工件在加工过程中的等待时间的和。（2）机床的等待时间为一个工件的加工时间 与下一个工件的加工时间()之差。()-1422 问题二的模型求解结合问题一的计算结果，运用 Lingo 软件对数据进行 0/1 规划，分别求出工件在加工过程中的等待时间以及机床等待时间。运用 excel 工作表，对数据进行整理归纳，得出工件在最优顺序下的加工起止时间表，见下表 4.2.2-1表 4.2.2-1 工件加工起止时间表工序号起止时间工件号M1 M2 M3D 8：00-8：08 8：08-8：18 8：18-8:24E 8：08-8：17 8：18-8：32 8：32-8：45J 8：17-8：30 8：33-8：40 8:51-9:00G 8：30-8：41 8：40-8：56 9:00-9:12H 8：41-8：57 8：56-9：05 9:15-9:33A 8：57-9：10 9：05-9：20 9:36-9:56I 9：10-9：25 9：20-9：32 10:04-10:11B 9：25-9：35 9：34-9:54 10:11-10:29F 9：35-9：54 9:55-10:15 10:29-10:43C 9：54-10：14 10:15-10:31 10:43-10:58通过对表 4.2-1 进行数据处理，将数据转化为 0/1 变量数学模型，然后解数学模型，得出工件加工过程中各机床的等待时间表，见下表 4.2.2-2：表 4.2.2-2 机床等待时间工序号机床等待时间工件号M1 M2 M3D 0 0 0E 0 0 8J 0 0 0G 0 2 3H 0 0 0A 0 4 0I 0 0 0B 0 0 3F 0 0 2C 0 0 243 问题三的模型建立与求解431 问题三的模型建立（1）由问题分析可知第 i 个加工工件在 M1 中；初始时间 A00=0;其余初始时间为上一个工件完成时间 Ai0+Ai-10；第一个工件完成时间：Ai1+Ai0+M1Zi；（2）由问题分析可知第 i 个加工工件在 M2 中；初始时间为第一个工件在 M1 的完成时间即：B00= A01;其余初始时间为 i-1 个工件在 M2 的完成时间 i 个工件在 M1 完成时间的最大值，即：Bi0=max（Bi-10, Ai1） ；第 i 个工件完成时间：Bi1+Bi0+M2Zi；（3）由问题分析可知第 i 个加工工件在 M3 中；初始时间为第一个工件在 M2 的完成时间即：C00= B01;其余初始时间为 i-1 个工件在 M3 的完成时间 i 个工件在 M2 完成时间的最大值，即：Ci0=max（Ci-10, Bi1） ；第 i 个工件完成时间：Ci1+Ci0+M3Zi；（4）由题中要求可知，机床 M3 加工每个零件等待时间不能超过 5 分钟，即为 sss5总等待时间不能超过 30 分钟,即为 w_t30(4)各个工件加工时间之和：M=(C01-A00)+( C11-A10)+( C91-A90)根据不同的加工顺序，即不同的 Z10序列，得出最小的 M，而 Z10中数据即为所求加工顺序。432 问题三的模型求解通过以上分析，运用 C+编程对模型进行求解，运行结果如下图 4.3.2-1所示：图 4.3.2-1由图 4.3.2-1 运行结果得出在问题三条件下工件的起止时间表： 表 4.3.2-2 工件加工起止时间表工序号起止时间顺序M1 M2 M3G 8:00-8:11 8:11-8:27 8:27-8:39I 8:11-8:26 8:27-8:39 8:39-8:46D 8:26-8:34 8:39-8:49 8:49-8:55H 8:34-8:50 8:50-8:59 8:59-9:17J 8:50-9:03 9:03-9:10 9:17-9:26E 9:03-9:12 9:12-9:26 9:26-9:39A 9:12-9:25 9:26-9:41 9:41-10:01F 9:25-9:44 9:44-10:04 10:04-10:18C 9:44-10:04 10:04-10:18 10:20-10:35B 10:04-10:14 10:18-10:40 10:40-10:58由工件起止时间表 4.3.2-2 得出机床等待时间表：表 4.3.2-3 机床等待时间工序号等待时间顺序M1 M2 M3G 0 0 0I 0 0 0D 0 0 3H 0 1 0J 0 4 0E 0 2 0A 0 0 2F 0 3 3C 0 0 2B 0 0 5通过表 4.3.2-2，表 4.3.2-3 数据分析，得出结论为，满足要求的总加工时间最短的加工顺序为：G-I-D-H-J-E-A-F-C-B,最短时间为 4255.模型的结果分析与检验51 问题一的模型结果分析通过对模型一结果的分析可知，要想使总的加工时间最少需要找到最优的加工顺序。易知工件总的纯加工时间一定，即为每个工件在每个工序的加工时间总和，因此，若使总的加工时间最少，则须使机床的的等待时间总和最少，即为机床 M2、M3 的等待时间之和最少。模型一就是根据以上所述运用 Lingo 进行编程运行，从而得到问题一的结果。52 问题二的模型结果分析根据问题二的要求，结合问题一所建立的模型和运行结果，对问题二进行定性以及定量分析，进而得到问题二的模型结果。由工件加工起止时间表可知，在工件加工过程中，在加工工序 M1 时工件等待时间不计算，即机床 M1 无等待时间，可理解为第 i-1 个工件在工序 M1 的加工完成时间即为第 i 个工件在工序M1 的加工开始时间。由机床的等待时间表可知，加工工序 M1、M2、M3 之间大多数情况下无等待时间，说明机床得到了充分的利用。53 问题三的模型结果分析问题三在问题一问题二的基础上增加了一些限定条件，重新建立数学模型,根据不同的加工顺序，即不同的 Z10序列，满足上述的限制条件得出最优的加工时间，而 Z10中数据即为所求的最优加工时间顺序，然后重新回答问题一和问题二。模型三是利用 C+软件对问题进行求最优序列。6.模型的推广与改进方向61 模型的推广本次我们用到是 0/1 规划和线性规划模型，通过对软件 Lingo 和 C+的编程获取所需数据，运用 excel 办公软件对数据进行统计和处理。Lingo 软件对非线性问的最优解有针对性。C+软件可以对优先问题进行相应的编程。此模型的推广也可以用来解决最短路问题、成本利润型问题等。由于在模型求解中利用了 Lingo 软件，大大简化了编程工作，且模型本身结合软件的使用就具有很强的可移植性，便于模型的推广。列如在推广到