加工生产调度 pascal某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以

加工生产调度
源程序名 prod. (pas, c, cpp) 可执行文件名 prod.exe
输入文件名 prod.in 输出文件名 prod.out
【问题描述】
某工厂收到了n个产品的订单,这n个产品分别在A,B两个车间加工,并且必须先在A车间
加工后才可以到B车间加工.
某个产品i在A,B两车间加工的时间分别为Ai,Bi.怎样安排这n个产品的加工顺序,才能
使总的加工时间最短.这里所说的加工时间是指:从开始加工第一个产品到最后所有的
产品都已在A,B两车间加工完毕的时间.
【输入】
第一行仅—个数据n(0 接下来n个数据是表示这n个产品在A车间加工各自所要的时间(
都是整数).
最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数).
【输出】
第一行一个数据,表示最少的加工时间;
第二行是一种最小加工时间的加工顺序.
【样例】
prod.in prod.out
5 34
3 5 8 7 10 1 5 4 2 3
6 2 1 4 9
【算法分析】
本题是要求一个加工顺序使得总的加工时间最少,而要使加工时间最少,就是让各车间
的空闲时间最少.一旦A车间开始加工,便会不停地进行加工(我们不要去管车间是否能
够一直生产,因为他们有三班,可以24时间不停地运转).关键是B车间在生产的过程中,
有可能要等待A车间的初加工产品.很显然所安排的第一个产品在A车间加工时,B车间是
要等待的,最后一个产品在B车间加工时,A车间已经完成了任务.
要使总的空闲时间最少,就要把在A车间加工时间最短的部件优先加工,这样使得B车间
能以最快的速度开始加工;把放在B车间加工时间最短的产品放在最后加工,这样使得最
后A车间的空闲时间最少.
设计出这样的贪心法:
设Mi=min{Ai,Bi}
将M按照由小到大的顺序排序,然后从第一个开始处理,如果Mi=Ai,则将它安排在从头开
始的已经安排的生产顺序后面,如果Mi=Bi,则将它安排在从尾开始的已安排的生产顺序
前面.
这种安排是否是最少的加工时间,还要通过数学证明.证明如下:
设S= 图3-1是加工作业i时A车间等待B车间的情况:
图3-1 A等B的情况
图3-2是加工作业i时B车间等待A车间的情形:
图3-2 B等A的情况
假设最佳的方案中,先加工作业Ji,然后再加工作业Jj,则有:
如果,则
如果,则
如果,则
如果将作业Ji和作业Jj的加工顺序调整,则有:
其中,
按照上面的假设,有T=5,可以证明当将h拆分为两个不相同的部分并且两部分都大于1时
两部分的乘积大于h.证明如下:
将h分为两部分:a,h-a其中22*a*(a-1)-a*a=a*a-2*a=a*(a-2)
又因为a>=2,所以a*(a-2)>=0,所以a*(h-a)-h>O即a*(h-a)>h.
从上面的证明可以看出,对于指定的正整数,如果其大于等于5,将它拆分为不同的部分
后乘积变大,对于中间结果也是如此.因此可以将指定的n,依次拆成a1+a2+a3+a4+…
+am,乘积最大.
现在的问题是如何拆分才能保证n=a1+a2+a3+a4+…+am呢
可以先这样取:当和不足n时,a1取2,a2取3,…,am-1取m,即从2开始按照自然数的顺序取
数,最后剩余的数给am,如果am4)拆分成从2开始的连续的自然数的和,如果最后
有剩余的数,将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项.
基本算法描述如下:
(1)拆分过程
拆分的数a先取2;
当n>a时做
Begin
选择a作为一项;
a增加1;
n减少a;
End;
如果n>0,那么将n从最后一项开始平均分给各项;
如果n还大于0,再从最后一项开始分一次;
(2)求乘积
设置一个数组来存放乘积,初始状态位数为1,结果为1;
将上面拆分的各项依次跟数组各项相乘并考虑进位;