Bottom-Left-First like Heuristic to evaluate BinPackingFeasible(r, i, j)
Arrange the n modularized boxes based on the increasing order of
pi; I = {0, 0, 0}, Lz = Lx = 0; for i = 1 to n do
flag = false;
for (x, y, z) ∈ I do
if box i can be put at (x, y, z) and x + hi ≤ Lx, z + di ≤ Lz then flag = true,
break;
end if
end for if flag =false
then
if Lx = 0 or Lx = H then
if box i can be put at (0, 0, Lz) then
x = 0,y = 0,z = Lz,flag =true,Lz = Lz + di,Lx = hi; else
if Lz < D then
Lz = D,Lx = H,i = i − 1;
end if
end if
else
for (x, y, z) ∈ I : x = Lx, y = 0 do
if box i can be put at (x, y, z) and z + di ≤ Lz then
flag =true,Lx = Lx + hi,break;
end if
end for if flag =false
then
Lx = H, i = i − 1;
end if
end if
else
put box i at position (x, y, z), I = I \ {(x, y, z)};
I = I ∪ {(x + hi, y, z), (x, y + wi, z), (x, y, z + di)}; end if
end for
*
It is worth noting that in the above Bottom-Left-First heuristic, when the attempt
to position box i at point (x,y,z) causes a failure, it is possible that we allow the
rotation of the box and try to put the rotated box at (x,y,z) again. Such an extra
consideration would increase the chance of BinPackingFeasible(r,i, j) being true but
would result in a longer computational time as well.
46
Sh. Sharif Azadeh et al.