Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations SkipVought on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Linear Nesting?

Status
Not open for further replies.
SqueakinSweep

SqueakinSweep

Programmer
Jun 20, 2002
945
0
0
GB
Here is a puzzle that has baffled me for years. In concept it is quite simple, but despite many attempts at coding, I have always failed to reach an optimum solution. Quite simply the puzzle is one of linear nesting, ie the best cut of a series of parts from a list of bars. 2 things are required…an optimum nest, and speed. Its no good trying to create every combination and, its just too slow…Ive tried it. Im sure there are algorithms that can be used, but not ones I am familiar with.

Here’s a sample for you to cut your teeth on (all lengths in mm)

Rules…
Get the best possible nest in the least time.
Make an allowance 10mm for each Cut made (to allow for the saw blade)

Bars to use
30 @ 15500
31 @ 14000

Pieces to Cut
22 @ 7114
2 @7097
2 @ 7074
15 @ 5016
15 @ 5006
80 @ 2930
10 @ 2740
110 @ 2636

The Optimal cut I have found so far….cuts 255 pieces out of 256, and leaves 1 @ 7097 uncut. Can anyone do better??






Sweep
...if it works, you know the rest..
Always remember that Google is your friend
curse.gif
 
Sort by date Sort by votes
I thought I'd try the simplest way - going through the "cut-offs" until I found one that was the right length. Here's my complete test-hanress:

Code: 
[COLOR=white]<html>
<head>
	<title>Cutting length optimiser</title>

	<style type="text/css">
		html, body {
			padding: 0px;
			margin: 0px;
		}
		body {
			margin: 1em;
			font-family: Verdana, Arial, sans-serif;
			font-size: 0.8em;
		}
		div.outer {
			background-color: #FFE7B9;
			margin-bottom: 1em;
			padding: 1em;
		}
	</style>

	<script type="text/javascript">
	<!--

		// both these arrays hold arrays of "quantity, length"
		var woodToCut = [[22, 7114], [2, 7097], [2, 7074], [15, 5016], [15, 5006], [80, 2930], [10, 2740], [110, 2636]];
		var woodAvailable = [[30, 15500], [31, 14000]];
		var bladeWidth = 10;

		var startTime = endTime = null;

		function sortPairsByLengthAsc(a, b) {
			if (a[1] < b[1]) return(-1);
			if (a[1] > b[1]) return(1);
			return(0);
		}

		function sortPairsByLengthDesc(a, b) {
			if (a[1] < b[1]) return(1);
			if (a[1] > b[1]) return(-1);
			return(0);
		}

		function findMeasurements() {
			var s = '';
			var iteration = 1;
			var runLoop = true;
			//var runLoop = false;		// leave in to bypass loop!

			startTime = new Date().getTime();
			while (runLoop) {
				s += '<br /><b>Iteration ' + iteration + '</b>\n';

				woodAvailable.sort(sortPairsByLengthDesc);

				var havePiecesLeft = false;
				for (var loop=0; loop<woodToCut.length; loop++) {
					// make sure we need to still cut pieces of this length
					if (woodToCut[loop][0] != 0) {
						havePiecesLeft = true;
						s += '<br />Trying to find a piece at least ' + woodToCut[loop][1] + 'mm in length<br />\n';

						// now see if we can cut this length from any pieces. if not, we may as well stop!
						var foundAt = -1;
						for (var loop2=0; loop2<woodAvailable.length; loop2++) {
							if (woodAvailable[loop2][1] >= woodToCut[loop][1] && woodAvailable[loop2][0] != 0) {
								foundAt = loop2;
								break;	// could go on here to search remaining lengths to see if an exact (or closer) match is found
							}
						}
						if (foundAt == -1) {
							// no point in continuing if we can never finish!
							s += '<br /><b>No more pieces of the right length left!</b><br />\n';
							runLoop = false;
							break;
						} else {
							var existingLength = newLength = woodAvailable[foundAt][1];

							// decrease cutting quantity
							woodToCut[loop][0]--;

							// perform cutting. remove length, and, if still necessary, 10mm
							// if the 10mm isn't available, we know this is the end of a length, and no cutting is necessary
							newLength -= woodToCut[loop][1];
							if (woodAvailable[foundAt][1] <= bladeWidth) {
								s += 'Found! No cut necessary. Single piece available of length: ' + woodAvailable[foundAt][1] + 'mm<br />\n';
							} else {
								newLength -= bladeWidth;
								s += 'Found! Cutting into a ' + existingLength + 'mm piece, leaving a ' + newLength + 'mm piece<br />\n';
							}

							// decrease count of bits of wood available of this length
							woodAvailable[foundAt][0]--;

							// and add in 1 piece of the new length, checking first to see if there are already any
							// (in which case, we simply increase the quantity)
							var foundExisting = false;
							for (var loop2=0; loop2<woodAvailable.length; loop2++) {
								if (woodAvailable[loop2][1] == newLength) {
									foundExisting = true;
									woodAvailable[loop2][0]++;
									break;
								}
							}
							if (!foundExisting) woodAvailable[woodAvailable.length] = [1, newLength];
						}
					}
				}		// for (var loop=0; loop<woodToCut.length; loop++) {
				if (!havePiecesLeft) runLoop = false;

				s += '<br /><b>Iteration ' + (iteration++) + ' Results</b><br />\n';
				for (var loop=0; loop<woodToCut.length; loop++) {
					s += 'Cut ' + woodToCut[loop][0] + ' pieces at ' + woodToCut[loop][1] + 'mm<br />\n';
				}
			}
			var delta = new Date().getTime() - startTime;
			document.getElementById('results').innerHTML = s;

			var mins = parseInt(delta / 1000 / 60, 10);
			var secs = (delta - (mins * 60 * 1000)) / 1000;

			var s = 'Time taken: ' + mins + (mins == 1 ? ' minute' : ' minutes') + ', ' + secs + ' seconds ';
			document.getElementById('stats').innerHTML = s;
		}

		window.onload = function() {
			// sort "wood to cut" list by length, in descending order
			woodToCut.sort(sortPairsByLengthDesc);
			woodAvailable.sort(sortPairsByLengthDesc);

			// Show user-friendly details
			var s = '<br /><b>Cutting Requirements</b><br />\n';
			for (var loop=0; loop<woodToCut.length; loop++) {
				s += 'Cut ' + woodToCut[loop][0] + ' pieces at ' + woodToCut[loop][1] + 'mm<br />\n';
			}

			s += '<br /><b>Wood Available</b><br />\n';
			for (var loop=0; loop<woodAvailable.length; loop++) {
				s += woodAvailable[loop][0] + ' pieces at ' + woodAvailable[loop][1] + 'mm<br />\n';
			}
			document.getElementById('requirements').innerHTML = s;

			findMeasurements();
		};

	//-->
	</script>
</head>

<body>
	<div class="outer">
		<b>Requirements</b>
		<div id="requirements">None yet</div>
	</div>
	<div class="outer">
		<b>Results</b>
		<div id="results">None yet</div>
	</div>
	<div class="outer">
		<b>Statistics</b>
		<div id="stats">None yet</div>
	</div>
</body>
</html>[/color]

Interestingly engough, I expected that running through the cut-offs in ascending length order would give better results that doing it in descending order... but for the lengths given in your post, that is not the case.

Anyway - this leaves me with 22 pieces at 2636mm left - so it's clearly not an optimal solution.

Is there actually a formula for solving this one? Does anyone have a name for it?

Dan

[tt]Dan's Page [blue]@[/blue] Code Couch
[/tt]
 
Upvote 0 Downvote
OK - I found lots of links to the algorithm (the "cutting stock" or "knapsack" problem).

This one looks promising, but I must admit to being lost fairly quickly. Especially when they started using phrases like:

NP complete
orthonormal latices
Abelian groups
diagonalize
orthogonolization
topomological straterization pomodical product

I swear some of those are made up just to make it appear more intellectual a problem than it is ;-)

Anyway - the link:


Dan



[tt]Dan's Page [blue]@[/blue] Code Couch
[/tt]
 
Upvote 0 Downvote
SqueakinSweep,

Nice problem, you even included the kerf measurement. The most efficient and accurate way I've found for creating cutting plans is to work with combination multisets. I don't have time at the moment to work this one up, but I was really impressed by the puzzle. This is exactly the kind of puzzle I was hoping to find in this forum.

boyd.gif

SweetPotato Software Website
My Blog
 
Upvote 0 Downvote
if it has ortho in it then it must have something to do with birds (the flying kind)(no not stewardesses).

Christiaan Baes
Belgium

"My new site" - Me
 
Upvote 0 Downvote
Wow!!

Dan...I am impressed, with what you came up with so quickly. Im going to take a look at the link you posted, and start afresh on my approach to this problem.

Craigsboyd...nice to see a familiar face from the VFP forums, where I started off in TT.

I actually use a "nesting engine" in a suite of software Im developing, and at present, Im using a 3rd party dll plug in. There are many linear nesting packages out there thet claim to be optimisers but arent by any means, and many of my own cobbled attempts have beaten these. I got reasonable results from creating a table of all possible combos, and then stripping out those with the minimum waste, but I soon realised this was way too slow. Ive also tried mechanises, long to short, short to long, along with incorporating pre-nest routines such as stripping out one to one nests, and also two from one.

In fact I used to have and will try to dig out again, a collection of so called "tricky cuts", which would identify the good optimisers from the poor ones. About the best I have found so far is one called CutLogic, which is actually available as a free download for 30 days.








Sweep
...if it works, you know the rest..
Always remember that Google is your friend
curse.gif
 
Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

theEclipse
  • Locked
  • Question
data structure theory: Infinite nesting stored in database.....
Replies
1
Views
14
gmmastros
gmmastros

Part and Inventory Search

Sponsor

Back
Top