(零件加工排序问题.docVIP

商丘师范学院2011-2012学年度第二学期期终考试 数学与信息科学学院 数学与应用数学、信息与计算科学专业 10级-1班、数本10-2班、信计10-1班）《》由于零件必须在它们要求的时间内完工，选择加工零件的种类及加工的次序,这些零件必须依次通过机床M1，M2，M3,其加工时间如下表(单位：分钟)。 M1 M2 M3 A 10 15 10 B 10 10 18 C 22 16 15 D 8 10 6 E 9 10 10 F 15 21 14 G 11 16 12 H 16 9 10 I 13 10 7 J 10 7 9 1. 试建立模型求出使总加工时间最短的加工顺序。 2. 写出个零件加工起止时间表，求出个机床的等待时间。 3. 若零件加工还要满足下面条件，零件D必须在零件E之前加工；零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟，总等待时间不能超过30分钟。试建立模型，重新回答前面两个问题。 二、问题分析 零件在M1工序上的总加工时间是固定的。关键是在M2及M3工序上会出现等待。如果采用不同序加工,那么在M1上已加工好的零件,在M2上加工的时间会落到在M1上比其后加工的零件的后面,则其在M2上等待的时间更长,同样在M2与M3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，选择加工零件的种类及加工的次序(i-1)零件完成在M3加工的总时间(i1) M:加工十个零件模型的总时间 五、模型的建立 由问题分析可知零件i在M1工序完成的时间： MI(1)= MI-1(1) + MI(2) （1） 对于零件在M1工序完成的时间MI(1)与(i-1)零件完成在M2加工的总时间，MI-1(2)要分两种情况分析： 1）当时MI(1)MI-1(2)即i零件完成M1工序的总时间大于或等于(i-1)零件完成M2工序的总时间，此时零件不需要等待(i-1)零件而立即就进入钻工序，因此零件完成M2工序的总时间表达式为; MI(2)= MI(1)+ MI(2) 2) 当时MI(1) MI-1(2)，即零件完成M1工序的总时间小于或等于(i-1)零件完成M2工序的总时间，此时零件需要等待(i-1)零件完成M2工序才能进入M2加工。因此零件完成M2工序的总时间表达式为MI(1)= MI-1(1) + XI(2)。 综合以上两种情况，得到零件完成M2工序的总时间计算公式为: MI(1)=max(MI(1), MI-1(1)) + XI(2) （2） 同理：对于零件在M2工序完成的时间MI(1)与(i-1)零件完成在M3加工的总时间MI(3)，有i零件完成M3工序的总时间计算公式为: MI(3)=max(MI(1), MI-1(3)) + XI(3) （3） 综合（1）（2）（3）可得加工十件零件需要的总时间为： M= MI(3)+ 约束条件： s.t. =1,(i=1,2,3,…,10) =1,(j=1,2,3,…,10) 六、模型求解 通过用Lingo编程求解，我们得出以下结论： 顺序号 零件号 M1加工时间XI(1)（分钟） M2加工时间分XI(2)钟） M3加工时间 Xi(3 （分钟） A D 8 10 6 B E 9 10 10 C J 10 7 9 D G 11 16 12 E H 16 9 10 F B 10 10 18 G I 13 10 7 H A 10 15 10 I F 15 21 14 J C 22 16 15 表1-1 顺序号 零件号 完成M1工序总时间MI(1)（分钟） 完成M2工序总时间MI(2（分钟） 完成M3工序总时间MI(3)（分钟） A D 8 18 24 B E 17 32 45 C J 30 39 54 D G 41 57 69 E H 57 66 87 F B 67 87 105 G I 82 99 112 H A 95 114 134 I F 114 134 148 J C 134 150 165 总时间：943 表1-2 由表6-1可知，我们可以排出各个零件加工的起止时间表，如下表所示： 起止时间表： M1 M2 M3 D 8:00-8:08 8:08-8:18 8：18-8:24 E 8：08-8:17 8:18-8:28 8:28-8:38 J 8:17-8:27 8:28-8:35 8:38-8:47 G 8:27-8:38 8:38-8:54 8:54-9;06