深度搜索定界 例2:设定有n台处理机p1,p2,......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断,作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短? 说明:本题有两重搜索法,搜索处理机和搜索作业,当m,n较大时,搜索处理机不可能?搜索作业容易确定上下界,容易剪支。 程序如下: program jobs;
const maxn=100;maxm=100;
var
t:array[1..maxm] of integer;
l,bestl:array[1..maxn] of integer;
a,besta:array[1..maxn,1..maxm] of integer;
time:array[0..maxn] of integer;
done:array[1..maxm] of boolean;
least,i,j,k,n,m,rest,min:integer;
procedure print ;
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to bestl do
write(besta[i,j],' ');
writeln;
end ;
writeln('Time=',time[0]+1);
end;
procedure init;
var
f:text;
fname:string;
i,j,k:integer;
begin
write('filename=');readln(fname);
assign(f,fname);
reset(f);
readln(f,n,m);
for i:=1 to m do
begin
read(f,t);inc(rest,t);
end;
close(f);
least:=trunc(rest div n)+1;{确定下界}
for i:=1 to m-1 do
for j:=i+1 to m do
if t<t[j] then
begin
k:=t;t:=t[j];t[j]:=k
end;
end;
procedure try(p,q:integer);{从p..m中选取作业放在处理机q上}
var i:integer;
begin
for i:=p to m do
if done and (time[q]+t<=time[q-1]) then
begin
done:=false;
inc(l[q]);
a[q,l[q]]:=t;
inc(time[q],t);
dec(rest,t);
try(i+1,q);
done:=true;
dec(l[q]);
dec(time[q],t);
inc(rest,t);
end;
if rest<=(n-q)*time[q] then
if rest=0 then
begin
bestl:=l;besta:=a;
time[0]:=time[1]-1;
if time[1]=least then
begin
print;halt;
end;
end else
if q<n then try(1,q+1);
end;
begin
init;
fillchar(done,sizeof(done),true);
fillchar(time,sizeof(time),0);
fillchar(a,sizeof(a),0);
fillchar(besta,sizeof(besta),0);
fillchar(l,sizeof(l),0);
fillchar(bestl,sizeof(bestl),0);
for i:=1 to m do{确定上界}
begin
k:=1;
for j:=2 to n do
if time[j]<time[k] then k:=j;
time[k]:=time[k]+t;
bestl[k]:=bestl[k]+1;
besta[k,bestl[k]]:=t;
end;
min:=time[1];
for i:=2 to n do
if time>min then min:=time;
time[0]:=min-1;
if min=least then begin print; halt end;
fillchar(time,sizeof(time),0);
time[0]:=min-1;
try(1,1);
print;
end.
|