One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm

Niluka P. Rodrigo; Wasantha B. Daundasekera; Athula I. Perera

doi:doi:10.11648/j.dmath.20180302.12

| Peer-Reviewed

One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm

Niluka P. Rodrigo, Wasantha B. Daundasekera, Athula I. Perera

Published in International Journal of Discrete Mathematics (Volume 3, Issue 2)

Received: 28 March 2018 Accepted: 14 May 2018 Published: 2 June 2018

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

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.

Published in	International Journal of Discrete Mathematics (Volume 3, Issue 2)
DOI	10.11648/j.dmath.20180302.12
Page(s)	36-40
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2018. Published by Science Publishing Group

Keywords

BPP, MBBA, Python Software Package, Cartesian Coordinate Points

References

[1]	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.
[2]	T. Dokeroglu, A. Cosar, “Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms” Computers & Industrial Engineering 75 (2014) 176–186.
[3]	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”.
[4]	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.
[5]	Andrea L, Silvano M and Daniele V. “Recent Advances on two-dimensional bin packing Problems”, Elsevier Science, Discrete Applied Mathematics. 123 (2002), 379-396.
[6]	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.
[7]	Saad M. A. Suliman. “Pattern generating procedure for the cutting stock problem”, International Journal of Production Economics 74 (2001) 293-301.
[8]	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.
[9]	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).
[10]	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.
[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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Niluka P. Rodrigo, Wasantha B. Daundasekera, Athula I. Perera. (2018). One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. International Journal of Discrete Mathematics, 3(2), 36-40. https://doi.org/10.11648/j.dmath.20180302.12

Copy | Download

ACS Style

Niluka P. Rodrigo; Wasantha B. Daundasekera; Athula I. Perera. One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. Int. J. Discrete Math. 2018, 3(2), 36-40. doi: 10.11648/j.dmath.20180302.12

Copy | Download

AMA Style

Niluka P. Rodrigo, Wasantha B. Daundasekera, Athula I. Perera. One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. Int J Discrete Math. 2018;3(2):36-40. doi: 10.11648/j.dmath.20180302.12

Copy | Download

@article{10.11648/j.dmath.20180302.12,
  author = {Niluka P. Rodrigo and Wasantha B. Daundasekera and Athula I. Perera},
  title = {One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm},
  journal = {International Journal of Discrete Mathematics},
  volume = {3},
  number = {2},
  pages = {36-40},
  doi = {10.11648/j.dmath.20180302.12},
  url = {https://doi.org/10.11648/j.dmath.20180302.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.dmath.20180302.12},
  abstract = {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.},
 year = {2018}
}

Copy | Download

TY  - JOUR
T1  - One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm
AU  - Niluka P. Rodrigo
AU  - Wasantha B. Daundasekera
AU  - Athula I. Perera
Y1  - 2018/06/02
PY  - 2018
N1  - https://doi.org/10.11648/j.dmath.20180302.12
DO  - 10.11648/j.dmath.20180302.12
T2  - International Journal of Discrete Mathematics
JF  - International Journal of Discrete Mathematics
JO  - International Journal of Discrete Mathematics
SP  - 36
EP  - 40
PB  - Science Publishing Group
SN  - 2578-9252
UR  - https://doi.org/10.11648/j.dmath.20180302.12
AB  - 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.
VL  - 3
IS  - 2
ER  -

Copy | Download

Author Information

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

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Niluka P. Rodrigo, Wasantha B. Daundasekera, Athula I. Perera. (2018). One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. International Journal of Discrete Mathematics, 3(2), 36-40. https://doi.org/10.11648/j.dmath.20180302.12

Copy | Download

ACS Style

Niluka P. Rodrigo; Wasantha B. Daundasekera; Athula I. Perera. One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. Int. J. Discrete Math. 2018, 3(2), 36-40. doi: 10.11648/j.dmath.20180302.12

Copy | Download

AMA Style

Niluka P. Rodrigo, Wasantha B. Daundasekera, Athula I. Perera. One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm. Int J Discrete Math. 2018;3(2):36-40. doi: 10.11648/j.dmath.20180302.12

Copy | Download

@article{10.11648/j.dmath.20180302.12,
  author = {Niluka P. Rodrigo and Wasantha B. Daundasekera and Athula I. Perera},
  title = {One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm},
  journal = {International Journal of Discrete Mathematics},
  volume = {3},
  number = {2},
  pages = {36-40},
  doi = {10.11648/j.dmath.20180302.12},
  url = {https://doi.org/10.11648/j.dmath.20180302.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.dmath.20180302.12},
  abstract = {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.},
 year = {2018}
}

Copy | Download

TY  - JOUR
T1  - One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm
AU  - Niluka P. Rodrigo
AU  - Wasantha B. Daundasekera
AU  - Athula I. Perera
Y1  - 2018/06/02
PY  - 2018
N1  - https://doi.org/10.11648/j.dmath.20180302.12
DO  - 10.11648/j.dmath.20180302.12
T2  - International Journal of Discrete Mathematics
JF  - International Journal of Discrete Mathematics
JO  - International Journal of Discrete Mathematics
SP  - 36
EP  - 40
PB  - Science Publishing Group
SN  - 2578-9252
UR  - https://doi.org/10.11648/j.dmath.20180302.12
AB  - 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.
VL  - 3
IS  - 2
ER  -

Copy | Download