06-17-2015, 12:26 PM

I'm trying to locate existing hp programming that might relate to the "Cutting Stock Problem." In particular, the 2D CSP is of special interest to me. I would appreciate any help!

Thanks,

-Dale-

Thanks,

-Dale-

You're currently viewing a stripped down version of our content. View the full version with proper formatting.

06-17-2015, 12:26 PM

I'm trying to locate existing hp programming that might relate to the "Cutting Stock Problem." In particular, the 2D CSP is of special interest to me. I would appreciate any help!

Thanks,

-Dale-

Thanks,

-Dale-

06-19-2015, 04:09 PM

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;

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;

06-19-2015, 05:05 PM

This may be a problem unsuitable for the calc for all but a few cuts. Especially if a non-guillotine solution is desirable. Matlab code can be found on the net, for a solution for this problem. I've been tinkering with that, just for the agony of it.

-Dale-

EDIT: There are some YouTube lectures on the subject,( if you haven't already seen them):

Lecture 4

-Dale-

EDIT: There are some YouTube lectures on the subject,( if you haven't already seen them):

Lecture 4

**HP Forums:**https://www.hpmuseum.org/forum/index.php**:**

Powered By MyBB, © 2002-2021 MyBB Group