数学建模(工件加工排序).pdf

《数学建模(工件加工排序).pdf》由会员分享，可在线阅读，更多相关《数学建模(工件加工排序).pdf（12页珍藏版）》请在三一文库上搜索。

1、数学建模竞赛试题：数学建模竞赛试题： C 题：工件加工排序题：工件加工排序 计划排序问题中的车间作业问题，研究 n 个工件在 m 台机器上有序的加工问题，每个 工件都有完工的日期（DD，Due date）, 加工的时间（PT，Processing time）和工件的价值 （VAL，Value if job is selected）. 现研究一个工厂生产工序的计划和安排，需要计划与合理 安排各个工件在这些机器上加工的先后次序， 即拟订加工工序， 通过各个工件在各种机器上 加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个 零件的加工时间和加工其他零件时它们等待时间之

2、和）或要求整个选择加工的工件价值最 大。 有一个工厂现在有 12 种工件（编号为工件 1，工件 2，工件 12）需要在车床，钻 床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题： (一) 这 12 种工件都要求在车床上加工，车床一次只能加工一种工件，这 12 种工件加工 所需时间，每个工件的完工时间和每个工件的价值如表（1）所示： 工件 加工时间（h） 完工时间(h) 工件价值 1 2.8 9 8 2 3.2 7.5 4 3 1.2 15 16 4 4 23 3 5 2.7 10 7 6 0.9 22 20 7 2.5 17 17 8 3.3 33 11 9 1.7 7 7 10 2

3、.5 18 12 11 3.6 25 5 12 4.7 11 18 表（1） 1) 不考虑工件的完工时间和工件的价值，为该工厂安排工件加工的次序，使得完成这批 工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。 2) 由于工件必须在它们要求的时间内完工，按照表（1）的数据，为该工厂安排选择加 工工件的种类及加工的次序，使得整个选择加工的工件价值最大。建立数学模型并给 出相应的算法。 (二) 如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工 之前必须先在车床上加工过） ， 每种机器一次只能加工一种工件， 这 12 种工件加工所需 时间如表（2）所示： 工件

4、 车床加工时间（h） 钻床加工时间(h) 1 2.8 4 2 3.2 1.3 3 1.2 1.8 4 4 2.2 5 2.7 3 6 0.9 4.5 7 2.5 1.7 8 3.3 2.5 9 1.7 4.5 10 2.5 2.5 11 3.6 3.8 12 4.7 1.9 表（2） 为该工厂安排工件加工的次序， 使得完成这批工件加工任务所需的总时间最省。 建立数 学模型并给出相应的算法。 (三) 如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加 工，每种机器一次只能加工一种工件，这 12 种工件加工所需时间如表（三）所示： 工件 车床加工时间（h） 钻床加工时间

5、(h) 铣床加工时间(h) 1 2.8 4 3 2 3.2 1.3 1 3 1.2 1.8 2.5 4 4 2.2 1.3 5 2.7 3 1.8 6 0.9 4.5 2 7 2.5 1.7 3.6 8 3.3 2.5 0.8 9 1.7 4.5 1 10 2.5 2.5 1.1 11 3.6 0.9 1.3 12 4.7 1.9 0.7 表（3） 为该工厂安排工件加工的次序， 使得完成这批工件加工任务所需的总时间最省。 建立数 学模型并给出相应的算法。 (四) 对于上述问题你做出的数学模型和相应的算法给出评价。并将模型推广到 n 个工件 在 m 台机器上加工的一般的工件排序问题，给出你的想法

6、和解决问题的思路。 解题正文：解题正文： C 题：工件加工排序 C 题：工件加工排序 （建模小组成员： AP0308306 陈运标 AP0308307 邓风仪 AP0206311 黄深泉） 摘要 摘要 本题根据已知数据，结合问题中的具体要求，我们引入 0/1 变量建立工件排 序的数学规划模型。借助 Lingo 软件进行求解运算，得出其中的最优排序方案。 使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件 （排序后） 完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总 时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。 模型的假设：模型的假设：在后

7、面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即 将整个工件加工过程简化为一个连续的过程，只考虑机床在加工工件时其他工件的等待时 间。 模型的建立：模型的建立：我们的思路是引入 0/1 变量对工件进行动态排序，根据问题要求得出排 序后的目标函数（即数学模型） 。根据题目的约束条件，利用 Lingo 软件算出模型的最优解， 从而获得工件的最优排序。 问题问题（一）（一）题目要求：12 种工件都要求在车床上加工，车床一次只能加工一种工件。设 i 工件车床加工时间为 Ai ,规定完工时间为 Bi,工件价值为 Ci 1） 不考虑工件的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件

8、加工任 务所需的总时间最省。 分析：引入 0/1 变量，利用目标函数最优化工件排序。 设为 i 工 件 实 际 完 工 时 间 ， 所 以 完 成 这 批 工 件 的 总 时 间 为 T=, 而 =A+Ai=A+A+Ai=A1+A += i T 1 12 1 i i T i T i2i1i2i A 1 i j j A 因此: 建立问题（建立问题（1）的目标函数即数学模型为）的目标函数即数学模型为 Min= 12 11 i j ij A 定义 x1，x x144为 0/1 变量，为原始工件序列下 i 工件的车床加工 时间；所以 21 a 2 a 12 a A1=x1a1+x a +.+x12a1

9、2 22 A =x13a1+x14a +.+xa12 2224 . . A12=xa1+x134a +.+xa12 1332 144 x1+x +.+x12=1 2 x13+x14+.+x=1 24 . . . x133+x134+.+x144=1 x1+x13+x+x121+x=1 25133 x +x14+x+x122+x134=1 226 . . . x12+x+x+x132+x144=1 2436 Lingo 程序： （附 wenti(1).lg4 文件） model: !不考虑完工时间和工件价值的排序问题; sets: gongjian/g1.g12/:shijian; !属性为原始

10、排序下各个工件的机床加工时间; shunxu/s1.s12/:time,fin_time; !属性为重新排序后各工件的机床加工时间和完成车工序的 时间; links(shunxu,gongjian): note; endsets !目标函数：求各个工件的加工总时间和最小; min=sum(shunxu(I):fin_time(I); !重新排序后各工件的机床加工时间; for(shunxu(J): time(J)=sum(gongjian(I):shijian(I)*note(I,J); ); !排序后各个工件的加工总时间; for(shunxu(I): fin_time(I)=sum(shu

11、nxu(J)|J#le#I:time(J); ); !每个顺序位只能有一个工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每个工件只能排在一个顺序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; ); !定义 0/1 变量; for(links:bin(note); data: !输出数据到 Excel 文档; OLE(D:liebiao.XLS)=time,fin_time; !原始排序下各个工件的机床加工时间; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.

12、3,1.7,2.5,3.6,4.7; enddata end 结果数据： 工件 加工时间 i A完成时间Ti 6 0.9 0.9 3 1.2 2.1 9 1.7 3.8 10 2.5 6.3 7 2.5 8.8 5 2.7 11.5 1 2.8 14.3 2 3.2 17.5 8 3.3 20.8 11 3.6 24.4 4 4 28.4 12 4.7 33.1 总计：171.9 表 1-1 所以最优排序是 639107512811412 完成这批工件加工任务所需的最省总时间为 171.9 2) 分析分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完 毕之间所用的总时

13、间应少于该工件的规定完工时间。 所以要使整个加工任务的工件总价值最 大，必须合理选择加工工件的种类及其加工的次序。 引入 0-1 变量,若选择 i 工件加工,则记 Yi=1.否则记 Yi=0; 工件的排序算法同问题 1） ，但约束条件有所不同。在本题中，12 种工件不一定都可以入选 到最优加工序列中（即目标排序中可能出现工件空缺） ，所以 12 , 1 0 j i i X (j=1, 2, .12)， 且 (i=1, 2, .12)， 12 , 1 0 i j j X , i j X为 0-1 变量。用 Lingo 进行编程，工件集加入原始排序 下车床加工时间，完工时间和工件价值属性；顺序集加

14、入重新排序后车床加工时间，完工时 间和工件价值属性；因此该模型为： 目标函数: Max= （在排序算法及程序中已隐含有） i i iY C 12 1 i Y 工件选择： ( 12 , 1 0 j i i X j=1, 2, .12)， 12 , 1 0 i j j X (i=1, 2, .12) 完工时间约束： ( 1 j iij i AYB j=1, 2, .12) Lingo 程序： （wenti(2).lg4 文件） model: !考虑完工时间和工件价值的排序问题; sets: gongjian/g1.g12/:shijian,endtime,gj_value; ! 属性为原始排序下各

15、个工件的机床加工时间， 完工时间，工件价值; shunxu/s1.s12/:time,overtime,fin_value; ! 属性为重新排序后各个工件的机床加工时间，完 工时间，工件价值; links(shunxu,gongjian): note; endsets !目标函数; max=sum(shunxu(I):fin_value(I); !从新排序后各工件的机床加工时间（可能为零，即表示未选中工件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J); !从新排序后各工件的完工时间（可能为零，即表示未选中工件）; f

16、or(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); ); !从新排序后各工件的工件价值（可能为零，即表示未选中工件）; for(shunxu(I): fin_value(I)=sum(gongjian(J):gj_value(J)*note(I,J); ); !每个顺序位只能有一个工件或者没有工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1); !每个工件只能排在一个顺序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1); !各

17、工件的完工时间约束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)=overtime(I); ); !定义 0/1 变量; for(links:bin(note); data: !原始排序下各个工件的机床加工时间; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各个工件的完工时间; endtime=9,7.5,15,23,10,22,17,33,7,18,25,11; !原始排序下各个工件的工件价值; gj_value=8,4,16,3,7,20,17,11,7,12,5,1

18、8; enddata end 模型结果： 导出列表： 工件顺序 车床加工时间 规定的完工时间 各工件价值 000 000 1 2.898 5 1.777 12 4.71118 10 2.51812 3 1.21516 6 0.92220 7 2.51717 2 4233 11 3.6255 8 3.33311 总价值：117 表 1-2 由上表可知，最优方案是选择工件由上表可知，最优方案是选择工件 1512103672118，并 按此顺序进行加工。从而获得最大的工件总价值为 ，并 按此顺序进行加工。从而获得最大的工件总价值为 117. 关于问题（二） ， （三） ， （四）关于问题（二） ，

19、（三） ， （四） 分析：分析：问题（二）要求：问题（二）要求：如果这 12 种工件都要求先在车床上加工，然后再在钻床上加 工（即工件在钻床加工之前必须先在车床上加工过） ，每种机器一次只能加工一种工件，求 工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义， 某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间， 等待上一个工件加工完的时间 （即从该工件在车床加工完毕时刻起到其上一个工件在钻床上 加工完毕这一段时间） ，该工件在钻床上加工的时间。我们假设i工件在车床 (1) M加工所需 时间为 (1) i X，在钻床上 (2) M加工所需

20、时间为 (2) i X；i工件完成在车床 (1) M加工的总时间为 (1) i M； （）工件完成在钻床1i (2) M加工的总时间为 (2) 1i M ， （） 。这里要分两种情况进 行分析： 1i 1).当 (1) i M (2) 1i M 时，即 工件完成车工序的总时间大于或等于（i1i）工件完成钻工序的 总时间，此时i工件不需要等待（）工件而立即就进入钻工序，因此i工件完成钻床工序 的总时间表达式为 1i (2) i M (1) i M+ (2) i X; 2).当 (1) i M (2) 1i M 时，即i工件完成车工序的总时间小于或等于（1i）工件完成钻工序的 总时间，此时i工件需

21、要等待（）工件完成钻床工序才能进入钻床加工。因此i工件完成 钻床工序的总时间表达式为 1i (2) i M (2) 1i M + (2) i X。 综合以上两种情况，得到i工件完成钻床工序的总时间计算公式为 (2) i MMax（ (1) i M， (2) 1i M ）+ （） (2) i X1i 同理，对于问题（三） ，我们也可以得到类似的计算公式.，下面是以列表的形式将这一 推导公式推广到i工件j个工序的情况： 假设 i 工件在车床 (1) M加工所需时间为 (1) i X；在钻床上 (2) M加工所需时间为 (2) i X；在 铣床 (3) M上加工所需要的时间为 (3) i X；在后续

22、的各工序（ ( ) j M）中加工所需要的时间设为 ( ) j i X；下表中内容表示 i 工件从任务开始时刻起到完成 ( j) M道工序止所需要的总时间 j i M 床铣床铣 (3) M 工序 顺序 床床 钻床钻床 (2) M j 工件顺序 车车 (1) M 加工加工 ( ) j M 1 (1) 1 0X (1) 1 M+ (2) 1 X (2) 1 M+ (3) 1 X (1) 1 j M + ( ) 1 j X 2 (1) 1 M+ (1) 2 X Max（ (1) 2 M ， (2) 1 M ）+ (2) 2 X Max （ (2) 2 M ， (3) 1 M ） + (3) 2 X

23、Max（ (1) 2 j M ， ( ) 1 j M ）+ ( ) 2 j X 3 3 (1)(1) 2 MX Max（ (1) 3 M ， (2 2 ) M ）+ (2) 3 X Max （ (2) 3 M ， (3 2 ) M ） + (3) 3 X Max（ (1) 3 j M ， ( ) 2 j M ）+ ( ) 3 j X i (1)(1) 1ii MX Max（ (1) i M ， (2) 1i M ）+ (2) i X Max （ (2) i M ， (3) 1i M ） + (3) i X Max（ (1)j i M ， ( ) 1 j i M ）+ ( ) j i X 表表

24、2-1 模型的建立：模型的建立： 工任务的最省总时间即为在最优排序下各工件 根据表 2-1，问题（二）中要求的完成加 完成钻床加工工序的总时间之和。 12 2i Max（ (1) i M， (2) 1i M ）+ (2) i X； 即建立问题（二）的数学模型为即建立问题（二）的数学模型为 Max= (2) 1 M+ 这里这里 1 (2) M 1 (1) M+ 1 (2) X； go Lin编程：附录 1（wenti(3).lg4）文件 （三）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加 同理，问题 工工序的总时间之和。 12 2i Max（ (2) i M， (3) 1i

25、M ）+ (3) i X； 建立问题（三）的数学模型为建立问题（三）的数学模型为 Max= (3) 1 M+ 这里这里 1 (3) M 1 (2) M+ 1 (3) X； Lo 编程：文件ing附录 2（wenti(4).lg4） i 个工件 j 部机 建立问题（四）的数学模型为建立问题（四）的数学模型为 Max= 归纳以上算式，推广到床的工件排序问题， ( ) 1 j M+ 2i i Max（ (1)j i M ， ( ) 1 j i M ）； + ( ) j i X 这里这里 1 ( ) j M 1 + 1 X (1)j M (1)j ；ngo 编程： （略） Li 模型结果：模型结果：

26、号 车床加工时 间 问题（二）问题（二） 运算后导出列表： 钻床加工时 间 (1) i X 完成车床工序 总时间 i (1) M 顺序号 工件 (1) i X 完成钻床工序 总时间 i (2) M 1 3 1.21.2 3 2 6 0.94.52.1 7.5 9. 1 1 20 2.1822 2. 28 1. 总时间：224 由上表可知，最优的工件排序为由上表可知，最优的工件排序为 3 72594 间为 间为 224.8。 1.8 3 7 2.51.74.6 2 4 2 3.21.37.8 0.5 5 10 2.52.50.3 13 6 5 2.7313 16 7 9 1.74.514.7 .

27、5 8 4 42.7 .7 9 8 3.32.522 25.2 10 1 8424.8 29.2 11 11 3.63.8.4 33 12 12 4.7933.1 35 .8 表表 2-2 6108111 12，完成这批工件加工任务所需的最省总时，完成这批工件加工任务所需的最省总时 问题（三）问题（三） 表： 车床加工时间 运算后导出列 钻床加工时间 (1) i X 铣床加工时间 (1) i X 顺序号 工件号 (1) i X 1.21.82.5 2 9 0.94.52 1. 1. 0. 1.0. 表表 顺序号 工件号 总时间 1 3 3 11 3.60.91.3 4 10 2.52.51 5

28、 7 2.51.73.6 6 9 1.74.51 7 2 3.21.31 8 5 2.738 9 8 3.32.58 10 1 2.843 11 4 42.21.3 12 12 4.797 2-3 完成车床工序完成钻床工序总 时间 (2) i M (1) i M 完成铣床工序总 时间 (3) i M 1 3 1.235.5 2 9 2.17.59.5 8.1 1 11 118 总时间：2 从软件的运行情况可知，最优的工件排序为从软件的运行情况可知，最优的工件排序为 39258 需的最省总时间为需的最省总时间为 239.4 3 11 5.740.8 4 10 8.20.912 5 7 0.72.

29、616.2 6 9 2.417.1.1 7 2 15.618.419.4 8 5 18.321.423.2 9 8 21.624.124.9 10 1 24.428.431.4 11 4 28.430.632.7 12 12 33.13535.7 39.4 表 2-4 111079 1412；完成这批工件加工任务所；完成这批工件加工任务所 - 12 - ，我们始终围绕一种化整为零 最优的排序下每个工件的实际 有很强的可移植性，便于模型的推广。列如在推广到 m 工 考资料：考资料： 姜启源 等，数学模型（第三版），高等教育出版社，2003。 忠， Lingo4.0 for windows 最优化

30、软件及应用， 北京大学出版社， 2001。 模型评价，改进方法，推广 模型评价，改进方法，推广 11 在本题的解答过程中所建立的数学规划模型中 的数学思想，将整批工件的加工任务拆分为在 加工情况来分析，根据各工件在加工过程中加工时间和总时间之间的联系， 寻求各工件加工总时间的具体算法。再利用 Lingo 软件进行求解模型，得出 工件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了 软件求解效率。 2 由于在模型求解中利用了 Lingo 软件，大大简化了编程工作，且模型本身结 合软件的使用就具 件 n 部机床的情况，只需在程序中的工件，顺序集里加入相应的属性；在程 序段中加入对应的算法和约束条件就可以完全替换从而解决问题了。 参参 1 2 洪文 吴本 3 4