第二组加工顺序

1、加工顺序问题第二组摘要本文主要是分别对各个加工工件的完工时间之和最小 , 机床花费的总时间 最小, 超时补偿费最小的探讨加工工件怎样安排加工顺序的问题。第一问采用了 二种方法，第一种用C+编程；第二个方案是借用LINGO软件分别求出了加工 各个工件的最少时间； 第二问， 由题目所给的表格画出了加工工件的有向图， 列 出约束条件结合目标函数求出最优解。 第三问通过对 ti u,ti u,ti u 进行分析 ,可以得到当 ui u 时,其排列顺序与第一问中的排列顺序相同 ,而其他情况通过一定的算法可以分析得到 .第一问的最终结果为 :加工顺序为 410 9711 5386 1 2141213 时，

2、各工件 的完工时间和最小，为 2588。第二问的最终结果为 :加工顺序为 4711109538621141213时，机床花 费的总时间最小为 459。第三问的最终结果为 :加工顺序为 4711105938612141213时，总补偿 费最小，为 14242。关键词 ：加工工件 0-1 因子、问题的重述加工顺序冋题现在14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始，第j号工件的加工时间tj及先期必须完工的工件号i由F表给出:工件号j1234567891011121314tj2028251642123210242040243616前期 工件 号3,45,7,85

3、,910 ,113,8,943,5,744,76,7,145 ,121,2,6(1) 若给出一个加工顺序，则确定了每个工件的完工时间(包括等待与加工两个 阶段)，试设计一个满足条件的加工顺序，使各个加工工件的完工时间之和 最小。(2) 若第j号工件紧接着第i号工件完工后开工，机床需要花费的准备时间是tij，t. i j，i j ij 2(i j), i j试设计一个满足条件的加工顺序，使机床花费的总时间最小。(3) 假设工件的完工时间(包括等待与加工两个阶段)超过一确定时间u ,则需要支付一定的补偿费用，其数值等于超过的时间与费用率之积(各工件的补 偿率Wj见下表)：Xi表示第i号工件的加工序

4、号f1表示各个加工工件的完工时间之和二、符号说明符号意义机床花费的总时间f3加工时的总补偿费tij表示从节点i到节点j的准备时间0Xj '1表示第i个节点到第j个节点不需要准备时间,1表示第i个节点到第j个节点需要准备时间三模型的假设1. 每个工件都合格的完成加工，不会影响下一工件的加工。2. 没有多余时间的浪费。3. 每个工件都能按照规定时间完成。四、模型的建立与求解问题一： 方案一: 借助软件求解：c为这些工件所对应的加工时建立三个矩阵a, b, c矩阵a为要加工的工件号，矩阵b中每列为前期要加工 的工件号，0表示没有要求前期加工过工件。矩阵 间。14，a 12 3 4 5 67

5、8 9 10 1112 1335501034340465b479011805007712080 009070 0 0140t 20 2825 1642 12 3210 2420 40 2436 16.我们把a,b,t写进一个数组里w a,b,t。当b中的某一列全为0,该列（即工件号）就进行加工，其他的各列就进行等待，并且把 b中的该列号变为0； 当 b中有某些列全为0,则该各列号下的t中哪个元素最小，此列就进行加工，其 他列（除已经加工的工件）就进入等待状态。依此下去，当b中元素全为0,贝y循环结束。就说明所有的工件加工完毕。用任何编译器按上述算法编程可得程序见附录1：计算得总完工时间之和最小

6、的加工次序为：冋"D: Backup9 KTsuceBt Files 12402410一性是是是是是是是是是是是是IU疋> nlpclpalrnnllrDlrolrnLHmFU 1 4 2 3 41971538612111该工件的毀資时咼 该工伴的b卷吋由= -T山曲SSe曲丰工4的奪待吁匕 工心旳#乐 丁別的奪:寺乐- 该工件的書核甘工卜的#宙询: 工卜的色旬e加工时间龙丿6该工件S成所S的财间丄6lb36£092132174199209S21241.2A9285309加工引环ZH 加工吋间：24 加工叶可：加工时间加工申-同; 加工乐-迥； 加工册色 加工乐-冋

7、加工时亦 加T时间 加工时间 加工乐可 -J I I - J I J_ 4 I > .' J I,所有工件列工所需时间之和：345该工日*324e4225le12ze28.Ifi:24:36哇丄邃工该工璋丰tts感所S的O签工件完戍庭的叮间 该工fr完戍篠的時司泌塞应阪5鯉护.F牛完成®要的乐冋Tg威艇旳时迴Jb6092132174199SQ9221241269.2fl牙 369:345计算得总完工时间之和最小的加工次序为：4-10-9-7-2-14-12-13总时间为：2588 方案二：各个加工工件的完工时间之和包括各工件的等待时间之和与各工件的加工时间之和。因为各工

8、件的加工时间之和是一定的为345,所以此问可转化为求各工件等待时间之和最小时加工工件的次序.在算总时间fi时，第i个工件有14-Xi个工件等待，加上第i个工件本身的加 工时间，因此，加工各个工件的时间之和为f114(15 xi )tii1(14 x1)*20 (14 x2)*28 x7)* 32 (14 x8)*10 (14 x13)*36 (14 x14 ) * 16(14 x3)* 25 (14 x4)*16 (14 x5)*42 (14 x6)*12 x9)*24 (14 x10 ) * 20 (14 x11)* 40 (14 x12 ) * 24借助 lingo 软件求解 : 目标函数

9、：min(14(14 约束条件 : x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=91; x1-x3>1;x1-x4>1;x2-x5>1;x2-x7>1;x2-x8>1; x3-x5>1;x3-x9>1;x5-x10>1;x5-x11>1; x6-x3>1;x6-x8>1;x6-x9>1;x4-x7>1;x8-x3>1;x8-x5>1;x8-x9>1;x9-x4>1; x11-x4>1;x11-x7>1;x12-x6>1;x12

10、-x7>1;x12-x14>1; x14-x1>1;x14-x2>1;x14-x6>1;x13-x5>1;x13-x12>1; 在加上由题目可知的约束条件得出了结果是 计算得总完工时间之和最小的加工次序为 :4-10-9-7-2-14-12-13 加工工件的总完工时间为 :2588问题二:要计算机床花费的总时间最小， 就必须知道总时间包括哪几部分， 通过分析 知道，机床可以由三部分组成：机床的等待时间，机床的准备时间，机床的加工 时间。通过进一步的分析，可以由题意得知：机床的等待时间可以为 0，机床的 工作时间可以为各个工件都完成的时间。 所以，我们求

11、得最少的准备时间的路线 即为总时间最小的路线。通过对表中的数据可以得到一下的图形：由题中给出的表格画出了上图。图中的圆圈 Vi 为要加工的工件号，连线箭头表示了加工工件的次序，建立了目标函数f2, tj表示从节点i到节点j的准备时间， xij 0 (0 表示第 i 个节点到第 j 个节点不需要准备时间， 1 表示第 i1个节点到第 j 个节点需要准备时间。 通过对上图的分析， 可以得到以下的目标函 数f2，目标函数即表示建立一个14*14的矩阵，而其中每一行每一列都只有一 个元素需要等待时间为 tij xij ，并且求出这个等待时间的最小值。 而第一工件不需 要等待时间， 所以里边的等待时间个

12、数一共为十三个。 根据上面的分析， 可以得到以下的目标函数和约束条件。14min f2i114tijxij,(i, j0,1 14)j114xiji114xijj10,1.140,1.14xij0,114 14 xij i1j1i,j 0,1.14通过对解的分析， 我们找到了第一号加工的工件到第十四号工件的准备总时 间为： 85路径为：4 711 10953 862 1 14由于我们的程序得到的是第一号工件到第十四号工件的准备的总时间， 通过 进一步分析，得到的总准备时间为： 114最终的路径为：4711109538621141213问题三：补偿时间本来跟三个因素有关， 即：工件的等待时间和加

13、工时间、 机床的准 备时间。 但我们得知机床的准备时间是一个定值 ，且值为 0。所以补偿时间只跟 等待时间、加工时间有关，当 U 大于 100时，之后的加工顺序与第一问的完全相同。因为大于 100 时，我们考虑的因素可以归纳为：14（a b 100）Wj （其中 a i为等待时间，b为加工时间），其中Wj,b已然是个定值，只要a的和最小，整个的补偿时间就最小。而第一问我们已经得到了a （等待时间）最小的一个顺序。所以当大于 100后的顺序就相同了。当U <100时，算法:通过对第一问前面的六个数进行分析 ,至于为什么采用前边的六个顺序 元素进行分析 ,因前边的六个元素的加工时间进行从小到

14、大的顺序进行计算使之 刚好大于 100,然后在找到对应的工件号正好在前六个元素里边.所以我们只讨论第一问答案的前六个元素.前六个元素的顺序我们放在 d数组中.与之对应的加工 时间放在e中.其补偿率放在f中我们用e中的元素进行循环相加，并且当加上那 个数正好大于100时,对它进行减去100再乘f的操作得到一个数 G操作完成之 后，并在一个数组中保存与之相对应d的顺序.依次循环.就可以得到G大小的许多 值,通过比较这个值 ,那个最小的值就是补偿时间 .与之对应的顺序就是补偿时间 最小的顺序 .通过可以得到 :4109 7 11 5;162024 32 40 42;165 10 10 10.总的顺序

15、为 :4711105938612141213五、模型改进该问题并没有考虑机器的故障时间和休息时间。并且在工厂里也并不是台机器单独工作，而是特别灵活地调用其他的机器协调工作。所以，在实际中，不仅要综合考虑，而且更加注意机器之间的协调工作。六、模型的优缺点及其评价优点：在第一问中，我们找到了一种解决问题的算法，通过计算机的快速循环遍历就可以得到对于任意多个工件的最精确的答案。在第二问、第三问中， 我们巧妙采用了 xij 0 这样的因子构建目标函数， 在1找到目标函数的所有约束条件，使得本问题迎刃而解。缺点：第一问中，算法用计算机语言表达比较难，更加使用于专业程序员解决。第二、三问中，约束条件比较难

16、找，并且约束条件用 lingo 描述比较长。 评价：本问题，通过两种巧妙方法的结合。得到了最准确的答案。并且此模型也适用于车辆调度问题、垃圾处理问题。七、参考文献1 刘育兴，钟剑，垃圾运输问题的模型及其求解 , 赣南师范学院学报2005 年。2 谢金星，薛毅 ,优化建模与 LINGO 软件，北京：清华大学出版社，附录 1：#include <>int uniform(struct graph w);void IntiGraph(struct graph w);void dowithliennum(struct graph w,int num); struct graphint a;

17、int b3;int t; ; struct TIME int waiting;int working;int total;int main()间：间：int order14; struct graph w14; struct TIME time14;int flag =0; int num = 0;int t=0; int i = 0; int j = 0; IntiGraph(w);for (;i<14;i+)num = uniform(w); dowithliennum(w,num); timenum.waiting = t; timenum.working = wnum.t; t

18、 = t+wnum.t;timenum.total = t; orderi = num+1;printf(" 加工过程为： n");i = 0; for (;i<14;i+) printf(" 工 件 号 是 ： %d 该 %d",orderi,timeorderi-1.waiting);printf(" 加 工 时 间 ： %d 该 工 %dn",timeorderi-1.working,timeorderi-1.total); printf("* getchar(); getchar(); return 1;所有工

19、件加工所需时间之和：工件的等待时件完成所要的时%dn",t);/*int uniform(struct graph w)int tempnum10;int num = 50;j!=0)break;if (j=3&&wi.a!=0)tempnum0+; tempnumposition = i; position+;i = 0;for (;i<tempnum0;i+)if (num>wtempnumi+1.t)num = tempnumi+1;return num;*/int uniform(struct graph w)int tempnum10;int n

20、um1 = 0;int num = 50;j!=0)break;if (j=3&&wi.a!=0)tempnum0+; tempnumposition = i; position+;i = 0;for (;i<tempnum0;i+)if (num>wtempnumi+1.t)num = wtempnumi+1.t; num1 = tempnumi+1;return num1;void IntiGraph(struct graph w)int i=0;for (;i<14;i+)wi.a = i+1;w0.b0 = 3,w0.b1 = 4,w0.b2 = 0,

21、w0.t = 20; w1.b0 = 5,w1.b1 = 7,w1.b2 = 8,w1.t = 28; w2.b0 = 5,w2.b1 = 9,w2.b2 = 0,w2.t = 25; w3.b0 = 0,w3.b1 = 0,w3.b2 = 0,w3.t = 16; w4.b0 =10,w4.b1 = 11,w4.b2 = 0,w4.t = 42; w5.b0 = 3,w5.b1 = 8,w5.b2 = 9,w5.t = 12; w6.b0 = 4,w6.b1 = 0,w6.b2 = 0,w6.t = 32; w7.b0 = 3,w7.b1 = 5,w7.b2 = 7,w7.t = 10; w

22、8.b0 = 4,w8.b1 = 0,w8.b2 = 0,w8.t = 24; w9.b0 = 0,w9.b1 = 0,w9.b2 = 0,w9.t = 20; w10.b0 = 4,w10.b1 = 7,w10.b2 = 0,w10.t = 40; w11.b0 = 6,w11.b1 = 7,w11.b2 = 14,w11.t = 24; w12.b0 = 5,w12.b1 = 12,w12.b2 = 0,w12.t = 36; w13.b0 = 1,w13.b1 = 2,w13.b2 = 6,w13.t = 16;void dowithliennum(struct graph w,int

23、num)int temp = num+1;int i=0;int j=0;wnum.a = 0;for (;i<14;i+)j = 0;for (;j<3;j+)if (wi.bj=temp)wi.bj = 0;min=4*x31+11*x38+9*x18+3*x12+7*x16+15*x114+14*x81+12*x82+4*x86+2*x21+8*x26+16*x214+10*x61+8*x62+20*x614+11*x47+13*x49+14*x410+12*x9 3+8*x95+4*x97+19*x910+20*x911+12*x104+10*x105+6*x107+2*x109+21*x1011+ 18*x711+16*x79+17*x710+12*x115+4*x119+2*x1110+4*x53+14*x59;x18+x16+x12+x114=1; x86+x82+x81=1;x62+x614+x61=1;x38+x31=1;x26+x214+x21=1;x31+x81+x21+x61=1;x38