Show simple item record

dc.contributor.authorQi, Michelle Bo 12:09:44 (GMT) 12:09:44 (GMT)
dc.description.abstractThe Bin Packing Problem (BPP) is an important optimization problem with many applications. Given a set of items with a certain weight and a set of bins with fixed capacity, the classical BPP seeks to pack the items into the minimum number of bins. In this thesis a variant of the BPP, the Bin Packing Problem with Fragile Objects (BPPFO), is studied. The BPPFO originates in telecommunication systems where cellphone calls are assigned to towers based on the noise level of calls and the tolerance level of each call in the channel.In this case, the calls are represented as objects that are characterized by a weight and a fragility parameter. The fragility parameter corresponds to the noise tolerance level of each call, and the weight corresponds to the noise produced by a call. As calls are assigned, the total noise produced within a channel can not exceed the lowest tolerance level among the calls. The less the tolerance level, the more fragile the line becomes. Hence, the capacity of the bin depends on the smallest fragility of any item packed in it. In this thesis, two new formulations are proposed. The first is based on the classical BPP formulation to which a Lagrangian relaxation is applied. Several heuristics are developed to find upper bounds, including a greedy heuristic. The second is a graph-based formulation that is solved directly. A standard data set is used for testing. It is found that the new formulation based on the classical BPP is more efficient in getting a Lagrangian lower bound and the greedy heuristic outperforms other heuristics in finding good quality upper bounds in very short computational times, especially with very large data instances.en
dc.publisherUniversity of Waterlooen
dc.subjectOperation Researchen
dc.subjectBin packing problemen
dc.titleThe Bin Packing Problem with Fragile Objects: Models and Solution Methodsen
dc.typeMaster Thesisen
dc.subject.programManagement Sciencesen Sciencesen
uws-etd.degreeMaster of Applied Scienceen

Files in this item


This item appears in the following Collection(s)

Show simple item record


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages