最佳调度问题Word文档下载推荐.docx

最佳调度问题Word文档下载推荐.docx

《最佳调度问题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《最佳调度问题Word文档下载推荐.docx（6页珍藏版）》请在冰点文库上搜索。

}

private:

voidInit（int）;

voidNewNode（MinHeapNode,int,int,int,int）;

ints;

//已安排作业数

intf1;

//机器1上最后完成时间

intf2;

//机器2上最后完成时间

intsf2;

//当前机器2上的完成时间和

intbb;

//当前完成时间和下界

int*x;

//当前作业调度

};

voidMinHeapNode:

:

Init（intn）

{//最小堆结点初始化

x=newint[n];

for（inti=0;

i<

n;

i++）

x[i]=i;

s=0;

f1=0;

f2=0;

sf2=0;

bb=0;

NewNode（MinHeapNodeE,intEf1,intEf2,intEbb,intn）

{//最小堆新结点

x[i]=E.x[i];

f1=Ef1;

f2=Ef2;

sf2=E.sf2+f2;

bb=Ebb;

s=E.s+1;

classFlowshop

friendintmain（）;

intBBFlow（）;

Flowshop（intn）;

//构造函数

~Flowshop（）;

//析构函数

intBound（MinHeapNode,int&

int&

bool**）;

voidSort（）;

intn;

int**M;

int**b;

int**a;

int*bestx;

intbestc;

bool**y;

Flowshop:

Flowshop（intn）

//M=newint*[n];

b=newint*[n];

a=newint*[n];

y=newbool*[n];

bestx=newint[n];

bestc=10000;

for（inti=0;

{

//M[i]=newint[2];

b[i]=newint[2];

a[i]=newint[2];

y[i]=newbool[2];

}

~Flowshop（）

delete[]M[i];

delete[]b[i];

delete[]a[i];

delete[]y[i];

deletebestx,M,b,a,y;

voidFlowshop:

Sort（）

{//对各作业在机器1和2上所需时间进行冒泡排序

int*c=newint[n];

for（intj=0;

j<

2;

j++）

for（inti=0;

{

b[i][j]=M[i][j];

c[i]=i;

}

for（i=0;

n-1;

for（intk=n-1;

k>

i;

k--）

if（b[k][j]<

b[k-1][j]）

{

swap（b[k][j],b[k-1][j]）;

swap（c[k],c[k-1]）;

}

a[c[i]][j]=i;

}

delete[]c;

intFlowshop:

Bound（MinHeapNodeE,int&

f1,int&

f2,bool**y）

{//计算完成时间和下界

for（intk=0;

k<

k++）

for（intj=0;

y[k][j]=0;

for（k=0;

=E.s;

y[a[E.x[k]][j]][j]=1;

f1=E.f1+M[E.x[E.s]][0];

f2=（（f1>

E.f2）?

f1:

E.f2）+M[E.x[E.s]][1];

intsf2=E.sf2+f2;

ints1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;

//计算s1的值

if（!

y[j][0]）

k1--;

if（k1==n-E.s-1）

f3=（f2>

f1+b[j][0]）?

f2:

f1+b[j][0];

s1+=f1+k1*b[j][0];

//计算s2的值

for（j=0;

y[j][1]）

k2--;

s1+=b[j][1];

s2+=f3+k2*b[j][1];

//返回完成时间和下界

returnsf2+（（s1>

s2）?

s1:

s2）;

BBFlow（）

Sort（）;

priority_queue<

MinHeapNode>

H;

MinHeapNodeE;

E.Init（n）;

while（E.s<

=n）

if（E.s==n）

if（E.sf2<

bestc）

{

bestc=E.sf2;

for（inti=0;

bestx[i]=E.x[i];

}

delete[]E.x;

else

for（inti=E.s;

swap（E.x[E.s],E.x[i]）;

intf1,f2;

intbb=Bound（E,f1,f2,y）;

if（bb<

MinHeapNodeN;

N.NewNode（E,f1,f2,bb,n）;

H.push（N）;

delete[]E.x;

if（H.empty（））

break;

E=H.top（）;

H.pop（）;

returnbestc;

intmain（）

intn;

cout<

<

"

输入作业数:

;

cin>

>

int**M=newint*[n];

M[i]=newint[2];

for（i=0;

cout<

M["

]["

]:

cin>

M[i][j];

FlowshopG（n）;

G.M=M;

G.n=n;

intf=G.BBFlow（）;

最佳调度方案:

cout<

G.bestx[i]<

"

endl;

最佳完成时间和:

f<

return0;