Bicriteria bin packing problem with deviation based objectives

Öylek, Ayla
In this thesis, two bicriteria bin packing problems are addressed. Bin packing problem is an NP-hard combinatorial optimization problem. Items with different weights are packed into bins with limited capacity in order to minimize the required number of bins. Objectives of the first problem are minimizing the number of bins and minimizing the total overdeviation. In the second problem, minimization of the number of bins and minimization of the maximum overdeviation are two conflicting objectives. For the solutions of the problems mixed integer linear programming models are formulated and used to find all nondominated objective vectors. The upper bounds and lower bounds are developed on the objective function values and bounds are incorporated into the mathematical models to increase the solution efficiency of the models. Computational results show that the problem with up to 100 items could be solved for high capacity bins. The problems with up to 75 items can be solved when the capacity is low.