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

Öz

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.

Anahtar Kelimeler

• 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

Öz

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.

Anahtar Kelimeler

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

Kaynakça

1. 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.
2. 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.
3. Bodis, A. 2015. Bin packing with directed stackability conflicts. Acta Universitatis Sapientiae, Informatica, 7(1): 31-57.
4. 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.
5. Epstein, L., & Levin, A. 2008. On bin packing with conflicts. SIAM Journal on Optimization, 19(3): 1270–1298.
6. Epstein, L., Favrholdt, L. M., & Levin, A. 2011. Online variable-sized bin packing with conflicts. Discrete Optimization, 8(2): 333-343.
7. Falkenauer, E. 1994. New Representation and Operators for GAs Applied to Grouping Problems. Evolutionary Computation, 2(2): 123-144.
8. Falkenauer, E. 1996. A Hybrid Grouping Genetic Algorithm for Bin Packing. Journal of Heuristics, 2(1): 5-30.

9. Friesen, D. K., & Langston, M. A. 1986. Variable sized bin-packing. SIAM Journal on Computing, 15(1): 222–230.
10. Haouari, M., & Serairi, M. 2009. Heuristics for the variable sized bin-packing problem. Computers & Operations Research, 36(10): 2877-2884.
11. Haouari, M., & Serairi, M. 2011. Relaxations and exact solution of the variable sized bin packing problem. Computational Optimization and Applications, 48(2): 345-368.
12. Iima, H., & Yakawa, T. 2003. A New Design of Genetic Algorithm for Bin Packing. The Congress on Evolutionary Computation - CEC '03, 1044-1049.
13. Jansen, K. 1999. An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization, 3(4): 363–377
14. Kang, J., & Park, S. 2003. Algorithms for the variable sized bin packing problem. European Journal of Operational Research, 147(2): 365-372.
15. Kinnersley, N. G., & Langston, M. A. 1988. Online Variable-Sized Bin Packing. Discrete Applied Mathematics, 22(2): 143-148.
16. Korte B., & Vygen J. 2006. Bin-Packing, Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics. 21. Springer, 426–441.
17. 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.
18. 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.
19. Martello, S., Pisinger, D., & Vigo, D. 2000. The Three Dimensional Bin Packing Problem. Operations Research, 48(2): 256-267.
20. Mohamadi, N. 2010. Application of Genetic Algorithm for the Bin Packing Problem with a New Representation Scheme. Mathematical Sciences, 4(3): 253-266.
21. Monacci, M. 2002. Algorithms for packing and scheduling problems. PhD thesis. Università di Bologna, Bologna.
22. 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.
23. Reeves, C. 1996. Hybrid Genetic Algorithms for Bin-packing and Related Problems. Annals of Operations Research, 63(3): 371-396.
24. Sadykov, R., & Vanderbeck, F. 2013. Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm. INFORMS Journal on Computing, 25(2): 244-255.