A DECISION SUPPORT SYSTEM BASED ON GENETIC ALGORITHM FOR VARIABLE SIZED BIN PACKING PROBLEM WITH ITEM CONFLICTS

Year 2017, Volume: 5 Issue: 1, 1 - 17, 14.07.2017

İnanç Kabasakal Fatma Demircan Keskin

https://doi.org/10.18825/iremjournal.272727

Abstract

In this paper, a variable sized bin
packing problem with conflicts is addressed. The problem includes assignment of
items to the variable sized bin categories considering weight and volume
capacity of bins while avoiding joint assignments of items that are in
conflict. The objective is to minimize the total cost of bins used to assign
all items. Bin packing problem, one of the classical combinatorial optimization
problems, is known to be NP-hard and thus, the variable sized bin packing
problem is NP hard as well. In the literature exact and approximation
algorithms are used to solve this problem. In this paper a model based on
Genetic Algorithm is proposed to provide decision support for variable sized
bin packing and related problems. The performance of the model is tested on the
derived problems and results are presented.

Keywords

Variable sized bin packing problem, Genetic Algorithm, item conflicts, decision support systems

A DECISION SUPPORT SYSTEM BASED ON GENETIC ALGORITHM FOR VARIABLE SIZED BIN PACKING PROBLEM WITH ITEM CONFLICTS

Abstract

Bin
packing problem (BPP) is a combinatorial NP-hard problem that has variations
including one, two and three dimensional packing, variable sized packing and
packing with constraints. In the literature, exact and approximation algorithms
have been mostly used to solve bin packing problems. Genetic Algorithms are meta-heuristic methods that
have been applied to a vast majority of well-known optimization problems
including the bin packing problems. In this paper, a variant of bin-packing
problem for variable bins is addressed. The capacity constraints including
volume and weight are given; moreover, to avoid item conflicts is defined as an
additional constraint. A decision support model utilizing the genetic algorithm
is introduced for this variant of the BPP. The performance of the model is tested with
sample input, the results obtained are presented and discussed in the results
section.

Keywords

Variable sized bin-packing problem, Genetic Algorithm, item conflicts, decision support systems

References

• Bang-Jensen, J. & Larsen, R. 2012. Efficient algorithms for real-life instances of the variable size bin packing problem. Computers & Operations Research, 39(11): 2848–2857.
• Belov, G. & Scheithauer, G. 2002. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. European Journal of Operational Research, 141(2): 274–294.
• Bodis, A. 2015. Bin packing with directed stackability conflicts. Acta Universitatis Sapientiae, Informatica, 7(1): 31-57.
• Correia, I., Gouveia, L., & Saldanha-da-Gama, F. 2008. Solving the variable size bin packing problem with discretized formulations. Computers & Operations Research, 35(6): 2103 – 2113.
• Epstein, L., & Levin, A. 2008. On bin packing with conflicts. SIAM Journal on Optimization, 19(3): 1270–1298.
• Epstein, L., Favrholdt, L. M., & Levin, A. 2011. Online variable-sized bin packing with conflicts. Discrete Optimization, 8(2): 333-343.
• Falkenauer, E. 1994. New Representation and Operators for GAs Applied to Grouping Problems. Evolutionary Computation, 2(2): 123-144.
• Falkenauer, E. 1996. A Hybrid Grouping Genetic Algorithm for Bin Packing. Journal of Heuristics, 2(1): 5-30.
• Friesen, D. K., & Langston, M. A. 1986. Variable sized bin-packing. SIAM Journal on Computing, 15(1): 222–230.
• Haouari, M., & Serairi, M. 2009. Heuristics for the variable sized bin-packing problem. Computers & Operations Research, 36(10): 2877-2884.
• Haouari, M., & Serairi, M. 2011. Relaxations and exact solution of the variable sized bin packing problem. Computational Optimization and Applications, 48(2): 345-368.
• Iima, H., & Yakawa, T. 2003. A New Design of Genetic Algorithm for Bin Packing. The Congress on Evolutionary Computation - CEC '03, 1044-1049.
• Jansen, K. 1999. An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization, 3(4): 363–377
• Kang, J., & Park, S. 2003. Algorithms for the variable sized bin packing problem. European Journal of Operational Research, 147(2): 365-372.
• Kinnersley, N. G., & Langston, M. A. 1988. Online Variable-Sized Bin Packing. Discrete Applied Mathematics, 22(2): 143-148.
• Korte B., & Vygen J. 2006. Bin-Packing, Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics. 21. Springer, 426–441.
• Li K., Liu H., Wu Y., & Xu X. 2014. A two-dimensional bin-packing problem with conflict penalties. International Journal of Production Research, 52(24): 7223-7238.
• Maiza M., Labed A., & Radjef M. S. 2013. Efficient algorithms for the offline variable sized bin-packing problem. Journal of Global Optimization, 57(3): 1025-1038.
• Martello, S., Pisinger, D., & Vigo, D. 2000. The Three Dimensional Bin Packing Problem. Operations Research, 48(2): 256-267.
• Mohamadi, N. 2010. Application of Genetic Algorithm for the Bin Packing Problem with a New Representation Scheme. Mathematical Sciences, 4(3): 253-266.
• Monacci, M. 2002. Algorithms for packing and scheduling problems. PhD thesis. Università di Bologna, Bologna.
• Quiroz-Castellanos, M., Cruz-Reyes, L., Torres-Jimenez, J., Gomez S., C., Huacuja, H.J.F., & Alvim, A.C.F. 2015. A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers & Operations Research, 55: 52–64.
• Reeves, C. 1996. Hybrid Genetic Algorithms for Bin-packing and Related Problems. Annals of Operations Research, 63(3): 371-396.
• Sadykov, R., & Vanderbeck, F. 2013. Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm. INFORMS Journal on Computing, 25(2): 244-255.