International Journal of Discrete Mathematics

| Peer-Reviewed |

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

Received: Mar. 28, 2018    Accepted: May 14, 2018    Published: Jun. 02, 2018
Views:       Downloads:

Share This Article

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.

DOI 10.11648/j.dmath.20180302.12
Published in International Journal of Discrete Mathematics ( Volume 3, Issue 2, June 2018 )
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), 2024. 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
  • 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://download.sciencepg.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
  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

  • Section