Meta-RaPS: A randomized priority search applied to the bin packing problem

A recurring engineering problem associated with any manufacturing, production or distribution facility that packs and ships different products is the Bin Packing Problem. The objective of this problem is to find the minimum amount of bins or containers required to hold a set number of objects where each object has its own weight, dimension or size. The research contained within this thesis attempts to develop a method that finds near optimal or good solutions for bin packing problems while using only a small amount of computer time to solve.; The meta-heuristic approach, Meta-RaPS, used for this study is a general solution approach developed to solve combinatorial problems including the bin packing problem. Meta-RaPS allows the user to introduce randomness into known bin packing algorithms such as the First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) bin packing algorithms. The introduction of randomness creates better solutions than those found using the original algorithms.; Data sets with known optimal solutions were tested using the Meta-RaPS bin packing heuristic. In many cases, the answers obtained using the Meta-RaPS heuristics are better than those obtained using the basic FFD and BFD algorithms. A maximum improvement of five more optimal solutions can be found for the FFD and BID algorithms respectively when the MFFD and MBFD is used in their place.