One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm
International Journal of Discrete Mathematics
Volume 3, Issue 2, June 2018, Pages: 36-40
Received: Mar. 28, 2018;
Accepted: May 14, 2018;
Published: Jun. 2, 2018
Views 1363 Downloads 136
Niluka P. Rodrigo, Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka
Wasantha B. Daundasekera, Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka
Athula I. Perera, Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka
Follow on us
In this paper, our objective is to develop a mathematical formulation of solving the Bin Packing Problem (BPP) with different sizes of box. It has become one of the most important mathematical applications throughout the time. In our study, Modified Branch and Bound Algorithm (MBBA) is developed to generate all the feasible packing patterns of given boxes to required containers for One-Dimensional BPP. Further development of algorithms was made to ascertain the locations of each box within the containers by using Cartesian coordinate system. Developed algorithms are coded and programmed in the Python programming environment to generate feasible packing patterns.
BPP, MBBA, Python Software Package, Cartesian Coordinate Points
To cite this article
Niluka P. Rodrigo,
Wasantha B. Daundasekera,
Athula I. Perera,
One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm, International Journal of Discrete Mathematics.
Vol. 3, No. 2,
2018, pp. 36-40.
Copyright © 2018 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/
) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Jatinder N. D Gupta and Johnny C. “A new heuristic algorithm for the one-dimensional bin-packing problem”, Production planning and Control, ISSN 0953-7287(1999), Vol. 10, No. 6, 598-603.
T. Dokeroglu, A. Cosar, “Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms” Computers & Industrial Engineering 75 (2014) 176–186.
Mukhacheva E. A, G. N Belov, V. M. Kartack and Mukhacheva A. S. “Linear one-dimensional cutting-packing problems: Numerical experiments with the sequential value, Correction Method and a modified Branch and Bound method”.
Fleszar K. and Khalil S. “New Heuristics for one-dimensional bin packing”, Research-Gate: Computers and Operations Research, DOI: 10.1016/S0305-0548(00)00082-4.
Andrea L, Silvano M and Daniele V. “Recent Advances on two-dimensional bin packing Problems”, Elsevier Science, Discrete Applied Mathematics. 123 (2002), 379-396.
Christian B. and Verena S. “Solving the 2D bin packing problem by means of a Hybrid Evolutionary Algorithm”, Elsevier, International Conference on Computational Science, ICCS (2013), 899-908.
Saad M. A. Suliman. “Pattern generating procedure for the cutting stock problem”, International Journal of Production Economics 74 (2001) 293-301.
W. N. P. Rodrigo, W. B. Daundasekara and A. A. I. Perera. “Pattern Generationfor Two-Dimensional Cutting Stock Problem”, International Journal of Mathematics Trends and Technology, Vol. 3, Issue 2: 54-62.
W. N. P. Rodrigo, W. B. Daundasekara and A. A. I. Perera. “Pattern Generation for Two-Dimensional Cutting Stock Problem with Location”, Indian Journal of Computer Science and Engineering (IJCSE), Vol. 3, No 2, April-May 2012, 354-368 (www.academia.edu/4463690/INDJCSE12-03-02-082).
W. N. P. Rodrigo, W. B. Daundasekara and A. A. I. Perera. “Modified Method for One-Dimensional Cutting Stock Problem”, Software Engineering. Vol. 3, No. 3, 2015, pp. 12- 17. doi: 10.11648/j.se.20150303.11.
Niluka Rodrigo, Sium Shashikala. “One-Dimensional Cutting Stock Problem with Cartesian Coordinate Points”, International Journal of Systems Science and Applied Mathematics. Vol. 2, No. 5, 2017, pp. 99-104. doi: 10.11648/j.ijssam.20170205.14.