双机调度问题

95 阅读 0 评论 63 点赞

我是靠谱客的博主沉默柜子，最近开发中收集的这篇文章主要介绍双机调度问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近算法作业布置了一道双机调度问题，要求要用动态规划来做，看了答案还是不太懂，花了很长时间终于勉强懂了，因此直接记下。
嗯，看的是这个的代码，看代码终于看懂的，附上代码链接：
双机调度问题代码参考链接

题目：

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例：n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}.

思路

设对于前k个任务，机器a花费的时间为x，由于对于任何一个任务要么是机器a来完成，要么是机器B来完成，因此机器B花费的时间肯定是一个与x有关的函数，用f（k，x）表示完成前k个任务在机器A花费时间为x的基础上机器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个任务和前k个任务对于A机器来说用的时间都是一样的，也就是x时间完成，因此这里x不变。而f[k-1,x-a[k]]则表示这个任务是由机器A来完成，因此，完成任务k和任务k-1B机器所用的时间是相同的，但A机器在完成前k-1个任务时所用时间为x-a[k],因此完成前k个任务和k-1个任务时间相同应该表示为f[k,x]=f[k-1,x-a[k]]。

刚开始还有个疑问，机器B取得是最小值呀，那每一个任务机器B都不执行时间不就是最小的吗，这里需要注意机器A花费的时间X是一个尝试性的数据，也就是它是在变化的，x=0,1,2…,因此，在某个时间，对于前k个任务，在这个规定的时间x下，机器A只能执行i个任务，则剩下的A不能执行的就只能全部强迫给B执行，因此，在被强迫的情况下，B也尽量去选一个对自己优势最大的。
这个题说了半天，其实想通了也不是太难，就和0/1背包问题差不多（如果对0
/1背包问题没有问题的话），0/1背包问题的动态规划是要把容量weight和物品总数n一起建立一个n*weight的表格，然后通过循环计算更新表中数据并在val[n-1][weight]处得到价值最大的值，而这里与0/1背包问题唯一的区别是对于n个任务，如果完全由机器A完成需要花费的时间是sum，而对于前k个任务，完全由机器A完成所需要花费的时间为k_sum,这我们在进行for（k=1to n）的任务循环进行填表时不需要完全填到sum，而是只需要填到前k个任务完全由A完成所需花费的时间k_sum即可。
然后循环到最后一个任务的时候，对于x从0到k_sum的循环从max（f[k,x],x）里选出的最小值就是本题的答案。

代码

这里只展示核心代码，完整的代码参考链接
https://www.cnblogs.com/chuaner/p/11776669.html

//注意代码用的是别人的代码
int get_result(int a[],int b[], int n){
	if(n==1)return min(a[0], b[0]);
	int sum=0, result = 10000;
	for(int i = 0;i < n;i++)sum += a[i];
	int f[n][sum+1];
	//初始化f的各个元素为0 
	memset(f, 0, sizeof(f));
	
	//初始化完成第一个任务时的情况
	for(int x = 0;x < a[0];x++)f[0][x] = b[0];
	f[0][a[0]] = 0; 
	
	//这里开始动规的过程
	sum = a[0];
	for(int k = 1;k < n;k++){
		sum += a[k];
		for(int x = 0;x <= sum;x++){
			//处理x<0时设为无穷大的情况 
			if(x-a[k] < 0){
				f[k][x] = f[k-1][x]+b[k];
			}
			else
				f[k][x] = min(f[k-1][x-a[k]], f[k-1][x]+b[k]);
			if(k == n-1){
				int val = max(x, f[k][x]);
				if(val < result)result = val;
			}
			
		}
	}
	return result; 
}