On-line algorithms for bin-covering problems with known item distributions

Bin-covering;Bin-packing;Algorithms;Markov decision processies;MDP;Simulation;Knapsack;Next-fit;Inspection theorem

Asgeirsson, Agni ; Andradottir, Sigrun Goldsman, David M. Industrial and Systems Engineering Keskinocak, Pinar Jensson, Pall Kleywegt, Anton J. ; Andradottir, Sigrun

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Bin-covering;    Bin-packing;    Algorithms;    Markov decision processies;    MDP;    Simulation;    Knapsack;    Next-fit;    Inspection theorem;   

Others  :  https://smartech.gatech.edu/bitstream/1853/53413/1/ASGEIRSSON-DISSERTATION-2014.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

This thesis focuses on algorithms solving the on-line Bin-Covering problem, whenthe items are generated from a known, stationary distribution. We introduce theProspect Algorithm.The main idea behind the Prospect Algorithm is to useinformation 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 extendedto 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 totackle 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.