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

数学建模竞赛试题：C题：工件加工排序计划排序问题中的车间作业问题，研究n个工件在m台机器上有序的加工问题，每个工件都有完工的日期（DD，Duedate）,加工的时间（PT，Processingtime）和工件的价值（VAL，Valueifjobisselected）.现研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有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）所示：-1-工件车床加工时间（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.3131.21.82.5442.21.352.731.860.94.5272.51.73.683.32.50.891.74.51102.52.51.1113.60.91.3124.71.90.7表（3）为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。(四)对于上述问题你做出的数学模型和相应的算法给出评价。并将模型推广到n个工件在m台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。解题正文：-2-C题：工件加工排序（建模小组成员：AP0308306陈运标AP0308307邓风仪AP0206311黄深泉）摘要本题根据已知数据，结合问题中的具体要求，我们引入0/1变量建立工件排序的数学规划模型。借助Lingo软件进行求解运算，得出其中的最优排序方案。使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。模型的假设：在后面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即将整个工件加工过程简化为一个连续的过程，只考虑机床在加工工件时其他工件的等待时间。模型的建立：我们的思路是引入0/1变量对工件进行动态排序，根据问题要求得出排序后的目标函数（即数学模型）。根据题目的约束条件，利用Lingo软件算出模型的最优解，从而获得工件的最优排序。问题（一）题目要求：12种工件都要求在车床上加工，车床一次只能加工一种工件。设i工件车床加工时间为Ai,规定完工时间为Bi,工件价值为Ci1）不考虑工件的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。分析：引入0/1变量，利用目标函数最优化工件排序。设为i工件实际完工时间，所以完成这批工件的总时间为T=,而=A+Ai=A+A+Ai=A1+A+………+=iT1121iiTiTi2i1i2iA1ijjA因此:建立问题（1）的目标函数即数学模型为Min=1211ijijA定义x1，x……x144为0/1变量，，，…为原始工件序列下i工件的车床加工时间；所以21a2a12a-3-A1=x1a1+xa+……..+x12a1222A=x13a1+x14a+……..+xa122224..A12=xa1+x134a+……..+xa121332144x1+x+…….+x12=12x13+x14+…….+x=124...x133+x134+…….+x144=1x1+x13+x+……+x121+x=125133x+x14+x+……+x122+x134=1226...x12+x+x+……+x132+x144=12436Lingo程序：（附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):-4-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结果数据：工件加工时间iA完成时间Ti60.90.931.22.191.73.8102.56.372.58.852.711.512.814.323.217.583.320.8113.624.44428.4124.733.1总计：171.9表1-1所以最优排序是6－3－9－10－7－5－1－2－8－11－4－12完成这批工件加工任务所需的最省总时间为171.9-5-2)分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完毕之间所用的总时间应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最大，必须合理选择加工工件的种类及其加工的次序。引入0-1变量,若选择i工件加工,则记Yi=1.否则记Yi=0;工件的排序算法同问题1），但约束条件有所不同。在本题中，12种工件不一定都可以入选到最优加工序列中（即目标排序中可能出现工件空缺），所以12,10jiiX(j=1,2,….12)，且(i=1,2,….12)，12,10ijjX,ijX为0-1变量。用Lingo进行编程，工件集加入原始排序下车床加工时间，完工时间和工件价值属性；顺序集加入重新排序后车床加工时间，完工时间和工件价值属性；因此该模型为：目标函数:Max=（在排序算法及程序中已隐含有）iiiYC121iY工件选择：(12,10jiiXj=1,2,….12)，12,10ijjX(i=1,2,….12)完工时间约束：(1jiijiAYBj=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):-6-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模型结果：导出列表：工件顺序车床加工时间规定的完工时间各工件价值00000012.89851.777124.71118102.5181231.2151660.9222072.5171724233113.625583.33311总价值：117表1-2由上表可知，最优方案是选择工件1－5－12－10－3－6－7－2－11－8，并按此顺序进行加工。从而获得最大的工件总价值为117.-7-关于问题（二），（三），（四）分析：问题（二）要求：如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，求工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，等待上一个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工件在钻床上加工完毕这一段时间），该工件在钻床上加工的时间。我