Show simple item record

dc.contributor.advisorAndradottir, Sigrun
dc.contributor.advisorGoldsman, David M.
dc.contributor.authorAsgeirsson, Agni
dc.date.accessioned2015-06-08T18:10:23Z
dc.date.available2015-06-09T05:30:07Z
dc.date.created2014-05
dc.date.issued2014-03-12
dc.date.submittedMay 2014
dc.identifier.urihttp://hdl.handle.net/1853/53413
dc.description.abstractThis thesis focuses on algorithms solving the on-line Bin-Covering problem, when the items are generated from a known, stationary distribution. We introduce the Prospect Algorithm. The main idea behind the Prospect Algorithm is to use information on the item distribution to estimate how easy it will be to fill a bin with small overfill as a function of the empty space left in it. This estimate is then used to determine where to place the items, so that all active bins either stay easily fillable, or are finished with small overfill. We test the performance of the algorithm by simulation, and discuss how it can be modified to cope with additional constraints and extended to solve the Bin-Packing problem as well. The Prospect Algorithm is then adapted to achieve perfect packing, yielding a new version, the Prospect+ Algorithm, that is a slight but consistent improvement. Next, a Markov Decision Process formulation is used to obtain an optimal Bin-Covering algorithm to compare with the Prospect Algorithm. Even though the optimal algorithm can only be applied to limited (small) cases, it gives useful insights that lead to another modification of the Prospect Algorithm. We also discuss two relaxations of the on-line constraint, and describe how algorithms that are based on solving the Subset-Sum problem are used to tackle these relaxed problems. Finally, several practical issues encountered when using the Prospect Algorithm in the real-world are analyzed, a computationally efficient way of doing the background calculations needed for the Prospect Algorithm is described, and the three versions of the Prospect Algorithm developed in this thesis are compared.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectBin-covering
dc.subjectBin-packing
dc.subjectAlgorithms
dc.subjectMarkov decision processies
dc.subjectMDP
dc.subjectSimulation
dc.subjectKnapsack
dc.subjectNext-fit
dc.subjectInspection theorem
dc.titleOn-line algorithms for bin-covering problems with known item distributions
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentIndustrial and Systems Engineering
dc.embargo.terms2015-05-01
thesis.degree.levelDoctoral
dc.contributor.committeeMemberKeskinocak, Pinar
dc.contributor.committeeMemberJensson, Pall
dc.contributor.committeeMemberKleywegt, Anton J.
dc.date.updated2015-06-08T18:10:23Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record