#include
#define?N?10???//限定機器數(shù)和作業(yè)數(shù)不超過N個，這里N取10?
using?namespace?std;
?
struct?MachineNode?
{???
	int?ID;?????//機器號???
	int?avail;?//機器可用時間?
};??
struct?JobNode
{???
	int?ID;?????//作業(yè)號?
	int?time;?//處理時間?
};??

//建立大根堆??
void?SiftD（JobNode?r[]int?kint?m）?
{???
	int?ij;??
	i=k;?
	j=2*i;??
	while（j<=m）
	{??
		if（j		if（r[i].time>r[j].time）break;??
		else??
		{????
			int?temp1temp2;??
			temp1=r[i].time;
			r[i].time=r[j].time;
			r[j].time=temp1;
			temp2=r[i].ID;
			r[i].ID=r[j].ID;?
			r[j].ID=temp2;???
		}??
	}?
}?

?void?HeapSortD（JobNode?r[]int?n）?
?{??
	?for（int?i=n/2;i>=1;i--）?
		?SiftD（rin）;?
?}
?
//建立小根堆??
void?SiftX（MachineNode?r[]int?kint?m）?
?{???
	?int?ij;??
	?i=k;??
	?j=2*i;???
	?while（j<=m）?
	?{???
		?if（jr[j+1].avail）j++;??
		?if（r[i].avail		?else???
		?{?????
			?int?temp1temp2;??
			?temp1=r[i].avail;??
			?r[i].avail=r[j].avail;??
			?r[j].avail=temp1;???
			?temp2=r[i].ID;???
			?r[i].ID=r[j].ID;???
			?r[j].ID=temp2;???
		?}?
	?}?
}??

void?HeapSortX（MachineNode?r[]int?n）
?{???
	?for（int?i=n/2;i>=1;i--）???
		?SiftX（rin）;?
?}?

//完成任務(wù)分配
void?assign（MachineNode?M[]JobNode?J[]int?mint?j）??
?{???
	if（m>=j）???//如果機器數(shù)m大于或等于作業(yè)數(shù)j??
	{???
		printf（“工作數(shù)和機器數(shù)相同一臺機器完成一個作業(yè)\n“）;???
		HeapSortD（Jj）;???//以各作業(yè)所需時間建立大根堆，堆頂元素即為最大耗時的作業(yè)?????
		printf（“最大工作時間為:%d\n“J[1].time）;??//最大工作時間即為最大耗時的作業(yè)的所需時間?
	}???
	else??//如果機器數(shù)m小于作業(yè)數(shù)j??
	{????
		for（int?i=1;i<=m;i++）?//先為每臺機器分配一個作業(yè)，先把所需時間最大的m個作業(yè)分配給m臺機器。????
		{
			HeapSortD（Jj）;??//建立大根堆求堆頂元素確定其中耗時最大的作業(yè)??
			M[i].avail=J[1].time;??//機器i的處理時間即為作業(yè)的所需時間???
			printf（“機器%d完成作業(yè)%d時間從0到%d\n“M[i].IDJ[1].IDM[i].avail）;???
			for（int?k=1;k				J[k]=J[k+1];???
			j=j-1;???
		}???
		for（int?q=j;j>=1;q--）?//把剩余的j-m個作業(yè)分配下去（j=j-m）??
		{???
			HeapSortX（Mm）;??//將m機器個機器按可用時建立小根堆??
			HeapSortD（Jj）;??//將j個作業(yè)按處理時間建立大根堆???
			printf（“機器%d完成作業(yè)%d時間從%d到%d\n“M[1].IDJ[1].IDM[1].availM[1].avail+J[1].time）;??//將大根堆的堆頂作業(yè)分配給小根堆的堆頂機器???
			M[1].avail+=J[1].time;?//將小根堆的堆頂機器加上大根堆的堆頂作業(yè)的處理時間，重新插入小根堆（循環(huán)執(zhí)行HeapSortX（Mm）時完成）
			for（int?k=1;k				J[k]=J[k+1];???
			j=j-1;??
		}??
		printf（“最短調(diào)度時間為：%d\n“M[1].avail）;??//小根堆的堆頂元素就是最短調(diào)用時間???
	}
?}

void?main（）?
{???
	int?j=0;????//作業(yè)個數(shù)??
	int?m=0;?//機器個數(shù)??
	int?i;??
	MachineNode?M[N];?????//機器的結(jié)構(gòu)體數(shù)組??
	JobNode?J[N];?????????//作業(yè)的結(jié)構(gòu)體數(shù)組
	printf（“********************機器調(diào)度問題*********************\n“）;
	printf（“請輸入作業(yè)個數(shù)：“）;??
	scanf（“%d“&j）;???
	printf（“請輸入%d個作業(yè)需要的處理時間（空格隔開）\n“j）;??
	for（i=1;i<=j;i++）??????????????
	{???
		J[i].ID=i;??????????????????????????????????????//為每個作業(yè)確定序號??
		scanf（“%d“&J[i].time）;
	}???
	printf（“請輸入機器的個數(shù)：“）;??
	scanf（“%d“&m）;??
	for（i=1;i<=m;i++）???
		M[i].ID=i;??????//為每臺機器確定序號?
	printf（“\n調(diào)度工作為：\n“）;
	assign（MJmj）;????//調(diào)用完成分配任務(wù)的函數(shù)?
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3430??2018-01-11?23:55??6機器調(diào)度問題\6.cpp

?????文件???????4350??2018-01-11?01:31??6機器調(diào)度問題\6機器調(diào)度問題.dsp

?????文件????????912??2018-01-11?23:56??6機器調(diào)度問題\6機器調(diào)度問題.plg

?????文件???????7047??2018-04-29?14:51??6機器調(diào)度問題\6機器調(diào)度問題.vcxproj

?????文件????????897??2018-01-20?18:36??6機器調(diào)度問題\6機器調(diào)度問題.vcxproj.filters

?????文件????????143??2018-01-11?23:15??6機器調(diào)度問題\6機器調(diào)度問題.vcxproj.user

?????文件??????19272??2018-01-11?23:56??6機器調(diào)度問題\Debug\6.obj

?????文件?????233581??2018-01-11?23:56??6機器調(diào)度問題\Debug\6機器調(diào)度問題.exe

?????文件?????356080??2018-01-11?23:56??6機器調(diào)度問題\Debug\6機器調(diào)度問題.ilk

?????文件?????123904??2018-01-11?23:56??6機器調(diào)度問題\Debug\vc60.idb

?????文件?????110592??2018-01-11?23:55??6機器調(diào)度問題\Debug\vc60.pdb

?????目錄??????????0??2018-03-27?20:16??6機器調(diào)度問題\Debug

?????目錄??????????0??2018-03-27?20:16??6機器調(diào)度問題

-----------?---------??----------?-----??----

???????????????860208????????????????????13