工件排序

-1-计划排序问题中的车间作业问题，研究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）所示：工件车床加工时间（h）钻床加工时间(h)12.8423.21.3-2-31.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台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。结果数据：工件加工时间iA完成时间Ti-3-60.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.92)分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完毕之间所用的总时间应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最大，必须合理选择加工工件的种类及其加工的次序。引入0-1变量,若选择i工件加工,则记Yi=1.否则记Yi=0;工件的排序算法同问题1），但约束条件有所不同。在本题中，12种工件不一定都可以入选到最优加工序列中（即目标排序中可能出现工件空缺），所以12,10jiiX(j=1,2,….12)，且12,10ijjX(i=1,2,….12)，,ijX为0-1变量。用Lingo进行编程，工件集加入原始排序下车床加工时间，完工时间和工件价值属性；顺序集加入重新排序后车床加工时间，完工时间和工件价值属性；因此该模型为：目标函数:Max=iiiYC121（在排序算法及程序中已隐含有iY）工件选择：12,10jiiX(j=1,2,….12)，12,10ijjX(i=1,2,….12)完工时间约束：1jiijiAYB(j=1,2,….12)Lingo程序：（wenti(2).lg4文件）-4-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-5-模型结果：导出列表：工件顺序车床加工时间规定的完工时间各工件价值00000012.89851.777124.71118102.5181231.2151660.9222072.5171724233113.625583.33311总价值：117表1-2由上表可知，最优方案是选择工件1－5－12－10－3－6－7－2－11－8，并按此顺序进行加工。从而获得最大的工件总价值为117.关于问题（二），（三），（四）分析：问题（二）要求：如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，求工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，等待上一个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工件在钻床上加工完毕这一段时间），该工件在钻床上加工的时间。我们假设i工件在车床(1)M加工所需时间为(1)iX，在钻床上(2)M加工所需时间为(2)iX；i工件完成在车床(1)M加工的总时间为(1)iM；（1i）工件完成在钻床(2)M加工的总时间为(2)1iM，（1i）。这里要分两种情况进行分析：1).当(1)iM(2)1iM时，即i工件完成车工序的总时间大于或等于（1i）工件完成钻工序的总时间，此时i工件不需要等待（1i）工件而立即就进入钻工序，因此i工件完成钻床工序的总时间表达式为(2)iM(1)iM+(2)iX;2).当(1)iM(2)1iM时，即i工件完成车工序的总时间小于或等于（1i）工件完成钻工序的-6-总时间，此时i工件需要等待（1i）工件完成钻床工序才能进入钻床加工。因此i工件完成钻床工序的总时间表达式为(2)iM(2)1iM+(2)iX。综合以上两种情况，得到i工件完成钻床工序的总时间计算公式为(2)iMMax（(1)iM，(2)1iM）+(2)iX（1i）同理，对于问题（三），我们也可以得到类似的计算公式.，下面是以列表的形式将这一推导公式推广到i工件j个工序的情况：假设i工件在车床(1)M加工所需时间为(1)iX；在钻床上(2)M加工所需时间为(2)iX；在铣床(3)M上加工所需要的时间为(3)iX；在后续的各工序（()jM）中加工所需要的时间设为()jiX；下表中内容表示i工件从任务开始时刻起到完成()jM道工序止所需要的总时间jiM工序顺序工件顺序车床(1)M钻床(2)M铣床(3)M…j加工()jM1(1)10X(1)1M+(2)1X(2)1M+(3)1X…(1)1jM+()1jX2(1)1M+(1)2XMax（(1)2M，(2)1M）+(2)2XMax（(2)2M，(3)1M）+(3)2X…Max（(1)2jM，()1jM）+()2jX3(1)(1)23MXMax（(1)3M，(2)2M）+(2)3XMax（(2)3M，(3)2M）+(3)3X…Max（(1)3jM，()2jM）+()3jX………………i(1)(1)1iiMXMax（(1)iM，(2)1iM）+(2)iXMax（(2)iM，(3)1iM）+(3)iX…Max（(1)jiM，()1jiM）+()jiX表2-1模型的建立：根据表2-1，问题（二）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成钻床加工工序的总时间之和。-7-即建立问题（二）的数学模型为Max=(2)1M+122i{Max（(1)iM，(2)1iM）+(2)iX}；这里(2)1M＝(1)1M+(2)1X；Lingo编程：附录1（wenti(3).lg4）文件同理，问题（三）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加工工序的总时间之和。建立问题（三）的数学模型为Max=(3)1M+122i{Max（(2)iM，(3)1iM）+(3)iX}；这里(3)1M＝(2)1M+(3)1X；Lingo编程：附录2（wenti(4).lg4）文件归纳以上算式，推广到i个工件j部机床的工件排序问题，建立问题（四）的数学模型为Max=()1jM+2ii{Max（(1)jiM，()1jiM）+()jiX}；这里()1jM＝(1)1jM+(1)1jX；Lingo编程：（略）模型结果：问题（二）运算后导出列表：顺序号工件号车床加工时间(1)iX钻床加工时间(1)iX完成车床工序总时间(1)iM完成钻床工序总时间(2)iM131.21.81.23260.94.52.17.5372.51.74.69.2423.21.37.810.55102.52.510.313652.731316791.74.514.720.58442.218.722.7983.32.52225.21012.8424.829.211113.63.828.43312124.71.933.135总时间：224.8表2-2由