资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
wordP1187加工生产调度题目解析:此题是要求一个加工顺序使得总的加工时间最少,而要使加工时间最少,就是让各车间的空闲时间最少。一旦A车间开始加工,便会不停地进展加工(我们不要去管车间是否能够一直生产,因为他们有三班,可以24时间不停地运转)。关键是B车间在生产的过程中,有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时,B车间是要等待的,最后一个产品在B车间加工时,A车间已经完成了任务。要使总的空闲时间最少:1就要把在A车间加工时间最短的部件优先加工,这样使得B车间能以最快的速度开始加工;2把放在B车间加工时间最短的产品放在最后加工,这样使得最后A车间的空闲时间最少。 设计出这样的贪心法: 设MiminAi,Bi 将M按照由小到大的顺序排序,然后从第一个开始处理,如果Mi=Ai,如此将它安排在从头开始的已经安排的生产顺序后面,如果MiBi,如此将它安排在从尾开始的已安排的生产顺序前面。这种安排是否是最少的加工时间,还要通过数学证明。证明如下:请学生自行证明完成!特殊案例分析:1考虑Ai=Bi的任务的高度情况怎样为最优方案。2考虑Ai=Bi的任务的调度情况怎样为最优方案。提出、分析、证明。概念1:最大缓冲区域 设SJ1,J2,Jn),是等待加工的作业序列,如果A车间开始加工S中的产品时,B车间还在加工其他产品,t时刻后B车间就可利用A车间加工过的产品。在这样的条件下,加工S中任务所要的最短时间T(S, t)=minAi+T(s-Ji,Bi+maxt-Ai, 0),其中,JiS。图3-1是加工作业i时A车间等待B车间的情况:图3-1 A等B的情况图3-2是加工作业i时B车间等待A车间的情形:图3-2 B等A的情况假设最优的方案中,先加工作业Ji,然后再加工作业Jj,如此有:如果,如此如果,如此如果,如此如果将作业Ji和作业Jj的加工顺序调整,如此有:其中,按照上面的假设,有T=T,所以有:从而有:即:这说是所谓的Johnson公式,也就是说在此公式成立的条件下,优先安排任务Ji在Jj之前可以得到最优解。也就是在A车间加工时间短的安排在前面,在B车间加工时间短的任务安排在后面。以样例数据为例:A1, A2, A3, A4, A5=3, 5, 8, 7, 10B1, B2, B3, B4, B5=6, 2, 1, 4, 9如此m1, m2, m3, m4, m5=3, 2, 1, 4, 9排序之后为:m3, m2, m1, m4, m5处理m3,因为m3=B3,所以m3安排在后面,3;处理m2,因为m2=B2,所以m2安排在后面,2,3;处理m1,因为m1=A1,所以m1安排在前面1,2,3;处理m4,因为m4=B4,所以m4安排在后面1,4,2,3;处理m5,因为m5=B5,所以m5安排在后面1,5,4,2,3。从而得到加工的顺序1,5,4,2,3。计算出最短的加工时间34。【补充说明】由于此题的原始数据并没有保证数据间没有重复,所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。思考2:任务j如果aj=bj在A车间的加工时间与其在B车间的加工时间一样的话,任务j的加工处理在任何时侯处理都一样,也就是说加工过程中如果我们在最优方案根底上,仅仅是调整任务j的加工顺序,如此将得到一个等效的加工方案。证明: 在的最优方案中,如果有任务i,并且Ai=Bi,如此如果改变其加工顺序。我们将得到一个等效的最优加工方案。根据以上特征,为了让输出解达到唯一,我们只有进而求其次,我在测试数据中修改了一下,将所有的测试数据均改为AiBi概念1:最大缓冲区域program prod;type data=record 任务数据特征分析:序号、A车间加工时间、B车间加工时间,最小时间 num,tima,timb,min:integer; end; arr=array1.1000of data;var a,b:arr; n,i,j,k:integer; sa,sb:longint;快速排序,不稳定,排序过程按min的值从小到大进展procedure qsort(var a:arr; l,r:integer); var i,j,m:integer; t:data; begin i:=l; j:=r; m:=a(i+j)div 2.min; repeat while ai.minm do inc(i); while maj.min do dec(j); if ij; if lj then qsort(a,l,j); if ir then qsort(a,i,r); end;begin readln(n); sa:=0; for i:=1 to n do begin read(ai.tima); inc(sa,ai.tima); ai.num:=i; ai.min:=ai.tima; 预处理:min的值 end; for i:=1 to n do begin read(ai.timb); if ai.timbsa,最后输出加工时间总流程为sb。统计A车间B车间从开始工作,到全部加工完毕总共所占用时间。变量i指向A车间当前加工的任务标号,sa用来记录此时A车间的加工时间。变量j指向B车间当前加工的任务的标号,sb用来记录此时B车间的加工时间。 i:=1; j:=0; sa:=b1.tima; sb:=b1.tima; repeatinc(i); inc(j);当前B车间加工所用时间为:(sb+bj.timb),而B车间下一任务的加工时间也有可能需要取决于A车间的加工情况,因为只有A车间中当前任务:(sa+bi.tima)已经完毕的话,B车才可以加工下一任务,因为分两种情况来考虑: if (sa+bi.tima)=(sb+bj.timb) A车间中当前任务:(sa+bi.tima)没有完毕 then begin inc(sa,bi.tima); sb:=sa; B车间尽管会先完毕,但其必须等待A车间完毕才可以加工下一任务,因而要调整其加工延迟时间为A车间当前任务加工完毕时间 end else begin A车间中当前任务:(sa+bi.tima)已经完毕,如此不会影响到B车间的下一任务加工调度,因为分别独立处理 inc(sa,bi.tima); inc(sb,bj.timb); end; until (i=n)and(j=n-1);A车间加工完,B车间最后一个任务还未做! inc(sb,bn.timb);追加B车间最后一个任务到sb时间上来 writeln(sb);输出全部AB车间完毕所耗时间 write(b1.num); for i:=2 to n do write( ,bi.num); writeln;end. /
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号