Bi-objective bin packing problems

Download

index.pdf

Date

2003

Author

Ilıcak, Işıl

Metadata

Show full item record

Item Usage Stats

117
views

0
downloads

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 developing our solution approaches. For both problems, we propose exact procedures that generate efficient solutions relative to two objectives. To increase the efficiency of the solutions, we propose some lower and upper bounding procedures. The results of our experiments show that total overdeviation problem is easier to solve compared to maximum overdeviation problem and the bin capacity, the weight of items and the number of items are important factors that effect the solution time and quality. Our procedures can solve the problems with up to 100 items in reasonable solution times.

Subject Keywords

Packaging, Efficiency industrial, Industrial engineering

URI

http://etd.lib.metu.edu.tr/upload/2/1079987/index.pdf
https://hdl.handle.net/11511/13828

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

The general lot sizing and scheduling problem with sequence dependent changeovers Koçlar, Ayşe; Süral, Haldun; Department of Industrial Engineering (2005) In this study, we consider the General Lot Sizing and Scheduling Problem in single level capacitated environments with sequence dependent item changeovers. Process industries may be regarded as suitable application areas of the problem. The focus on capacity utilization and intensively time consuming changeovers necessitate the integration of lot sizing and sequencing decisions in the production plan. We present a mathematical model which captures the essence of cases in the most generic and realistic setti...
A variable neighborhood search procedure for the combined location with partial coverage and selective traveling salesman problem Rahim, Fatih; Sepil, Canan; Department of Industrial Engineering (2010) In this study, a metaheuristic procedure, particularly a variable neighborhood search procedure, is proposed to solve the combined location and selective traveling salesman problem in glass recycling. The collection of used glass is done by a collecting vehicle that visits a number of predefined collection centers, like restaurants and hospitals that are going to be referred to as compulsory points. Meanwhile, it is desired to locate a predetermined number of bottle banks to residential areas. The aim is to...
The cardinality constrained multiple knapsack problem Aslan, Murat; Azizoğlu, Meral; Department of Industrial Engineering (2008) The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce. In this study we consider the cardinality constra...
Monitoring high quality processes: a study of estimation errors on the time-between-events exponentially weighted moving average schemes Özsan, Güney; Köksal, Gülser; Department of Industrial Engineering (2008) In some production environments the defect rates are considerably low such that measurement of fraction of nonconforming items reaches parts per million level. In such environments, monitoring the number of conforming items between consecutive nonconforming items, namely the time between events (TBE) is often suggested. However, in the design of control charts for TBE monitoring a common practice is the assumptions of known process parameters. Nevertheless, in many applications the true values of the proces...
A lagrangean heuristic for the two-stage modular capacitated facility location problem Sevinç, Selim; Meral, Fatma Sedef; Department of Industrial Engineering (2008) In this study, a Lagrangean heuristic based on Lagrangean relaxation and subgradient optimization is proposed for the two-stage modular capacitated facility location problem. The objective is to minimize the cost of locating and operating plants and warehouses, plus the cost of transporting goods at both echelons to satisfy the demand of customers. The difference of our study from the two-stage capacitated facility location problem is the existence of multiple capacity levels as a candidate for each plant i...

Citation Formats

I. Ilıcak, “Bi-objective bin packing problems,” M.S. - Master of Science, Middle East Technical University, 2003.