独立任务最优调度（动态规划）

题目：

用两台处理机A和B处理n个作业。设A和B处理第k个作业的时间分别为ak和bk。由于各个作业的特点和机器性能的关系，对某些作业，在A上的处理时间长；而对另一些作业，在B上的处理时间更长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现在要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间和最少。

算法思路：

当完成k个作业时，设机器A花费了x时间，机器B花费时间的最小值肯定是x的一个函数。设F[k,x]表示完成k个作业且机器A花费x时间的条件下机器B所花费时间的最小值，那么F[k,x]=min{F[k−1,x]+bk,F[k−1,x−ak]}。其中F[k−1,x]+bk表示第k个作业由机器B来处理，完成前k−1个作业时机器A所花费的时间还是x。而F[k−1,x−ak]表示第k个作业由机器A来处理，此时完成前k−1个作业机器A花费的时间是x−ak。

    根据F的定义，我们知道F[n,x]表示完成n个作业且机器A花费x时间的条件下机器B所花费时间的最小值。显然，0≤x≤∑k=0nak，所以对于xi(区间[0,∑k=0nak]内的任一整数)，总有一个F[n,xi]与其对应，那么min{max{xi,F[n,xi]}}就是最后的结果。由于要处理每个作业k，并且处理每个作业k的时候都要循环∑j=0kaj次，所以算法的时间复杂度为O(n∑k=0nak)。

    考虑以下包含6个作业的例子，其中ak={2,5,7,10,5,2}，而bk={3,8,4,11,3,4}。下面对前两个作业进行简单的分析。

	作业1	作业2	作业3	作业4	作业5	作业6
处理机A	2	5	7	10	5	2
处理机B	3	8	4	11	3	4

（1）对于第一个作业，机器A所花费时间x的取值范围是0≤x≤a1。当x<0时，设F[1,x]=∞。x=0时，F[1,0]=3,此时max(0,F[1,0])=3，即机器A花费0时间，机器B花费3时间；x=1时，F[1,1]=3，max(1,F[1,1])=3；x=2时，F[1,2]=0，max(2,F[1,2])=2，此时作业1由机器A来处理，花费2时间，而机器B不处理作业。   

（2）对于第二个作业，x的取值范围是0≤x≤a1+a2。当x<0时，同样设F[2,x]=∞。

（3）下面是详细步骤：

x=0， F[2,0]=min{F[1,0]+b2,F[1,0−a2]}=min{3+8,∞}=11，所以max(0,11)=11；
    x=1，F[2,1]=min{F[1,1]+b2,F[1,1−a2]}=min{3+8,∞}=11，所以max(1,11)=11；
    x=2，F[2,2]=min{F[1,2]+b2,F[1,2−a2]}=min{0+8,∞}=8，所以max(2,8)=8；
    x=3，F[2,3]=min{F[1,3]+b2,F[1,3−a2]}=min{0+8,∞}=8，所以max(3,8)=8；
    x=4，F[2,4]=min{F[1,4]+b2,F[1,4−a2]}=min{0+8,∞}=8，所以max(4,8)=8；
    x=5，F[2,5]=min{F[1,5]+b2,F[1,5−a2]}=min{0+8,3}=3，所以max(5,3)=5；
    x=6，F[2,6]=min{F[1,6]+b2,F[1,6−a2]}=min{0+8,3}=3，所以max(6,3)=6；
    x=7，F[2,7]=min{F[1,7]+b2,F[1,7−a2]}=min{0+8,0}=0，所以max(7,0)=7；

依次类推

下面是代码的实现：

#include<iostream>
using namespace std;

void Read(int *a,int *b,int n)///输入对应的时间值
{
    cout<<"请输入机器A处理每个作业的时间：";
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cout<<endl<<"请输入机器B处理每个作业的时间：";
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
}

int min(int x, int y)
{
    return x < y ? x : y;
}

int max(int x, int y)
{
    return x > y ? x : y;
}

int dyna(int *a,int *b,int **F,int n,int *time)
{
    int sumA=a[1];///一开始的时间
    ///当k=1的时候
    for(int x=0;x<a[1];x++)///时间<a[1]时说明是b完成的
    {
     F[1][x]=b[1];///这里要注意
    }
    F[1][a[1]]=min(a[1],b[1]);///第一个要选择最小值来完成第一个工作

    ///此时需要进行初始化
    for(int i=2;i<=n;i++)
    {
      for(int j=0;j<=n;j++)
      {
          F[i][j]=100000000;
      }
    }
    ///当k=2时，
    for(int k=2;k<=n;k++)
    {
      sumA+=a[k];///时间的累加
       time[k]=100000000;
      for(int x=0;x<=sumA;x++)///注意是x
      {
            if(x<a[k])///说明第k个是b完成的，k-1是a完成的
            {
                F[k][x]=F[k-1][x]+b[k];
            }
            else///说明第k-1个是b完成的，第k个是a完成的
            {
                F[k][x]=min(F[k-1][x]+b[k],F[k-1][x-a[k]]);
            }
            time[k]=min(time[k],max(x,F[k][x]));
      }
    }
    return time[n];
}
int main()
{
    int n;
    cin>>n;

    int *a=new int[n];
    int *b=new int[n];
    int **F=new int *[n];
    int *time=new int[n];
    for(int i=1;i<=n;i++)
    {
        F[i]=new int[n*n];
    }
    Read(a,b,n);
    cout<<endl<<"输出独立任务最优调度的时间值为："<<dyna(a,b,F,n,time);
    return 0;
}

下面是运行结果如下：