数学建模C题论文(工件加工排序).doc

命题人： 邹祥福 审批人： 试卷分类（A卷或B卷） A 数学建模竞赛试题：C题：工件加工排序计划排序问题中的车间作业问题，研究n个工件在m台机器上有序的加工问题，每个工件都有完工的日期（DD，Due date）, 加工的时间（PT，Processing time）和工件的价值（VAL，Value if job is selected）. 现研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有12种工件（编号为工件1，工件2，工件12）需要在车床，钻床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题：(一) 这12种工件都要求在车床上加工，车床一次只能加工一种工件，这12种工件加工所需时间，每个工件的完工时间和每个工件的价值如表（1）所示：工件加工时间（h）完工时间(h)工件价值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118表（1）1) 不考虑工件的完工时间和工件的价值，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。2) 由于工件必须在它们要求的时间内完工，按照表（1）的数据，为该工厂安排选择加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。建立数学模型并给出相应的算法。(二) 如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，这12种工件加工所需时间如表（2）所示： 工件车床加工时间（h）钻床加工时间(h)12.8423.21.331.21.8442.252.7360.94.572.51.783.32.591.74.5102.52.5113.63.8124.71.9 表（2）为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。 (三) 如果这12种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加工，每种机器一次只能加工一种工件，这12种工件加工所需时间如表（三）所示：工件车床加工时间（h）钻床加工时间(h)铣床加工时间(h)12.84323.21.3442.21.352.731.860.94.5291.74.51表（3）为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。(四) 对于上述问题你做出的数学模型和相应的算法给出评价。并将模型推广到n个工件在m台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。解题正文：C题：工件加工排序（建模小组成员： AP0308306 陈运标 AP0308307邓风仪 AP0206311 黄深泉） 摘要本题根据已知数据，结合问题中的具体要求，我们引入0/1变量建立工件排序的数学规划模型。借助Lingo软件进行求解运算，得出其中的最优排序方案。使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。模型的假设：在后面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即将整个工件加工过程简化为一个连续的过程，只考虑机床在加工工件时其他工件的等待时间。模型的建立：我们的思路是引入0/1变量对工件进行动态排序，根据问题要求得出排序后的目标函数（即数学模型）。根据题目的约束条件，利用Lingo软件算出模型的最优解，从而获得工件的最优排序。问题（一）题目要求：12种工件都要求在车床上加工，车床一次只能加工一种工件。设 i 工件车床加工时间为A ,规定完工时间为B,工件价值为C1） 不考虑工件的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。分析：引入0/1变量，利用目标函数最优化工件排序。 设为i工件实际完工时间，所以完成这批工件的总时间为T=,而 =A+A=A+A+A=A+A+=因此: 建立问题（1）的目标函数即数学模型为Min= 定义x，xx为0/1变量，为原始工件序列下i工件的车床加工时间；所以A=xa+xa+.+xaA=xa+xa+.+xa . A=xa+xa+.+xax+x+.+x=1x+x+.+x=1.x+x+.+x=1x+x+x+x+x=1x+x+x+x+x=1.x+x+x+x+x=1Lingo程序：（附wenti(1).lg4文件）model: !不考虑完工时间和工件价值的排序问题;sets: gongjian/g1.g12/:shijian; !属性为原始排序下各个工件的机床加工时间; 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(shunxu(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.3,1.7,2.5,3.6,4.7;enddataend结果数据：工件加工时间完成时间T60.90.93.8102.56.372.58.852.711.512.814.323.217.583.320.8113.624.44428.4124.733.1总计：171.9 表1-1 所以最优排序是639107512811412完成这批工件加工任务所需的最省总时间为171.92) 分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完毕之间所用的总时间应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最大，必须合理选择加工工件的种类及其加工的次序。 引入0-1变量,若选择i工件加工,则记Y=1.否则记Y=0;工件的排序算法同问题1），但约束条件有所不同。在本题中，12种工件不一定都可以入选到最优加工序列中（即目标排序中可能出现工件空缺），所以 (=1, 2, .12)，且 (=1, 2, .12)，为0-1变量。用Lingo进行编程，工件集加入原始排序下车床加工时间，完工时间和工件价值属性；顺序集加入重新排序后车床加工时间，完工时间和工件价值属性；因此该模型为：目标函数: Max= （在排序算法及程序中已隐含有）工件选择： (=1, 2, .12)， (=1, 2, .12)完工时间约束： (=1, 2, .12)Lingo程序：（wenti(2).lg4文件）model: !考虑完工时间和工件价值的排序问题;sets: gongjian/g1.g12/:shijian,endtime,gj_value; ! 属性为原始排序下各个工件的机床加工时间，完工时间，工件价值; 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);!从新排序后各工件的完工时间（可能为零，即表示未选中工件）;for(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); !各工件的完工时间约束; 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,18;enddataend模型结果：导出列表：工件顺序车床加工时间规定的完工时间各工件价值000000 12.898 51.777 124.71118 102.51812 31.21516 60.92220 72.51717 24233 113.6255 83.33311总价值：117 表1-2 由上表可知，最优方案是选择工件1512103672118，并按此顺序进行加工。从而获得最大的工件总价值为117.关于问题（二），（三），（四）分析：问题（二）要求：如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，求工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，等待上一个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工件在钻床上加工完毕这一段时间），该工件在钻床上加工的时间。我们假设工件在车床加工所需时间为，在钻床上加工所需时间为；工件完成在车床加工的总时间为；（）工件完成在钻床加工的总时间为，（）。这里要分两种情况进行分析： 1).当时，即工件完成车工序的总时间大于或等于（）工件完成钻工序的总时间，此时工件不需要等待（）工件而立即就进入钻工序，因此工件完成钻床工序的总时间表达式为+; 2).当时，即工件完成车工序的总时间小于或等于（）工件完成钻工序的总时间，此时工件需要等待（）工件完成钻床工序才能进入钻床加工。因此工件完成钻床工序的总时间表达式为+。 综合以上两种情况，得到工件完成钻床工序的总时间计算公式为 Max（，）+ （） 同理，对于问题（三），我们也可以得到类似的计算公式.，下面是以列表的形式将这一推导公式推广到工件个工序的情况：假设i工件在车床加工所需时间为；在钻床上加工所需时间为；在铣床上加工所需要的时间为；在后续的各工序（）中加工所需要的时间设为；下表中内容表示i工件从任务开始时刻起到完成道工序止所需要的总时间 工序 顺序 工件顺序车床钻床铣床 加工1+ +2+Max（，）+Max（，）+ Max（，）+3Max（，）+Max（，）+ Max（，）+ iMax（，）+Max（，）+ Max（，）+表2-1模型的建立： 根据表2-1，问题（二）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成钻床加工工序的总时间之和。即建立问题（二）的数学模型为Max=+ （，）+；这里 +；Lingo编程：附录1（wenti(3).lg4）文件同理，问题（三）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加工工序的总时间之和。 建立问题（三）的数学模型为Max=+ （，）+；这里 +；Lingo编程：附录2（wenti(4).lg4）文件归纳以上算式，推广到i个工件j部机床的工件排序问题， 建立问题（四）的数学模型为Max=+ （，）+；这里 +；Lingo编程：（略） 模型结果：问题（二）运算后导出列表：顺序号工件号车床加工时间 钻床加工时间完成车床工序总时间完成钻床工序总时间 1 3 2 7.5 3 9.2 4 10.5 5 102.52.510.313 6 52.731316 7 91.74.514.720.5 8 442.218.722.7 9 83.32.52225.2 10 12.8424.829.2 11 113.63.828.433 12 124.71.933.135总时间：224.8表2-2 由上表可知，最优的工件排序为367210594811112，完成这批工件加工任务所需的最省总时间为224.8。问题（三）运算后导出列表：顺序号 工件号车床加工时间 钻床加工时间铣床加工时间 1 2 90.94.52 3 4 5 6 91.74.51 7 23.21.31 8 52.731.8 9 10 12.843 11 442.21.3 12 表2-3顺序号工件号完成车床工序总时间完成钻床工序总时间完成铣床工序总时间 1 31.235.5 2 3 115.78.410.8 4 108.210.912 5 710.712.616.2 6 912.417.118.1 7 215.618.419.4 8 518.321.423.2 9 821.624.124.9 10 124.428.431.4 11 428.430.632.7 12 1233.13535.7总时间：239.4 表2-4 从软件的运行情况可知，最优的工件排序为391110792581412；完成这批工件加工任务所需的最省总时间为239.4模型评价，改进方法，推广1 在本题的解答过程中所建立的数学规划模型中，我们始终围绕一种化整为零的数学思想，将整批工件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析，根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出工件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率。2 由于在模型求解中利用了Lingo软件，大大简化了编程工作，且模型本身结合软件的使用就具有很强的可移植性，便于模型的推广。列如在推广到m工件n部机床的情况，只需在程序中的工件，顺序集里加入相应的属性；在程序段中加入对应的算法和约束条件就可以完全替换从而解决问题了。参考资料：1 姜启源 等，数学模型（第三版），高等教育出版社，2003。2 洪文 吴本忠，Lingo4.0 for windows 最优化软件及应用，北京大学出版社，2001。3 4 /Forums/1/268/ShowPost.aspx#268 附录一：model: !工件先车后钻的排序问题;sets: gongjian/g1.g12/:che_shijian,zuan_shijian; shunxu/s1.s12/:che_time,zuan_time,che_fintime,zuan_fintime; links(shunxu,gongjian): note;endsets !目标函数; min=sum(shunxu(I):zuan_fintime(I);!从新排序后各工件的车床加工时间; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!从新排序后各工件的钻床加工时间;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); ); !每个顺序位只能有一个工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每个工件只能排在一个顺序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!从新排序后各工件在完成车工序的总时间;for(shunxu(I): che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J); );!从新排序后各工件在完成钻工序的总时间;for(shunxu(I)| I#gt#1:zuan_fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zuan_time(I); ); !顺序1中的工件在完成钻工序的总时间; zuan_fintime(1)=che_fintime(1)+zuan_time(1); !定义0/1变量; for(links:bin(note); data: !原始排序下各个工件的车床加工时间; che_shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各个工件的钻床加工时间; zuan_shijian=4,1.3,1.8,2.2,3,4.5,1.7,2.5,4.5,2.5,3.8,1.9; enddataend附录二：model: !工件先车后钻再铣的的排序问题;sets: gongjian/g1.g12/:che_shijian,zuan_shijian,xi_shijian; shunxu/s1.s12/:che_time,zuan_time,xi_time,che_fintime,zuan_fintime,xi_fintime; links(shunxu,gongjian): note;endsets !目标函数; min=sum(shunxu(I):xi_fintime(I);!从新排序后各工件的车床加工时间; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!从新排序后各工件的钻床加工时间;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); );!从新排序后各工件的铣床加工时间;for(shunxu(I): xi_time(I)=sum(gongjian(J):xi_shijian(J)*note(I,J); ); !每个顺序位只能有一个工件; for(shunxu(I): sum(gongjian(J): note