独立任务最调度.doc

《独立任务最调度.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、参考资料1——独立任务最优调度问题：独立任务最优调度，又称双机调度问题：用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例：n=6a={2,5,7,10,5,2};b={3,8,4,11,3,4}.分析：当完成k个作业，设机器A花费了x时间，机器B所花费时间的最小值肯定是x的一个函数，设F[k][x]表

2、示机器B所花费时间的最小值（注意，这是B机器所花费的时间，即当B机器停机时的时间点）。则有F[k][x]=Min{F[k-1][x]+b[k],F[k-1][x-a[k]]}；其中，F[k-1][x]+b[k]表示第k个作业由机器B来处理（完成k-1个作业时机器A花费的时间仍是x，前提就是A机器停机的时间是x），F[k-1][x-a[k]]表示第k个作业由机器A处理（完成k-1个作业时机器A花费的时间是x-a[k]）。那么x（表示A机器的停机时间）、F[k][x]（表示B机器的停机时间）两者取最晚停机的时间，也就是两者中最大的时间，是在AB在此时间中完成k任务最终的时间

3、：Max(x,F[k][x])。而机器A花费的时间x在此期间是一个变量，其取值可以是即x=0,1,2……x(max)，（理论上x的取值是离散的，但为编程方便，设为整数连续的）由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。理解难点在于B是A的函数表达式，也即动态规划所在。花点时间，看懂表达式，加上思考，理解了这点一切OK，后面的编程实现完全依据这个思想。先用前两个任务的枚举示例来帮助理解。示例：前两个作业示例足矣。初始化第一个作业：下标以0开始。首先，机器A所花费时间的所有可能值范围：0<=x<=a[0].设x<0时，设F[0][x]=∞，

4、则max(x,∞)=∞；记法意义见下。x=0时，F[0][0]=3，则Max(0,3)=3，机器A花费0时间，机器B花费3时间，而此时两个机器所需时间为3；x=1时，F[0][1]=3，Max(1,3)=3；x=2时，F[0][2]=0，则Max(2,0)=2；那么上面的点对序列中，可以看出当x=2时，完成第一个作业两台机器花费最少的时间为2，此时机器A花费2时间，机器B花费0时间。来看第二个作业：首先，x的取值范围是：0<=x<=(a[0]+a[1]).当x<0时，记F[1][x]=∞；这个记法编程使用，因为数组下标不能小于0。在这里的实际含义是：x是代表完成前两个作

5、业机器A的时间，a[1]是机器A完成第2个作业的时间，若x

6、]=Min{F[0][3]+b[2],F[0][3-a[1]]}=Min{0+8,∞}=8，进而Max(3,8)=8；x=4，则F[1][4]=Min{F[0][4]+b[2],F[0][4-a[1]]}=Min{0+8,∞}=8，进而Max(4,8)=8；x=5，则F[1][5]=Min{F[0][5]+b[2],F[0][5-a[1]]}=Min{0+8,3}=3，进而Max(5,3)=5；x=6，则F[1][6]=Min{F[0][6]+b[2],F[0][6-a[1]]}=Min{0+8,3}=3，进而Max(6,3)=6；x=7，则F[1][7]=Min{F[

7、0][7]+b[2],F[0][7-a[1]]}=Min{0+8,0}=0，进而Max(7,0)=7；那么上面的点对序列中，可以看出当x=5时，完成两个作业两台机器花费最少的时间为5，此时机器A花费5时间，机器B花费3时间。程序代码如下：[csharp]viewplaincopyprint?1.usingSystem;2.namespacezydd3.{4.classProgram5.{6.//独立任务最优调度函数，参数为两组任务和任务个数，最优时间和顺序结果。7.staticvo