深度搜索定界

深度搜索定界

例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.