Dergiler / International Review of Economics and Management / 2017 / Cilt: 5 - Sayı: 1
A DECISION SUPPORT SYSTEM BASED ON GENETIC ALGORITHM FOR VARIABLE SIZED BIN PACKING PROBLEM WITH ITEM CONFLICTS
- Sayfa
- 1–17
- DOI
- —
Özet
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.
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.