Cutting Stock Problem

[roadrunner]

I know you asked for a 2d cutting stock problem; I am currently working on one. All I have so far is a solution to a 1d cutting stock problem. You input a size list, a quantity list, and the length of the raw stock. It outputs a list and the wasted stock. You cut the pieces in the order of the output list.

For an example, if you want to cut 3 boards 2 feet long, 1 board 8 feet long, and 3 boards 4 feet long out of 10 foot long boards type on the command line:

main({3,8,4},{2,1,3},10)

The output in this case is: {{4,4,8,4,3,3},4}

This indicates you cut 2 boards of 4 feet from the first 10 footer and toss the 2 feet left over, cut 1 board 8 feet long out of a second 10 footer and toss the 2 feet left over, then cut 1 board 4 feet long and two boards 3 feet long out of the third 10 footer. You’ve wasted 4 feet of board.

Problems I have with this code are:

1. More than 6 or 7 boards takes forever to run on the emulator (and forever and a day on the handheld) because it checks every permutation, even the repeated ones;
2. Has a for loop that may subtract 1 from the index inside the loop; dangerous because, if not done correctly, it could result in an infinite loop;
3. Has a subroutine that calls itself, also dangerous because that hogs a lot of memory and may lead to a crashed calculator.
4. Ignores the width of the saw blade.

I am still trying to decide if this program returns a “best” solution or not. I plan to modify it to eliminate the redundant checks on repeated permutations and to work on a 2d problem that cuts rectangles out of round stock.

Road

Here is the code:

local mainlist;
local bestlist;
local bestwaste;
local sizeofrawstock;
local mainlistsize;

local getwastedstock()
BEGIN
local tempstocksize, waste;
waste:=0;
tempstocksize:=sizeofrawstock;
for I from 1 to mainlistsize do
tempstocksize:=tempstocksize − mainlist(I);
if tempstocksize < 0 then
waste:=waste + tempstocksize + mainlist(I);
I:=I−1;
tempstocksize:=sizeofrawstock;
end;
end;
waste:=waste + tempstocksize;
if waste < bestwaste then
bestwaste:=waste;
bestlist:=mainlist;
end;
print();
print("best so far: " + string(bestlist) +
" / " + string(bestwaste));
print("checking: " + string(mainlist) + " / " + string(waste));
END;

local lastelement(number)
BEGIN
mainlist:=concat(number,mainlist);
getwastedstock();
mainlist:=sub(mainlist,2,size(mainlist));
END;

local takeanelementout(list,n)
BEGIN
local s;
s:=size(list);
if s == 1 then return {};
end;
if n == 1 then return sub(list,2,s);
end;
if n == s then return sub(list,1,s-1);
end;
return concat(sub(list,1,n-1),sub(list,n+1,s));
END;

local putanelementin(list, location, element)
BEGIN
if location == 1 then
return concat(element, list);
end;
local listsize;
listsize:=size(list);
if location == listsize + 1 then
return concat(list, element);
end;
return concat(sub(list,1,location−1),
element, sub(list, location, listsize));
END;

local doalist(list)
BEGIN
local listsize, i;
listsize:=size(list);
if listsize = 1 then
lastelement(list(1));
return 0;
else
for i from 1 to listsize do
mainlist:=putanelementin(mainlist,1,list(i));
list:=takeanelementout(list,i);
doalist(list);
list:=putanelementin(list,i,mainlist(1));
mainlist:=takeanelementout(mainlist, 1);
end;
end;
END;

local makealist(piecesize,quantity)
BEGIN
local list:={};
for I from 1 to size(piecesize) do
for J from 1 to quantity(I) do
list:=CONCAT(list, piecesize(I));
end;
end;
mainlistsize:=size(list);
bestwaste:=sizeofrawstock*mainlistsize;
return list;
END;

export main(piecesize, quantity, stocksize)
BEGIN
if max(piecesize) > stocksize then
return "you need bigger stock";
end;
print();
mainlist:={};
bestlist:={};
sizeofrawstock:=stocksize;
doalist(makealist(piecesize, quantity));
return {bestlist,bestwaste};
END;