Solved

Algorithm Building and Rebuilding Pallets

Posted on 2012-03-22
4
489 Views
Last Modified: 2012-08-13
I need an algorithm to build or rebuild pallets.  It's pretty straight forward.  200 boxes per pallet, all boxes the same size.  So, all I have to worry about is building as few pallets as possible.

An example:
Product #1, 100
Product #2, 73
Product #3, 48
etc.

They don't want products put on different pallets, so the 48 can't be split into 27 on one pallet and 21 on another.   I was going to just sort by qty and keep adding until I can't add anything else to the pallet (in this case, pallet #1 would have 173 and #2 would have 48).  This is an easy algorithm, but that won't build the most efficient pallets.

Any ideas?  

Thanks!
0
Comment
Question by:gebigler
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
4 Comments
 
LVL 8

Expert Comment

by:gpizzuto
ID: 37754730
This is a so-called "knapsack problem 0-1".
What you described is a Greedy Algorhitm:
Take ever the maximum box available that fits the remaining space on the pallet.
This algorhitm is not the best, but is best "locally" (in each step takes the best choice)

If you want the best solution you have to use Dynamic Programming (DP) .

have a look at:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm
0
 
LVL 4

Accepted Solution

by:
petr_hlucin earned 175 total points
ID: 37754812
This problem is NP-hard which (explained in a simple way) means that we don't know about polynomial algorithm which solves this problem. If you needed the most optimal solution the algorithm would be probably O(m^n) where m is pallettes count and n is boxes set count.

However an approximative solution would be like this:
sort sets of goods according to the size
while sets of goods are remaining do
  while largest set fits onto the current pallette
    put the largest set on the current pallette
  end while
  while smallest set fits onto the current pallette
    put the largest set from the remaining sets on the current pallette
  end while
  ship pallette
end while

For the test data the algorithm would work like this:
- put 100
- put 48
- ship pallette with 148
- put 73
- whip pallette with 73
0
 

Author Closing Comment

by:gebigler
ID: 37766644
This will meet the need.  Thanks!
0
 
LVL 8

Expert Comment

by:gpizzuto
ID: 37766709
As you said,
This is an easy algorithm, but that won't build the most efficient pallets.

This because Greedy algorithm is optimal ONLY locally... and IS NOT the best solution !!!
Best wishes.
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question