贪心算法解决多机调度问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了贪心算法解决多机调度问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题描述

设有N个独立的作业{1,2,...,n},由M台相同的机器进行加工处理。作业i所需时间为Ti.约定：任何作业可以在任何一台机器上加工，处理单位完工前不允许中断处理，人和作业不能拆分成更小的作业。要求给出一种作业调度方案，使所给的N个作业，在尽可能短的时间内有M台机器加工处理完成。

要求：随机生成N个作业相关信息，并计算由M台机器处理的最短时间

二、算法选择与分析

用贪心算法解决多机调度问题。

贪心算法只考虑眼前利益，不通盘考虑问题的所有可能，每一步做出当时看起来最佳的选择（局部最优选择）利用贪心算法求解的问题往往具有两个重要的特性，贪心选择性质和最优子结构性质。如果满足这两个性质，就可以使用贪心算法了。

所谓贪心选择，是指原问题的整体最优解，可以通过一系列局部最优的选择得到应用。同一规则，将原问题变为一个相似的，但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于自己做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题，在程序的运用过程中无回溯过程。

最优子结构，当一个问题的最优解包含其子问题的最优解释，称此问题具有最优子结构性质问题的最优子结构性质，是该问题是否可用贪心算法求解的关键。

三、设计思路

作业项数为你n，机器数为m。若n<=m，则一台机器随机分配一项作业，最长作业时间为机器所用最少时间。若n>m，则使用贪心算法寻求最佳解决方案，如下：

假设：一共有七项作业，解决时间分别为{5,4,16,14,3,2,6} 一共有三台机器，M1，M2，M3

首先，按照作业完成时间将作业从大到小排序，为{16,14,6,5,4,3,2}然后分别将16，14，6安排在M1，M2，M3三台机器上，然后进行比较。16，14，6中6最小，所以将下一项作业5安排在M3机器上。5+6=11。再次将更新后的三台机器进行比较并决出最小项，依此类推。

贪心算法解决多机调度问题

四、代码实现文章来源地址https://www.toymoban.com/news/detail-505969.html

#include<iostream> 
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
 
using namespace std;
#define N 1000
#define M 3 
int s[M] = { 0, 0, 0 };
 
 
//求出目前处理作业的时间和 最小的机器号 
int min(int m){
int min = 0;
int i;
for (i = 1; i<m; i++){
if (s[min]>s[i]){
min = i;
}
}
return min;
}
//求最终结果（最长处理时间） 
int max(int s[], int num){
int max = s[0];
for (int i = 1; i<num; i++){
if (max<s[i])
max = s[i];
}
return max;
}
//机器数大于待分配作业数 
int setwork1(int t[], int n){
int i = 0;
for (; i<n; i++){
s[i] = t[i];
}
int ma = max(s, N);
return ma;
}
//机器数小于待分配作业数 
int setwork2(int t[], int n){
int i;
int mi = 0;
for (i = 0; i<n; i++){
mi = min(M);
printf("\n") ;
cout << "接下来由" << mi+1 << "号机器处理任务" << i + 1 << endl;
s[mi] = s[mi] + t[i];
}
int ma = max(s, M);
return ma;
}
int main()  //DEV中是int,vc++6.0中是void
{
	//随机生成处理时间 
	int i;
	int t[N];
	srand((unsigned)time(NULL));
	for(i = 0;i<N;i++)
	{
  		t[i] =rand()%100+1;
  		printf("%d   ",t[i]);
	}	
	

		
		
	//int t[N] = { 16, 14, 6, 5, 4, 3, 2 };//处理时间按从大到小排序 
	int maxtime;
	if (M >= N)
		maxtime = setwork1(t, N);
	else
		maxtime = setwork2(t, N);
	printf("%d台机器中",M);
	cout << "最多耗费时间为：" << maxtime << endl;
	printf("由%d台机器",M);
	cout << "处理的最短时间为：" << maxtime << endl;
	
}

到了这里，关于贪心算法解决多机调度问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！