Thread: How to combines differents pieces and form a package

  1. #1
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184

    Question How to combines differents pieces and form a package

    Hi friends!

    I need find a best way to combine pieces with 200-380g weight and form a package (box) of 2000 - 2030 grams.

    At the system, the pieces come one each time and have 12 boxes (options) to distribute and form a packages.

    Pieces can be discarded, when it's not possible fit at neither box.
    But the Rejects needs be low.

    Someone Knows a Algorithm to help me a resolve this situation ?


    collected statistics of pieces occurrences
    How to combines differents pieces and form a package-rangle-table-png

    Sample of packages (boxes) finished
    How to combines differents pieces and form a package-sample-boxcompletes-png

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,685
    > Sample of packages (boxes) finished
    Box 4 seems overweight.

    > the pieces come one each time and have 12 boxes (options) to distribute and form a packages.
    So how many boxes can you fill concurrently ?

    > Pieces can be discarded, when it's not possible fit at neither box.
    Either means "a choice of two", so neither is "not a choice of two".

    Do you have a finite number of items, and a finite number of boxes?
    Say for example, 100 items need to be packed into 12 boxes, but you're only allowed to fill one box at once.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184
    Quote Originally Posted by Salem View Post
    > Sample of packages (boxes) finished
    Box 4 seems overweight.
    Yes, Sorry.... It's only a manual sample with error

    > the pieces come one each time and have 12 boxes (options) to distribute and form a packages.
    So how many boxes can you fill concurrently ?
    12 boxes at same time, when one box complete 2000g, the user press a button to reset and start again

    > Pieces can be discarded, when it's not possible fit at neither box.
    Either means "a choice of two", so neither is "not a choice of two".
    160 pices by minute comes, 8% of reject (discarded pieces is acceptable), these pieces go to 13 box.

    Do you have a finite number of items, and a finite number of boxes?
    Say for example, 100 items need to be packed into 12 boxes, but you're only allowed to fill one box at once.
    No, no order, all itens can be distributed at any box in any time or order

  4. #4
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184
    This software run in this machine:

    YouTube

    Actually, I have a software working at other situations, but 200-380g with 270g average pieces, is a difficult case!

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,685
    Why do you need to reject any?

    If the current item doesn't fit in any box, just close the heaviest and start a fresh box.

    Or are you saying that every full box must be in the narrow window of 2000 to 2030 grams.
    30g seems an awfully small target to hit when the average random size is 10 times that.

    What happens in extreme cases where every box is just over 1840g (say 250*4 + 300*2 + 240) and is incapable of storing any item of any size without going overweight.

    Let's say you have 6 items in each of 12 boxes (72 in total). Can you use the distribution table?
    I mean, if you haven't seen a 370g item in the last 72, chances would seem to be high that one might be along soon.
    Or if you've seen two 370g items in the last 72, then you could pretty much discount the appearance of another one any time soon.
    In other words, match the current distribution of all the items you currently know about with your long-term average to help with decision making.

    Knapsack problem - Wikipedia
    Bin packing problem - Wikipedia
    Packing problems - Wikipedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184
    I did not express myself because of my short English.

    * Yes, all packages need be to 2000 - 2030 grams, reject is a option to discard pieces when no way to fit the package, even in cases not last piece on package.

    * Yes, 1840g block any chance to fit a package 2000-2030, the routine prevent this (rejecting pieces).

    * Current routine have a table with last n pieces and know how the most common pieces. (77% between 240g-300g)
    With only one low limit piece (200-240) or high limite piece (300-360) for each 6 pieces, is very difficult fit a package.
    The routine needs to select the middle parts well.


    For now, I'll also study these algorithms.... Thanks!

  7. #7
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184
    Apparently these algorithms serve to solve the same problem, but when we already know all the pieces available ...

    Which is not exacly my case.

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    I'd say that the best way would be to weigh the packages ahead of time so that you could use Salem's suggested algorithms.

    Going down a conveyor belt the order of the packages should remain constant, and you could slow down the speed so that you could look up to 100 packages ahead.

    You could then determine if any packages won't fit in any boxes and reject them before packing (saving time and boxes). These could then be sent back through the weighing...
    Fact - Beethoven wrote his first symphony in C

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,685
    A sort of template for experimenting with.
    Code:
    #include <iostream>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <ctime>
    #include <random>
    using namespace std;
    
    // Compile with g++ -std=c++11 foo.cpp
    
    const int numBins = 12;
    const int lowCapacity = 2000;
    const int highCapacity = 2030;
    
    void fillConveyorBelt(vector<int> &belt, int count = 1) {
        const int distribution[] = {
            2,7,19,34,24,7,3,2,2
        };
        const int baseWeight = 201;
        const int intervalWeight = 19;
        for ( int c = 0 ; c < count ; c++ ) {
            for ( size_t i = 0 ; i < sizeof(distribution)/sizeof(distribution[0]) ; i++ ) {
                int low = baseWeight + i * (intervalWeight+1);
                int high= low + intervalWeight;
                //cout << low << " " << high << " " << distribution[i] << endl;
                std::default_random_engine gen(time(NULL));
                std::uniform_int_distribution<int> dist(low,high);
                for ( int n = 0 ; n < distribution[i] ; n++ ) {
                    belt.push_back(dist(gen));
                }
            }
        }
    }
    
    class bin {
        vector< vector<int> >   bins;
        vector<int>             capacity;
    public:
        bin() :
            bins(numBins,vector<int>()),
            capacity(numBins,0)
            {
        }
        // add a piece to a bin, returning true if it was fitted.
        bool addPiece(int binNumber, int piece) {
            if ( checkPieceWillFit(binNumber,piece) ) {
                bins[binNumber].push_back(piece);
                capacity[binNumber] += piece;
                return true;
            } else {
                return false;
            }
        }
        // true if the piece will fit in a given bin
        bool checkPieceWillFit(int binNumber, int piece) {
            return capacity[binNumber] + piece <= highCapacity;
        }
        // true if the bin is optimally full
        bool binReadyForDispatch(int binNumber) {
            return capacity[binNumber] >= lowCapacity && capacity[binNumber] <= highCapacity;
        }
        // find the bin which is most empty
        int emptiestBin() {
            int empty = highCapacity;
            int id = 0;
            for ( int i = 0 ; i < numBins ; i++ ) {
                if ( capacity[i] < empty ) {
                    empty = capacity[i];
                    id = i;
                }
            }
            return id;
        }
        // Find the bin which is most full
        int fullestBin() {
            int full = 0;
            int id = 0;
            for ( int i = 0 ; i < numBins ; i++ ) {
                if ( capacity[i] > full ) {
                    full = capacity[i];
                    id = i;
                }
            }
            return id;
        }
        // The bin is judged to be full, so output the details and make it empty
        void dispatchBin(int binNumber) {
            cout << binNumber << "=" << capacity[binNumber] << ":";
            for ( size_t i = 0 ; i < bins[binNumber].size(); i++ ) {
                cout << bins[binNumber][i] << " ";
            }
            cout << endl;
            capacity[binNumber] = 0;
            bins[binNumber].resize(0);
        }
    };
    
    // Fill the bins in strict rotation
    class linear : public bin {
        int     binNumber;
    public:
        linear() :
            binNumber(0)
            {
        }
        void addPiece(int piece) {
            if ( bin::addPiece(binNumber,piece) ) {
                ;
            } else {
                // bin was full, empty it and add the piece
                dispatchBin(binNumber);
                bin::addPiece(binNumber,piece);
            }
            binNumber = (binNumber + 1) % numBins;
        }
    };
    
    // Best fit (bin with highest capacity)
    
    // Worst fit (bin with lowest capacity)
    
    // Probable fit (use cumulative histogram of all seen pieces to estimate the best bin)
    
    
    int main ( ) {
        vector<int> belt;
        fillConveyorBelt(belt,100);
        shuffle(belt.begin(),belt.end(),std::default_random_engine(time(NULL)));
        cout << belt.size() << endl;
        linear  l;
        for ( int i = 0 ; i < 300 ; i++ ) {
            l.addPiece(belt[i]);
        }
    }
    Having filled the conveyor belt with thousands of items matching your distribution profile, you can experiment with pulling items off the belt one at a time and trying different strategies for filling the bins.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Registered User
    Join Date
    Nov 2008
    Location
    Santa Catarina - Brasil
    Posts
    184
    Thanks you so much SALEM,

    Now I'm studying your code, as soon as possible I will comment about results....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. joining two pieces of code
    By sean146 in forum C Programming
    Replies: 1
    Last Post: 11-13-2016, 02:26 AM
  2. Differents results x86 and ARM
    By Eduardo Alfaia in forum C Programming
    Replies: 3
    Last Post: 01-21-2015, 08:46 PM
  3. sending JPGs in pieces?
    By chris24300 in forum C Programming
    Replies: 4
    Last Post: 01-15-2010, 08:04 AM
  4. copying differents maps
    By l2u in forum C++ Programming
    Replies: 20
    Last Post: 10-14-2008, 04:59 AM
  5. Using differents API in a program
    By gustavosserra in forum C++ Programming
    Replies: 2
    Last Post: 06-29-2003, 07:30 PM

Tags for this Thread