I saw an interesting project on Guru.com to look at pallet packing efficiency. The client input had job numbers/quantities and they wanted an optimized pallet loading. The loading was based on a minimum/maximum pallet quantities with a criteria that a job quantity can’t be split across pallets (a job must ship together). The client also had a “desired” quantity, which really didn’t provide additional information. The goal was to develop an Excel VBA to provide the optimized pallet loading for what I assumed to be their daily output.
Although I haven’t worked on bin packing algorithms, this sounded a lot like memory allocation schemes, which I have implemented; first, best, and worst fit algorithms. I performed some basic research and found that bin packing solutions are similar to memory management allocation schemes. The bin packing algorithms include next-fit, first-fit, and best-fit algorithms. There are also variations of these algorithms that pre-sorts the data in decreasing quantities sizes before apply the algorithm.
The next-fit algorithm checks to see if the the current bin can hold the quantity. If so, then place that quantity in that bin, else place the quantity in a new bin. With the next-fit algorithm you never go back to an earlier bin.
The first-fit algorithm scans open bins in order and places the quantity in the first bin that will hold it. If the quantity doesn’t fit in any bin, then start a new bin. The best-fit scans all bins for the best fit, if it doesn’t fit in an existing bin, then start a new one. The decreasing algorithm versions have the quantities sorted by size, largest to smallest, and then the algorithm is run.
Although not seen in the literature, I also included a worst fit algorithm which is the opposite of the best-fit algorithm where bins are scanned for the worst fit (most space left after adding the quantity to the bin). If the quantity doesn’t fit in an existing bin, start a new one.
I created an Excel VBA to run some trials where I could vary different parameters and create constrained random values. Random parameters includes the number of jobs and quantities per job. Fixed parameters are the min/max quantity on a pallet (in a bin) and the number of trials. After each trial the most efficient solution was selected (least number of pallets/bins) that met the minimum pallet quantity (i.e. a solution with the minimum number of pallets wasn’t selected if any pallet quantity was below the minimum threshold).
After varying a number of parameters and using uniform random numbers, generally the best fit or best fit decreasing algorithm was the most favorable. This experiment did not account for processor speed. One would expect that best and worst fit algorithms to require the most processing power since every open bin needs to be examined prior to placing a job in a bin.
Anyware, LLC 