Bounded-space online bin cover

In this paper, we look at the online bounded-space bin cover problem and show how we can use the language of Markov chains to model and analyze the problem. We will use the insights given by the Markov chains to design an algorithm for the online bounded-space bin cover problem. The algorithm is a h...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2009-10, Vol.12 (5), p.461-474
Main Authors: Asgeirsson, Eyjolfur Ingi, Stein, Cliff
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Boxes
Business and Management
Calculus of Variations and Optimal Control
Optimization
Markov analysis
Operations Research/Decision Theory
Optimization
Packing problem
Performance evaluation
Studies
Supply Chain Management
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we look at the online bounded-space bin cover problem and show how we can use the language of Markov chains to model and analyze the problem. We will use the insights given by the Markov chains to design an algorithm for the online bounded-space bin cover problem. The algorithm is a heuristic that we create by simplifying the Markov chain. We also show how we can use simple methods to improve the efficiency of the algorithm. Finally, we will analyze our algorithm and compare it to a well known online bin cover algorithm.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-009-0116-x