《P1187加工生产调度》由会员分享，可在线阅读，更多相关《P1187加工生产调度（5页珍藏版）》请在金锄头文库上搜索。
1、wordP1187加工生产调度题目解析：此题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进展加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。要使总的空闲时间最少：1就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；2把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。
2、 设计出这样的贪心法： 设MiminAi，Bi 将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，如此将它安排在从头开始的已经安排的生产顺序后面，如果MiBi，如此将它安排在从尾开始的已安排的生产顺序前面。这种安排是否是最少的加工时间，还要通过数学证明。证明如下：请学生自行证明完成！特殊案例分析：1考虑Ai=Bi的任务的高度情况怎样为最优方案。2考虑Ai=Bi的任务的调度情况怎样为最优方案。提出、分析、证明。概念1：最大缓冲区域 设SJ1，J2，Jn)，是等待加工的作业序列，如果A车间开始加工S中的产品时，B车间还在加工其他产品，t时刻后B车间就可利用A车间加工过的产品。在这样
3、的条件下，加工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车间
4、加工时间短的任务安排在后面。以样例数据为例：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，
5、4，2，3。计算出最短的加工时间34。【补充说明】由于此题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。思考2：任务j如果aj=bj在A车间的加工时间与其在B车间的加工时间一样的话，任务j的加工处理在任何时侯处理都一样，也就是说加工过程中如果我们在最优方案根底上，仅仅是调整任务j的加工顺序，如此将得到一个等效的加工方案。证明： 在的最优方案中，如果有任务i，并且Ai=Bi，如此如果改变其加工顺序。我们将得到一个等效的最优加工方案。根据以上特征，为了让输出解达到唯一，我们只有进而求其次，我在测试数据中修改了一下，将所有的测试数据
6、均改为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)d
7、iv 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
8、，最后输出加工时间总流程为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.t
9、ima)=(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. /
