机器调度.cpp

机器调度是指有m台机器要处理n个作业

#include <stdio.h>
#include <malloc.h>
#define     MAXTASK		100
#define		MAXMACH		100
#define		LT(A,B)  ((A) < (B))
#define		EQ(A,B)  ((A) == (B))
#define		LQ(A,B)  ((A) <= (B)) 
#define		GT(A,B)	 ((A) >  (B))

typedef	struct{        //任务所需时间
	int ti;
	int num;
}TaskType;

typedef struct{			//分配给机器的时刻
	int sch;
	int num;
}MachType;

typedef	struct{			//任务的数据结构
	int		tasknum;
	TaskType	*task;
}HeapType;

typedef struct{			//机器的数据结构
	int		machnum;
	MachType	*machine;
}BitType;


void HeapAdjust (HeapType &H,int s,int m){
//已经H.task[s..m]中记录的时间除H.task[s].ti之外均满足堆的定义,本函数调整H.task[s]
//的时间,使H.task[s..m]成为一个大顶堆
	TaskType rc;
	int	j;
	rc=H.task[s];
	for(j=2*s; j<=m; j*=2){//沿ti较大的孩子结点向下筛选
		if( j<m && LT(H.task[j].ti,H.task[j+1].ti) )	++j;//j为ti较大的记录的下标
		if( !LT(rc.ti,H.task[j].ti) )	break;				//rc应插入在位置s上
		H.task[s]=H.task[j];
		s=j;
	}
	H.task[s]=rc;     //插入
}

void BitAdjust (BitType &B,int s,int m){
	//已经B.machine[s..m]中记录的时间除B.machine[s].sch之外均满足堆的定义,本函数调整B.machine[s]
	//的时间,使B.machine[s..m]成为一个小顶堆
	MachType rc;
	int j;
	rc=B.machine[s];
	for(j=2*s;j<=m;j*=2){//沿sch较小的孩子结点向下筛选
		if(j<m && GT(B.machine[j].sch , B.machine[j+1].sch))  ++j;
		if(LT(rc.sch, B.machine[j].sch))	break;
		B.machine[s]=B.machine[j];
		s=j;
	}
	B.machine[s]=rc;
}
void Heap(BitType &B,int s,int m){
	MachType rc;
	int	j;
	rc=B.machine[s];
	for(j=2*s; j<=m; j*=2){//沿ti较大的孩子结点向下筛选
		if( j<m && LT(B.machine[j].sch,B.machine[j+1].sch) )	++j;//j为ti较大的记录的下标
		if( !LT(rc.sch,B.machine[j].sch) )	break;				//rc应插入在位置s上
		B.machine[s]=B.machine[j];
		s=j;
	}
	B.machine[s]=rc;     //插入
}

void HeapSort( HeapType &H){
	int i;
	for( i=H.tasknum/2 ; i>0 ; --i) //把H.task[1..H.tasknum]建成大顶堆
		HeapAdjust(H,i,H.tasknum);
}
void BitSort( BitType &B){
	int i;
	for(i=B.machnum/2 ;i>0 ; --i)  //把B.task[1..B.tasknum]建成小顶堆
		BitAdjust(B,i,B.machnum);
}

int	LPT(HeapType &H,BitType &B){
//任务调度算法
	int i,j;
	int machine[MAXTASK][MAXMACH];//machine[i]为第i台机器被分配的任务
	for(i=0;i<=B.machnum;i++)     //初始化数组machine
		for(j=0;j<=H.tasknum;j++)
			machine[i][j]=0;
	if(H.tasknum <= B.machnum){
	//作业数n<=机器数m,则将作业i分配到机器i上
	//最短调度长度等于n个作业中处理时间最大值
		for(i=1;i<=H.tasknum;i++){
			B.machine[i].sch=H.task[i].ti;
			machine[i][0]=H.task[i].num;
		}
		B.machine[0].sch=B.machine[1].sch;
		for(i=2;i<=H.tasknum;i++){// 查找其中的最大值
			if(GT(B.machine[i].sch,B.machine[0].sch))
				B.machine[0].sch=B.machine[i].sch;
		}
		B.machine[1].sch=B.machine[0].sch;
	}
	else {
		for(i=H.tasknum;i>=1;--i){//分配任务
			HeapSort(H);//把任务按时间排成大顶堆
			BitSort(B); //把机器按时刻表排成小顶堆
			B.machine[1].sch=B.machine[1].sch+H.task[1].ti;//将H的堆顶任务分配给B的堆顶机器
			for(j=0;machine[B.machine[1].num][j];j++) ;
			machine[B.machine[1].num][j]=H.task[1].num;
			H.task[1]=H.task[i];//把排在最后的任务置堆顶(即把堆顶任务删除)
			H.task[i].ti=0;
			H.tasknum--;//任务数少一
		}
		for(i=B.machnum/2;i>=1;i--)//任务全部分配完时,再一次大顶堆排序
			Heap(B,i,B.machnum);
	}
	printf("scheme dispather:\n");
	printf("machine\t\ttask\n");
	for(i=1;i<=B.machnum && machine[i][0];i++){
		printf("NO.%d:   \t",i);
		for(j=0;machine[i][j];j++)
			printf("%d  ",machine[i][j]);
		printf("\n");
	}
	return B.machine[1].sch;
}

void main(){
	HeapType H;
	BitType  B;
	printf("input the amount of machines:");
	scanf("%d",&B.machnum);
	fflush(stdin);
	B.machine=(MachType *)malloc((B.machnum+1) * sizeof(MachType));
	for(int i=1;i<=B.machnum;i++){
		B.machine[i].sch=0; //初始化机器的时刻
		B.machine[i].num=i;
	}
	printf("input the amount of tasks:");
	scanf("%d",&H.tasknum);
	fflush(stdin);
	H.task=(TaskType *)malloc((H.tasknum+1)*sizeof(TaskType));
	for(i=1;i<=H.tasknum;i++){
		H.task[i].num=i;
		printf("NO.%d task:",i);
		scanf("%d",&H.task[i].ti);
	}
	printf("\n");
	printf("the least time of the job scheduling:%d\n",LPT(H,B));
	fflush(stdin);
	getchar();
}