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

第C++貪心算法處理多機調(diào)度問題詳解1、把作業(yè)按加工所用的時間從大到小排序

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

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

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

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

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

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

*貪?策略：優(yōu)先處理花費時間長的任務，這樣可以減少短任務的等待時間.

問題描述

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

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

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

#includeiostream

usingnamespacestd;

#defineN7

#defineM3

ints[M]={0,0,0};

//求出目前處理作業(yè)的時間和最小的機器號

intmin(intm){

intmin=0;

inti;

for(i=1;ii++){

if(s[min]s[i]){

min=i;

returnmin;

//求最終結(jié)果（最長處理時間）

intmax(ints[],intnum){

intmax=s[0];

for(inti=1;ii++){

if(maxs[i])

max=s[i];

returnmax;

//機器數(shù)大于待分配作業(yè)數(shù)

intsetwork1(intt[],intn){

inti=0;

for(;ii++){

s[i]=t[i];

intma=max(s,N);

returnma;

//機器數(shù)小于待分配作業(yè)數(shù)

intsetwork2(intt[],intn){

inti;

intmi=0;

for(i=0;ii++){

mi=min(M);

cout"接下來由"mi+1"號機器處理任務"i+1endl;

s[mi]=s[mi]+t[i];

intma=max(s,M);

returnma;

voidmain()//DEV中是int,vc++6.0中是void

inttime[N]={16,14,6,5,4,3,2};//處理時間按從大到小排序

intmaxtime;

if(M=N)

maxtime=setwork1(time,N);

else

m