独立任务的最优调度问题（动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了独立任务的最优调度问题（动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述:

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai>bi，而对于某些j,j≠i，有aj>bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。

算法讲解：

一、首先，搞懂p是干嘛的，二维数组p存储的内容到底是什么

1、p数组的列坐标k记录n个作业，横坐标t是a机器单独处理所需要的时间 *

2、p数组元素值来记录加上b机器后，每次添加一个作业后，在a机器单独处理的每个时刻上加上b后的最优解

3、p数组是一列一列更新的，即每次增加一个作业，在不同的时间下，b机器的最优用时 *

二、所以每次更新的值就是两种情况：

1、新加入的k作业，当用时t<a[k]时，说明此时a机器根本无法处理k，只能是b来处理，所以就是直接更新p[t][k]的值为p[t][k-1]+b[k]; *

2、新加入的k作业，t>=a[k]时，此时a机器有直接处理k的能力，所以就要进行比较，比较的双方就是

(1)a不处理k，b接着在t时刻，k-1次作业后继续处理k(也就是情况1) p[t][k]=p[t][k-1]+b[k];

(2)a处理k，b此时的值就直接继承:a处理k用时后的剩余时间(t-a[k])，对应的前k-1个作业的用时 p[t][k]=p[t-a[k]][k-1]; *

三、动态更新完p数组之后，我们就得到了最后一列的值

1、横坐标t结合数组内元素值p[t][n]分别是t时间内a机器单独处理用时和b机器在a机器处理的基础上最优用时，说白了就是横坐标t就是a单独处理a的用时，p内值就是a、b并行工作后b的最优用时 2、分别比较每一行的两个数值，记录每一行的最大值，用一个变量min记录所有最大值的最小值，就得到了最优解

研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。

（给张图片，Excel搞的，没画完，只画了前三列，不过应该已经足够你理解了，竖着一列一列的画，最重要的还是搞懂p里面记录的到底是什么，横坐标t到底是什么）

独立任务最优调度问题,动态规划,算法

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define MAXTIME 500
int p[MAXTIME][MAXTIME];

int Dynamic(int a[],int b[],int n){
    int aTime = 0;//作业仅在机器a上运行是所需要的时间
    for(int k = 1;k<=n;k++){//从1开始，到n，方便操作
        aTime += a[k];//记录此时a机器单独操作需要的最大时间
        for(int t = 0;t<=aTime;t++){//一列一列的更新
            if(t<a[k]){//此时时间条件不允许a单独处理k
                p[t][k]=p[t][k-1]+b[k];//此处p元素值直接是b处理完k-1后继续处理k
            } else{//此时时间条件允许a处理新加入的k，进行比较
                p[t][k]=p[t-a[k]][k-1]>p[t][k-1]+b[k]?p[t][k-1]+b[k]:p[t-a[k]][k-1];
            }
        }
    }
    int minTime = 999999;
    for(int t = 0;t<aTime;t++){
        int maxt = max(t,p[t][n]);//找到每个时间段对应的两者的最大值
        minTime = minTime>maxt?maxt:minTime;//minTime每次更新，记录最小值
    }//说白了就是横坐标t就是a单独处理a的用时，p内值就是a、b并行工作后b的最优用时
    //在考虑到所有作业时，比较最后一列每一行两者的大小就能得到最优用时
    return minTime;
}
int main(){
    int n;//n个作业
    cin >> n; //读入作业个数
    int a[n+1];
    int b[n+1];
    for(int i=1;i<=n;i++)//读入机器A运行时间
        cin >> a[i];
    for(int i=1;i<=n;i++)//读入机器B运行时间
        cin >> b[i];
    int minTime = Dynamic(a,b,n);
    cout << minTime;
    return 0;
}
/*
 * 算法描述:
 * 一、首先，搞懂p是干嘛的，二维数组p存储的内容到底是什么
 * 1、p数组的列坐标k记录n个作业，横坐标t是a机器单独处理所需要的时间
 * 2、p数组元素值来记录加上b机器后，每次添加一个作业后，在a机器单独处理的每个时刻上加上b后的最优解
 * 3、p数组是一列一列更新的，即每次增加一个作业，在不同的时间下，b机器的最优用时
 * 二、所以每次更新的值就是两种情况：
 * 1、新加入的k作业，当用时t<a[k]时，说明此时a机器根本无法处理k，只能是b来处理，所以就是直接更新p[t][k]的值为p[t][k-1]+b[k];
 * 2、新加入的k作业，t>=a[k]时，此时a机器有直接处理k的能力，所以就要进行比较，比较的双方就是
 *   (1)a不处理k，b接着在t时刻，k-1次作业后继续处理k(也就是情况1)  p[t][k]=p[t][k-1]+b[k];
 *   (2)a处理k，b此时的值就直接继承:a处理k用时后的剩余时间(t-a[k])，对应的前k-1个作业的用时 p[t][k]=p[t-a[k]][k-1];
 * 三、动态更新完p数组之后，我们就得到了最后一列的值
 * 1、横坐标t结合数组内元素值p[t][n]分别是t时间内a机器单独处理用时 和b机器在a机器处理的基础上最优用时
 *    说白了就是横坐标t就是a单独处理a的用时，p内值就是a、b并行工作后b的最优用时
 * 2、分别比较每一行的两个数值，记录每一行的最大值，用一个变量min记录所有最大值的最小值，就得到了最优解
*/

运行结果如下：

独立任务最优调度问题,动态规划,算法