动态规划 独立任务最优调度问题详解

问题描述

用2台处理机A和B处理n个作业。
设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai>=bi，而对于某些j,j≠i，有aj<bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。
设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。
研究一个实例： (a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。 对于给定的2 台处理机A 和B处理n 个作业，找出一个最优调度方案，使2台机器处理完这n 个作业的时间最短。

本文给出了三种解法，分别需要使用三维数组、二维数组、一维数组。代码在文章最后

分析

本问题乍一看似乎与动态规划没有什么关系。但是，我们可以注意到下面几点：

1. 每个任务仅有两个选择：由A处理，或者由B处理。我们的目标是合理安排每个任务由哪个机器处理，从而找到最短的处理完所有任务的时间。
2. 所有任务都是需要被处理的。这也就意味着，每个任务的处理顺序是无关紧要的。所以，为讨论的简单起见，我们可以从第一个任务开始，按顺序决定每个任务由哪个机器处理，直到处理完所有的任务。下文所有讨论都是按照顺序处理任务。

由以上分析，我们至少可以想到一种解决问题的办法：穷举法。对于每个任务，都有两种选择，所以n个任务共2ⁿ种选择。我们可以穷举出这2ⁿ种情况，计算每种情况花费的时间，并选择出时间最短的那一种。

这种方法一定可以找到最优解，但是单单考虑到任务分配便有2^n种情况，再考虑到每种情况计算时间的过程，复杂度过高，算法无效。

动态规划解法

简单的动态规划思路

上面的穷举法的思想是将任务当作自变量，完成时间当作因变量，复杂度下限为 O(2^n)。

但是，我们可以注意到：完成任务最慢的情况，是把所有任务都交给一台机器完成，另一台机器全程闲置。但是，即使在这种情况下，也是可以在有限时间内完成任务的。设sum_a=a[0]+a[1]+···+a[n-1]，sum_b=b[0]+b[1]+···+b[n]，设max_sum_ab=max(sum_a,sum_b)，易知，待求的最短时间一定不超过max_sum_ab。

由以上分析，我们可以引出动态规划解法的思路。设布尔量p[i][j][k]表示前k个作业是否可以在处理机A用时不超过i且处理机B用时不超过j时间内完成。由上述分析，我们可以知道：当i>=sum_a，或者j>=sum_b时，p[i][j][k]一定为真。那么我们可以使用穷举法，将机器A、B花费的时间分别从0枚举至sum_a和sum_b，对于每种情况，都求出p的bool值，再从中选择出最短时间即可。

这里对p的定义进行一些补充。已经清楚的朋友可以跳过下面这一段。

• p[i][j][k]是一个bool值，其真假表示a机器花费i时间、b机器花费j时间的前提下，是否可以完成k个任务。我们这里假设任务都是按顺序处理。也就是说，假设机器A花费时间i、机器B花费时间j，若可以在此时间内完成至任务k，那么p[i][j][k]=true，否则为false。

  举个例子理解一下：

• 假设一共有两个任务，花费时间如上。由以上表格可知：p[7][0][2]=true。因为，若把所有任务都给A机器，那么A机器时间消耗为7，B机器时间消耗为0，完成任务数为2，即p[7][0][2]=true。
• 同时，p[4][2][2]=true。把任务1给B，任务2给A，恰好A机器时间花费为4，B机器时间花费为2，此时两个任务都可以完成。
• 以此类推，p[3][2][2]=false，因为当机器A花费时间不超过3并且B不超过2时，显然是无法完成两个任务的。

递推关系

到这里，动态规划的基本思想已经解释清楚了。接下来的关键就是如何将p[0..sum_a][0..sum_b][0..n]全部求出来。

实际上，第k个任务和第k-1个任务有密不可分的关系。假设p[0..sum_a][0..sum_b][0..k-1]已经全部求解完毕。那么完成第k件任务有两个选择：分配给A机器，或者B机器。假设A花费i时间、B花费j时间，可以完成任务k-1，那么A花费i+ak时间、B花费j时间，一定可以完成任务k。同样的，若A花费i时间、B花费j+bk时间，也一定可以完成任务k。因为这就相当于将k分别交给A或者B完成。

将上面的关系写成以p表示的形式，即p[i][j][k]=p[i-ak][j][k-1] || p[i][j-bk][k-1]。解释如下：p[i][j][k]=true，表示完成k个任务，a、b机器使用的时间分别不超过i、j。那么我们可以推知：p[i-ak][j][k-1] 和 p[i][j-bk][k-1]中必有一个为true。因为：在完成第k-1个任务后，第k个任务要不是A机器处理，要不是B机器处理，分别对应着 p[i-ak+ak][j][k-1+1]和p[i][j-bk+bk][k-1+1]。所以，p[i][j][k]=p[i-ak][j][k-1] || p[i][j-bk][k-1]。

最后，求得所有p的值后，我们找到所有值为true的p，选出min(max(i,j))即为问题的解。先取max，是因为最终结果取决于A和B中花费时间较长的那一个。再取min，是因为我们要在所有能够完成任务的(i,j)组合中寻出最小值。

主要代码如下：

const int get_min_time_dyna_3d()	//使用三维数组
{
	·····   //这里是部分初始化操作

	for (k = 1; k <= n; k++) {  //每次循环，安排一件任务
		for (i = 0; i <= mn; i++) { //a机器的时间从0~mn逐步尝试
			for (j = 0; j <= mn; j++) {
				if (i - a[k - 1] >= 0)  //若当前任务可以由a机器在i时间内完成
					p[i][j][k] = p[i - a[k - 1]][j][k - 1];
				if (j - b[k - 1] >= 0)  //若当前任务可以由b机器在j时间内完成
					p[i][j][k] = p[i][j][k] || p[i][j - b[k - 1]][k - 1];
			}
		}
	}

	····	//遍历p，在p为true的前提下选出 ret=min(max(i,j))

	return ret;

}

算法复杂度分析

上述算法的时间复杂性主要在三重循环上。时间复杂度为 O(m²n³)。

同时，该算法空间复杂度也较高，主要空间花费在p数组上，复杂度为 O(m²n³)。

虽然复杂度高，但是相比穷举法的 O(2ⁿ) 已经降下了很多。

算法改进

上述算法使用了三维数组，空间复杂度高。我们考虑可否对其进行优化：

可以想象：当i和k不变时，p[i][j][k]的bool值对于j有一个临界值j0。当j<j0时，p[i][j][k]=false；当j>=j0时，p[i][j][k]=true。

所以，我们可以将三维数组改为二维数组 p[i][k]=int，表示a机器花费不超过i时间且能够完成k个任务时，b机器花费时间的最小值。也就是上面说到的j0。

算法改进的思想已经介绍完毕。那么，要怎么求出p[0..sum_a][0..n]的值呢？我们还是可以这样考虑：假设p[0..sum_a][0..k-1]已经全部求解完毕（注意这里的p[i][k]的值表示的是B机器花费的最少时间）。那么完成第k件任务有两个选择：分配给A机器，或者B机器。若我们把任务k分配给A机器，那么p[i][k]=p[i-ak][k-1]，因为这个任务是由A完成的，所以B花费的最短时间同上次没有变化。若分配给B机器，那么p[i][k]=p[i][k-1]+bk，将B花费的最短时间加上了完成任务k的时间。

究竟是选A还是选B呢？我们的目的是在p中存储B花费时间的最小值。这样的话，递推方程就变为：p[i][k]=min(p[i-ak][k-1],p[i][k-1]+bk)。

改进后的代码如下：

const int get_min_time_dyna_2d()
{
	···		//初始化操作。注意需要将p数组全部置0

	for (k = 1, sum_a = 0; k <= n; k++) {
		//k表示当前完成到第几个任务。作下标使用需要-1
		sum_a += a[k - 1];	//每次迭代，A机器最长时间不超过a1+a2+···+ak
		for (i = 0; i < sum_a; i++) {	//i=sum_a时不用算，因为p一定是0
			p[i][k] = p[i][k - 1] + b[k - 1];
			if (i >= a[k - 1])
				p[i][k] = p[i][k] < p[i - a[k - 1]][k - 1] ? 
						p[i][k] : p[i - a[k - 1]][k - 1];
		}
	}

	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
		//遍历p，选出 ret=min(max(i,j))
		int max_ij = i > p[i] ? i : p[i];
		if (max_ij < ret)
			ret = max_ij;
	}
	····	//内存释放等操作

	return ret;
}

再次改进算法

观察上述改进后的算法可知，虽然p数组记录了 p[0..sum_a][0..n]，但是最终使用到的仅有 p[0..sum_a][n]。因此，我们可以进一步改进算法，使用一维数组p[i]=j来记录完成所有任务且A机器花费不超过i时间的情况下，B机器花费时间的最小值。

算法的思想与二维数组完全一致，但是由于p数组的值不断更新，循环的前期其实p记录的并不是完成所有任务的时间，所以代码可读性变差。这里不再对其进行解释，仅将代码附在文末。

代码

#include <iostream>
#include<string.h>
using namespace std;

const int INTMAX = 0x7fffffff;

int n;
int* a, * b;

const int get_min_time_dyna_1d()
{
	const int n = ::n;		//防止求解过程中修改n、a、b
	const int* a = ::a;
	const int* b = ::b;

	int i, k;
	int* p;	//p[i]=j表示所有任务由a完成不超过i时间，由b完成不超过j时间
	int ret;

	int sum_a = 0, sum_b = 0;	//存储任务完全由a/b机器完成所需要花费的时间
	for (i = 0; i < n; i++) {
		sum_a += a[i];
		sum_b += b[i];
	}

	try {
		p = new int[sum_a + 1];
	}
	catch (const std::exception& e) {
		cerr << "内存申请失败！" << e.what() << endl;
		return -1;
	}

	for (i = 0; i <= sum_a; i++)
		p[i] = 0;		//初始化，假设任务全由a完成

	for (k = 0; k < n; k++) {	//每次循环完成一件任务
		for (i = sum_a; i >= 0; i--) {	//初始化时，任务全由a完成
			p[i] = p[i] + b[k];	//初始化，把任务k派给b机器
			if (i >= a[k])	//如果a机器在i时间也可以完成任务k
				p[i] = p[i] < p[i - a[k]] ? p[i] : p[i - a[k]];
		}
	}

	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
		int temp = i > p[i] ? i : p[i];
		if (temp < ret)
			ret = temp;
	}

	delete[]p;
	return ret;
}

const int get_min_time_dyna_2d()
{
	const int n = ::n;
	const int* a = ::a;
	const int* b = ::b;

	int i, k;
	int** p;	//p[i]=j表示所有任务由a完成不超过i时间，由b完成不超过j时间
	int ret;

	int sum_a = 0;	//存储任务完全由a机器完成所需要花费的时间
	for (i = 0; i < n; i++)
		sum_a += a[i];

	const int total_sum_a = sum_a;	//记录a的任务时间总和

	try {
		p = new int* [total_sum_a + 1];
		for (i = 0; i <= total_sum_a; i++) {
			p[i] = new int[n + 1];
			memset(p[i], 0, (n + 1) * sizeof(int));	//初始全部置0
		}
	}
	catch (const std::exception& e) {
		cerr << "内存申请失败！" << e.what() << endl;
		return -1;
	}

	for (k = 1, sum_a = 0; k <= n; k++) {
		//k表示当前完成到第几个任务。作下标使用需要-1
		sum_a += a[k - 1];

		for (i = 0; i < sum_a; i++) {	//i=sum_a时不用算，因为p一定是0
			p[i][k] = p[i][k - 1] + b[k - 1];
			if (i >= a[k - 1])
				p[i][k] = p[i][k] < p[i - a[k - 1]][k - 1] ? p[i][k] : p[i - a[k - 1]][k - 1];
		}
	}

	for (i = 0, ret = INTMAX; i <= total_sum_a; i++) {
		int max_ij = i > p[i][n] ? i : p[i][n];
		if (max_ij < ret)
			ret = max_ij;
	}

	for (i = 0; i <= total_sum_a; i++)
		delete[]p[i];
	delete[]p;
	return ret;
}

const int get_min_time_dyna_3d()
{
	const int n = ::n;
	const int* a = ::a;
	const int* b = ::b;

	int i, j, k;
	bool*** p;

	int sum_a = 0, sum_b = 0;	//存储任务完全由a/b机器完成所需要花费的时间
	for (i = 0; i < n; i++) {
		sum_a += a[i];
		sum_b += b[i];
	}

	int ret;

	try {
		p = new bool** [sum_a + 1];
		for (i = 0; i <= sum_a; i++)
			p[i] = new bool* [sum_b + 1];
		for (i = 0; i <= sum_a; i++)
			for (j = 0; j <= sum_b; j++)
				p[i][j] = new bool[n + 1];
	}
	catch (const std::exception& e) {
		cerr << "内存申请失败！" << e.what() << endl;
		return -1;
	}

	for (i = 0; i <= sum_a; i++) {
		for (j = 0; j <= sum_b; j++) {
			p[i][j][0] = true;
			for (k = 1; k <= n; k++)
				p[i][j][k] = false;
		}
	}

	for (k = 1; k <= n; k++) {
		for (i = 0; i <= sum_a; i++) {
			for (j = 0; j <= sum_b; j++) {
				if (i - a[k - 1] >= 0)
					p[i][j][k] = p[i - a[k - 1]][j][k - 1];
				if (j - b[k - 1] >= 0)
					p[i][j][k] = p[i][j][k] || p[i][j - b[k - 1]][k - 1];
			}
		}
	}

	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
		for (j = 0; j <= sum_b; j++) {
			if (p[i][j][n]) {
				int tmp = (i > j) ? i : j;
				if (tmp < ret)
					ret = tmp;
			}
		}
	}

	for (i = 0; i <= sum_a; i++) {
		for (j = 0; j <= sum_b; j++)
			delete[] p[i][j];
		delete[]p[i];
	}
	delete[]p;

	return ret;

}

int main()
{
	cin >> n;

	try {
		a = new int[n];
		b = new int[n];
	}
	catch (const std::exception& e) {
		cerr << "内存申请失败！" << e.what() << endl;
		return -1;
	}

	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cin >> b[i];

	cout << get_min_time_dyna_1d() << endl;

	delete[]a;
	delete[]b;

	return 0;
}