Bicriteria bin packing problem with deviation based objectives

Download

index.pdf

Date

2015

Author

Öylek, Ayla

Metadata

Show full item record

Item Usage Stats

212
views

72
downloads

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.

Subject Keywords

Industrial engineering, Deviation (Mathematics)., Mathematical optimization., Operations research., Packaging.

URI

http://etd.lib.metu.edu.tr/upload/12619550/index.pdf
https://hdl.handle.net/11511/25281

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Assembly line balancing with multi-manned tasks Esin, Ceyhan Erdem; Kırca, Ömer; Department of Industrial Engineering (2007) In this thesis, we define a new problem area for assembly lines. In the literature, there are various studies on assembly line balancing, but none of them consider multi-manned tasks, task to which at least two operators have to be assigned. Two mathematical models and one constraint programming model are developed for both Type-I and Type-II ALB problems. The objective of Type-I problem is to minimize the number of stations whereas the objective of Type-II problem is to minimize the cycle time. In addition...
Bi-objective bin packing problems Ilıcak, Işıl; Karasakal, Esra; Azizoğlu, Meral; Department of Industrial Engineering (2003) In this study, we consider two bi-objective bin packing problems that assign a number of weighted items to bins having identical capacities. Firstly, we aim to minimize total deviation over bin capacity and minimize number of bins. We show that these two objectives are conflicting. Secondly, we study the problem of minimizing maximum overdeviation and minimizing the number of bins. We show the similarities of these two problems to parallel machine scheduling problems and benefit from the results while devel...
On the generalizations and properties of Abramovich-Wickstead spaces Polat, Faruk; Alpay, Şafak; Department of Mathematics (2008) In this thesis, we study two problems. The first problem is to introduce the general version of Abramovich-Wickstead type spaces and investigate its order properties. In particular, we study the ideals, order bounded sets, disjointness properties, Dedekind completion and the norm properties of this Riesz space. We also define a new concrete example of Riesz space-valued uniformly continuous functions, denoted by CDr0 which generalizes the original Abramovich-Wickstead space. It is also shown that similar sp...
Multidimensional assortment problem with an application Tripathy, A; Süral, Haldun; Gerchak, Y (1999-05-01) This paper addresses the discrete multidimensional assortment problem. Assortment issues arise frequently in practice as an important design and inventory problem which simultaneously seeks the answers to two related questions: (a) Which items (or sizes of a product) to stock? (b) How much of each to stock? its discrete multidimensional version concerns itself with choosing sizes from among a discrete set of possible ones with each size being characterized by more than one dimension. Our research is motivat...
A heuristic approach for the single machine scheduling tardiness problems Özbakır, Saffet İlker; Kırca, Ömer; Department of Industrial Engineering (2011) In this thesis, we study the single machine scheduling problem. Our general aim is to schedule a set of jobs to the machine with a goal to minimize tardiness value. The problem is studied for two objectives: minimizing total tardiness value and minimizing total weighted tardiness value. Solving optimally this problem is difficult, because both of the total tardiness problem and total weighted tardiness problem are NP-hard problems. Therefore, we construct a heuristic procedure for this problem. Our heuristi...

Citation Formats

A. Öylek, “Bicriteria bin packing problem with deviation based objectives,” M.S. - Master of Science, Middle East Technical University, 2015.