多机调度问题.cpp

贪心算法解一系列算法经典问题

/*多机调度问题

【问题描述】
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。

【实现提示】
1、把作业按加工所需时间从大到小排序
2、如果作业数目比机器的数目少或相等，则直接把作业分配下去
3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，下面的作业分配时，是选那个表头上S最小的链表加入新作业。*/

#include <stdio.h>
#define SIZE 20

void Greedy(int p[],int t[]);
void Sort(int a[],int b[]);
int Minimum(int a[]);

void main()
{
	int i,p[n],t[n]={2,14,4,16,6,5,3};
	printf("\nPi:");
	for(i=0; i<n; i++)
	{
		p[i]=i+1;
		printf("\t%d",p[i]);
	}
	printf("\nTi:");
	for(i=0; i<n; i++) printf("\t%d",t[i]);
	printf("\n\n");
	Greedy(p,t);
	printf("\n");
}

// 多机调度算法
void Greedy(int p[],int t[])
{
	if(n<=m)
	{
		printf("为每个作业分配一台机器.\n");
		return;
	}
	Sort(t,p);	//依据ti降序排列

	//分配作业
	int i,j,k,S[n]={0},M[m][n]={0};
	for(i=0; i<n; i++)
	{
		k=Minimum(S);	//找机器中作业量最小者
		for(j=0; M[k][j]>0; j++);
		M[k][j]=p[i];	//第k台机器第j个作业
		S[k]+=t[i];	//第k台机器作业量累计
	}

	//输出分配结果
	for(i=0; i<m; i++)
	{
		printf("M%d: (%d)",i+1,S[i]);
		for(j=0; M[i][j]>0; j++) printf("\t%d",M[i][j]);
		printf("\n");
	}
}

// 对a从大到小排序，同时调整b
void Sort(int a[],int b[])
{
	int change,temp,N=n;
	while(N>0)
	{
		change=0;
		for(int j=0; j<N-1; ++j)
			if(a[j+1]>a[j])
			{ 
				change=j+1;
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				temp=b[j];
				b[j]=b[j+1];
				b[j+1]=temp;
			}
			N=change;
	}
}

// 找机器中作业量a的最小者
int Minimum(int a[])
{
	int i,k=0,x=a[0];
	for(i=1; i<m; i++)
		if(a[i]<x)
		{
			x=a[i];
			k=i;
		}
	return k;
}