C++貪心算法處理多機(jī)調(diào)度問題詳解

更新時(shí)間：2022年06月30日 09:25:56 作者：成就一億技術(shù)人

貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解

多機(jī)調(diào)度問題思路

1、把作業(yè)按加工所用的時(shí)間從大到小排序

2、如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等，則直接把作業(yè)分配下去

3、如果作業(yè)數(shù)目比機(jī)器的數(shù)目多，則每臺(tái)機(jī)器上先分配一個(gè)作業(yè)，如下的作業(yè)分配時(shí)，是選那個(gè)表頭上 s 最小的鏈表加入新作業(yè)

可以考慮以下的貪心策略:

(1)最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略。

(2)最短處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略。

(3)作業(yè)到達(dá)時(shí)間優(yōu)先的貪心選擇策略。

*貪?策略：優(yōu)先處理花費(fèi)時(shí)間長(zhǎng)的任務(wù)，這樣可以減少短任務(wù)的等待時(shí)間.

問題描述

形式：有n個(gè)任務(wù)，m臺(tái)機(jī)器，n>m，每個(gè)作業(yè)i可以選擇?臺(tái)設(shè)備進(jìn)?加?，加?時(shí)間為ti，每臺(tái)機(jī)器同時(shí)只能加??個(gè)作業(yè)，且不可中斷。實(shí)現(xiàn)作業(yè)調(diào)度，使得n個(gè)作業(yè)的等待時(shí)間最短。

假定有7個(gè)獨(dú)立作業(yè)，所需處理時(shí)間分別為｛2，14，4，16，6，5，3｝，由三臺(tái)機(jī)器M1,M2,M3加工。按照貪心算法產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需總加工時(shí)間為17.

代碼實(shí)現(xiàn)【C++】

#include<iostream> 
using namespace std;
#define N 7 
#define M 3 
int s[M] = { 0, 0, 0 };
//求出目前處理作業(yè)的時(shí)間和 最小的機(jī)器號(hào) 
int min(int m){
int min = 0;
int i;
for (i = 1; i<m; i++){
if (s[min]>s[i]){
min = i;
}
}
return min;
}
//求最終結(jié)果（最長(zhǎng)處理時(shí)間） 
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;
}
//機(jī)器數(shù)大于待分配作業(yè)數(shù) 
int setwork1(int t[], int n){
int i = 0;
for (; i<n; i++){
s[i] = t[i];
}
int ma = max(s, N);
return ma;
}
//機(jī)器數(shù)小于待分配作業(yè)數(shù) 
int setwork2(int t[], int n){
int i;
int mi = 0;
for (i = 0; i<n; i++){
mi = min(M);
cout << "接下來由" << mi+1 << "號(hào)機(jī)器處理任務(wù)" << i + 1 << endl;
s[mi] = s[mi] + t[i];
}
int ma = max(s, M);
return ma;
}
void main()  //DEV中是int,vc++6.0中是void
{
	int time[N] = { 16, 14, 6, 5, 4, 3, 2 };//處理時(shí)間按從大到小排序 
	int maxtime;
	if (M >= N)
		maxtime = setwork1(time, N);
	else
		maxtime = setwork2(time, N);
	cout << "最多耗費(fèi)時(shí)間" << maxtime << endl;
}

結(jié)果