APPLICATIONS OF BIN PACKING MODELS THROUGH THE SUPPLY CHAIN

Year 2009, Volume: 1 Issue: 1, 11 - 19, 01.06.2009

Ugur Elııyı Deniz Tusel Elııyı

Abstract

The Bin Packing Problem is defined as the placement of a set of different-sized items into identical bins so that the number of bins used is minimized. Specific cases of the problem vary according to the dimensions of items/bins, priority and placement constraints, and the planning horizon. The problem has important applications in Supply Chain Management, including vehicle, container, pallet or cargo loading, cutting stock and trim loss problems, packaging design, resource allocation, load balancing, scheduling, project management and financial budgeting. This study reviews various bin packing models, solution approaches, and several applications through different stages of the supply chain

Keywords

Bin Packing Problem, Optimization, Supply Chain Management.

References

• Bansal, Nikhil, Jose R. Correa, Claire Kenyon and Maxim Sviridenko (2006), “Bin packing in multiple dimensions: inapproximability results and approximation schemes”, Mathematics of
• Operations Research, Vol. 31, pp. 31-49. Bischoff, E.E. (2006), “Three-dimensional packing of items with limited load bearing strength”,
• European Journal of Operational Research, Vol. 168, No. 3, pp. 952-966. Crainic, Teodor G., Guido Perboli and Roberto Tadei (2009), “TS2PACK: A two-level tabu search for the three-dimensional bin packing problem”, European Journal of Operational Research, Vol. , No. 3, pp. 744-760.
• Dósa, G., Y. He, (2006), “Bin packing problems with rejection penalties and their dual problems”,
• Information and Computation, Vol. 204, No. 5, pp. 795-815. Fekete, Sandor P. and Jörg Schepers (2004), “A combinatorial characterization of higher- dimensional orthogonal packing”, Mathematics of Operations Research, Vol. 29, No. 2, pp. 353
• Garey, Michael R., David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, New Jersey: W.H. Freeman.
• Gilmore, P.C. and R.E. Gomory (1963), “A linear programming approach to the cutting-stock problem part II”, Operations Research, Vol. 11, pp. 864-888.
• Hoffman, P. (1998), The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth, New York: Hyperion.
• Johnson, David S., A. Demers, J.D. Ullman, M.R. Garey and R.L. Graham (1974), “Worst-case performance bounds for simple one-dimensional packing algorithms”, SIAM Journal on Computing, Vol. 3, pp. 299-325.
• Kim, Jong-Kyou, H. Lee-Kwang and Seung W. Yoo (2001), “Fuzzy bin packing problem”, Fuzzy
• Sets and Systems, Vol. 120, No. 3, pp. 429-434. Martello, Silvano and Paolo Toth (1990), Knapsack Problems: Algorithms and Computer
• Implementations, Chichester: John Wiley & Sons. Martello, Silvano, David Pisinger and Daniele Vigo (2000), “The Three-Dimensional Bin Packing
• Problem”, Operations Research, Vol. 48, No. 2, pp. 256-267. Nasibov, Efendi N. (2004), “An Algorithm for Constructing an Admissible Solution to the Bin
• Packing Problem with Fuzzy Constraints”, Journal of Computer and Systems Sciences International, Vol. 43, No. 2, pp. 205-212. Pisinger, David (2002), “Heuristics for the container loading problem”, European Journal of
• Operational Research, Vol. 141, No. 2, pp. 382-392. Scheithauer, Guntram (1999), “LP-based bounds for the container and multi-container loading problem”, International Transactions in Operations Research, Vol. 6, pp. 199-213.
• Schumann, R., J. Behrens and J. Siemer (2005), “The potted plant packing problem”, (in: J. Sauer- Ed., Workshop Plan, Scheduling und Konfigurieren/Entwerfen), Koblenz: Universitat Koblenz
• Landau Fachbereich Informatik. Skiena, S.S. (1998), The Algorithm Design Manual, New York: Springer.
• Terno, Johannes, Guntram Scheithauer, Uta Sommerweiß and Jan Riehme (2000), “An efficient approach for the multi-pallet loading problem”, European Journal of Operational Research, Vol. , No. 2, pp. 372-381.
• Wäscher, Gerhard and T. Gau (1996), “Heuristics for the Integer one-dimensional cutting stock problem: a computational study”, OR Spectrum, Vol.18, pp. 131-144.