+ Reply to Thread
Results 1 to 3 of 3

Formula to limit the minimum waste

  1. #1
    Registered User
    Join Date

    Formula to limit the minimum waste

    I've got a problem, that I can't seen to solve.
    I have a list o values (with comma) Eg.:

    And this are the lenght of the strip of fabric I've to cut, the problem is that I'm limited do a 6 m max lenght. What I needed to do is simple...... distribute those values so that I have a remaning of as small as possible.

    (excellent would be to be able to limit the minimum waste (so that it's usable))

    P.s. I'm not a newbie but i'm stuck.... I just need some help to get me started....... I just need the core.....

    Last edited by Krazy_Kaos; 09-26-2007 at 07:27 AM.

  2. #2
    Forum Contributor
    Join Date
    Lexington, MA
    Your problem is to select lengths of fabric that add up to 6 m without going over. This is similar to adding various weights to bins that have a maximum load, and trying to use as few bins as possible.

    The usual practical approach is the Greedy algorithm. You start with the biggest item that will fit your conditions, then add the next biggest, and so on.

    For more work, you can change the search to make reasonable "mistakes", taking some choices that are not biggest, and see if you happen on a better fit. You look at as many other choices as you can within your time constraints, and usually that is enough for practical purposes.

    The algorithm is not optimal, because there can be combinations in the data that would be better. For example, if the goal is to choose amounts that add close to 100 without going over, consider this data: 50, 40, 25, 25.

    The Greedy algorithm picks 50 + 40 and stops at a total of 90. It can't fit in a 25. Obviously, if it skipped 40 (violating Greedy) it would end up with 50 + 25 + 25 = 100, a perfect fit.

    So, Greedy is a good first algorithm, and adding "side searches" that explore other combinations can give a better result. Unfortunately, there is no way of being perfect without examining all possibilities.

    The attached workbook implements this algorithm using worksheet formulas, as an example.
    Attached Files Attached Files
    FrankBoston is the pen name for Andrew Garland, Lexington MA

  3. #3
    Registered User
    Join Date


    Thanx for your help FrankBoston ......
    Tonight I'll take a look at that but it seems like I'll have to find a way of trying every single possible combination and choosing the one with less waste (or a better waste ..... I'm thinking of a minimum waste greater than 1,50 or smaller then 0,5 ).

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1