Nesting and Optimization Logic Process
-
Hello, I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little... First, let me define the terms I will use (a crash course in steel purchasing): -Mill Order: simply an order of material placed to the steel mill -Beams: should be self explanatory, but I want to cover their dimensioning: -a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length. Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number of 1/16ths of an inch that make up the length. -> For the sample, the length would be 1728 (1728/16)/12=9).) -Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50 -Standard Size: any beam length 30ft-65ft in increments of 5ft. -Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams. -Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory the extra. a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you 4. But if you need 2, you must buy 3 and inventory the extra. The bundle requirements change with each flange depth and weight. Ok. Now to the logic bit... I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle. This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program. I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or someth
-
Hello, I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little... First, let me define the terms I will use (a crash course in steel purchasing): -Mill Order: simply an order of material placed to the steel mill -Beams: should be self explanatory, but I want to cover their dimensioning: -a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length. Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number of 1/16ths of an inch that make up the length. -> For the sample, the length would be 1728 (1728/16)/12=9).) -Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50 -Standard Size: any beam length 30ft-65ft in increments of 5ft. -Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams. -Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory the extra. a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you 4. But if you need 2, you must buy 3 and inventory the extra. The bundle requirements change with each flange depth and weight. Ok. Now to the logic bit... I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle. This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program. I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or someth
I think I might be able to help. Before we start, I have two observations: [1] I take it that ordering the beams in a manner that is not suited to the design will result in someone at the site cutting / trimming / grinding each beam ordered to the beam design specs. If so, there are personnel charges, equipment usage, temporary storage locations, etc... that are costs to the company to make that happen. I do not see those costs in your description, and I wonder if sometimes the cost of buying a non-standard size/bundle is actually cheaper. I will ignore this complexity for now. [2] Clearly, the problem is overwhelming you as it has too many parameters to jostle at once. A good problem solving strategy in such cases is to relax a few of the paramaters and get a solution for the relaxed problem. For example, I would start off assuming you are always ordering beams of the same nominal flange depth and the same pounds per foot. The examples discussed almost suggest you are indeed making this assumption, but I want to be clear. I would like to start here and steer you to a solution. Once we find a solution for this relaxed problem, we will add back one of the constraints and see what changes. We will then continue to iterativley add back in all the constraints until the original problem is solved. Is this approach ok? HossFly
-
I think I might be able to help. Before we start, I have two observations: [1] I take it that ordering the beams in a manner that is not suited to the design will result in someone at the site cutting / trimming / grinding each beam ordered to the beam design specs. If so, there are personnel charges, equipment usage, temporary storage locations, etc... that are costs to the company to make that happen. I do not see those costs in your description, and I wonder if sometimes the cost of buying a non-standard size/bundle is actually cheaper. I will ignore this complexity for now. [2] Clearly, the problem is overwhelming you as it has too many parameters to jostle at once. A good problem solving strategy in such cases is to relax a few of the paramaters and get a solution for the relaxed problem. For example, I would start off assuming you are always ordering beams of the same nominal flange depth and the same pounds per foot. The examples discussed almost suggest you are indeed making this assumption, but I want to be clear. I would like to start here and steer you to a solution. Once we find a solution for this relaxed problem, we will add back one of the constraints and see what changes. We will then continue to iterativley add back in all the constraints until the original problem is solved. Is this approach ok? HossFly
HossFly, First of all, I cannot tell you how much I appreciate a timely and professional response. Such things are a rarity among most forums and message boards. To address your first point raised; all cutting, grinding, welding, etc. is done by us in our shop. So the ammount of "shop hours" is billed seperately to the job. But that is a very good point I had not thought of. As for your second point, yes, the problem is overwhelming me. I had thought of letting some of the parameters lie dormant for a short while, but it seems that every element of the problem is so closely related to the other - I am not quite sure of which parameters to drop. But I do like your recommendation of using the same beam size. I will try that and see if I can get a chunk of the problem diagrammed. My biggest problem right now, is that I cannot seem to even write out on paper how this process works. Thank you for your response, -David
-
HossFly, First of all, I cannot tell you how much I appreciate a timely and professional response. Such things are a rarity among most forums and message boards. To address your first point raised; all cutting, grinding, welding, etc. is done by us in our shop. So the ammount of "shop hours" is billed seperately to the job. But that is a very good point I had not thought of. As for your second point, yes, the problem is overwhelming me. I had thought of letting some of the parameters lie dormant for a short while, but it seems that every element of the problem is so closely related to the other - I am not quite sure of which parameters to drop. But I do like your recommendation of using the same beam size. I will try that and see if I can get a chunk of the problem diagrammed. My biggest problem right now, is that I cannot seem to even write out on paper how this process works. Thank you for your response, -David
Alright, we can break the problem down even further. I do intend to honor your request and not provide source or solution, but rather help you attack the problem. Here is a suggested course. Problem1: [1] Assume nominal flange depth and pounds per foot are fixed. [2] Assume there is only one standard size, and it is 30 ft. Problem2: [1] Assume Problem 1, but now allow for 30 ft or 35 ft standard sizes. I think once you solve Problem1, and especially after you solve Problem2, you will understand how the 30-65 feet increments are impacting your solution. Let me know how that goes. HossFly
-
Hello, I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little... First, let me define the terms I will use (a crash course in steel purchasing): -Mill Order: simply an order of material placed to the steel mill -Beams: should be self explanatory, but I want to cover their dimensioning: -a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length. Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number of 1/16ths of an inch that make up the length. -> For the sample, the length would be 1728 (1728/16)/12=9).) -Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50 -Standard Size: any beam length 30ft-65ft in increments of 5ft. -Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams. -Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory the extra. a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you 4. But if you need 2, you must buy 3 and inventory the extra. The bundle requirements change with each flange depth and weight. Ok. Now to the logic bit... I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle. This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program. I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or someth
I think you might be able to get a long way by using a multiple knapsack algorithm. The knapsack problem is to select a combination of N items with weights {Wi} to fill a knapsack with capacity K. The multiple knapsack problem tries to fill M knapsacks with capacities {Kj} from the N weights {Wi}. In your case the knapsacks are the available beamlengths. So if for one beam size the available beamlength is 20' and you need lengths {10', 6', 8', 12', 15', 2', 5', 7', 8'} then you need 73' of beam, so try to fill 4 knapsacks of 20'. If the algorithm fails, try to fill 5 etc... One standard multiple knapsack code is http://www.netlib.org/toms/632[^]. Once you know how many beams you need you can then cope with bundling. -- modified at 2:22 Saturday 22nd September, 2007 The multiple knapsack algorithm also allows you to include arbitrary beam lengths in your own inventory. So for the example given, if you had a 14' length of beam on hand, you could try to solve for 4 knapsacks {14, 20, 20, 20} and if this didn't work then add an additional 20' knapsack. This way you will continually use up your inventory
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
I think you might be able to get a long way by using a multiple knapsack algorithm. The knapsack problem is to select a combination of N items with weights {Wi} to fill a knapsack with capacity K. The multiple knapsack problem tries to fill M knapsacks with capacities {Kj} from the N weights {Wi}. In your case the knapsacks are the available beamlengths. So if for one beam size the available beamlength is 20' and you need lengths {10', 6', 8', 12', 15', 2', 5', 7', 8'} then you need 73' of beam, so try to fill 4 knapsacks of 20'. If the algorithm fails, try to fill 5 etc... One standard multiple knapsack code is http://www.netlib.org/toms/632[^]. Once you know how many beams you need you can then cope with bundling. -- modified at 2:22 Saturday 22nd September, 2007 The multiple knapsack algorithm also allows you to include arbitrary beam lengths in your own inventory. So for the example given, if you had a 14' length of beam on hand, you could try to solve for 4 knapsacks {14, 20, 20, 20} and if this didn't work then add an additional 20' knapsack. This way you will continually use up your inventory
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
A request was made to give no source code, and it was requested in BOLD. Yet you gave a link to an algorithm and source. Incredible.
HossFly, Thank you for helping me break down the problem like that. That was help much needed. I think I have a good chunk figured out. I used one length and worked out how to nest the beams into that length with respect to bundling. It seems to be working very well, on paper. Right now, I input the beam(s) to be nested, and I nest them into lengths of 65', 60', 55', 50', 45', 40', 35', and 30' (all the standard lengths) one at a time. Each of the standard lengths is a function and returns two values; the total number of bundles (after making sure the beam meets the bundle requirements), and the amount of drop (unused portions of the beam(s) I am nesting into). Then I sort out which function returns the least amount of drop (as this will be the cheapest and most productive solution). I think my next step is to do the same but for non-standard lengths (my only problem here is that I do not know how to round the lengths into even 6in. incriments). That way I can compare standard and non-standard prices. After that it's just a simple task of designing a report to output to the user. But I still have questions about this method's efficency and/or actual optimization. Is there a test of some kind that you know of that can provide evidence for this? If not, don't worry about it. Thank you again for breaking it down like that. I wish I had thought of that, but I guess that's why God didn't put me on the Earth by myself. -David
-
A request was made to give no source code, and it was requested in BOLD. Yet you gave a link to an algorithm and source. Incredible.
I suggested that a well-known algorithm may be applicable, and from the posting I guessed that the OP would not be aware that tried and tested source code was available - so I posted a link to one. It would be silly for a professional programmer to try to solve the multiple knapsack problem without at least considering the standard codes. Get offended if you like - it's your blood pressure. From re-reading the original post, the fact that the standard lengths are not fixed but come in increments of 5' means that the multiple knapsack is not optimal. It would give you an efficient way of quickly testing different bundles - e.g. if you need 73' as in my example, you could try your inventory plus 3 lengths of 25', 3 of 30' and see if a solution existed. If the number of lengths is small then the problem can be efficiently solved with an exhaustive search, but the complexity quickly escalates as the number of lengths increases.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
HossFly, Thank you for helping me break down the problem like that. That was help much needed. I think I have a good chunk figured out. I used one length and worked out how to nest the beams into that length with respect to bundling. It seems to be working very well, on paper. Right now, I input the beam(s) to be nested, and I nest them into lengths of 65', 60', 55', 50', 45', 40', 35', and 30' (all the standard lengths) one at a time. Each of the standard lengths is a function and returns two values; the total number of bundles (after making sure the beam meets the bundle requirements), and the amount of drop (unused portions of the beam(s) I am nesting into). Then I sort out which function returns the least amount of drop (as this will be the cheapest and most productive solution). I think my next step is to do the same but for non-standard lengths (my only problem here is that I do not know how to round the lengths into even 6in. incriments). That way I can compare standard and non-standard prices. After that it's just a simple task of designing a report to output to the user. But I still have questions about this method's efficency and/or actual optimization. Is there a test of some kind that you know of that can provide evidence for this? If not, don't worry about it. Thank you again for breaking it down like that. I wish I had thought of that, but I guess that's why God didn't put me on the Earth by myself. -David
Alright, we are getting closer. The next suggested steps would be: Problem3: [1] Assume nominal flange depth and pounds per foot are fixed. [2] Assume there are only only non-standard sizes. Problem4: [1] Assume nominal flange depth and pounds per foot are fixed. [2] Assume there is one standard size (e.g., 30') and non-standard sizes. After you solve Problem4 you will then have unraveled another aspect of your algortihm (how the standard and non-standard sizes impact the logic.) The big picture ... I have often been in need of a niche-like algorithm similar in complexity to yours. I cannot count the times I have been frustratingly lost and on my own as well. My intent was not to give you fish, but rather share with you how I have caught several fish. You have used that now to (almost) catch your own fish, and that is very rewarding. Sometimes you may not catch your fish, but by applying good problem solving skills (e.g., break down, relaxing conditions, combining sub-optimal sub-solutions, etc...), you gain the knowledge and understanding needed to realize what aspect of someone else's solution might work for you. You will soon have your own algorithm. Not only that, you will have a deeper understanding of the mechanics of your problem. Having an algorithm is one thing - an optimal algorithm is another. Being able to analyze optimality requires intimacy with the problem. You are gaining this intimacy as well. The standard means to measure optimality is to do a flop count (floating point operations). Some folk measure a "flop" as one addition and one multiplication. The idea is to then count the flops in your algorithm. A good example is Matrix-Vector multiplication. To multiply an n-by-n matrix by a an n-vector would require roughly n^2 flops. Sometimes your matrix may have special properties (e.g., cyclic) and there are algorithms out there that can do the work in far less than n^2 flops. I would suggest at least an attempt to count flops. This is a very difficult aspect of algorithm construction. Once you have completed your algorithm, and have been over the entire process with diligence, you will then be in a position to analyze the good/bad of a previous post about a possible alternative algorithm for you. I leave it to you to weigh the good and bad of that algorithm. Best Regards, HossFly