Optimizing memory using knapsack algorithm

Loading...
Thumbnail Image
Date
July 2015
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Knapsack problem model is a general resource allocation model in which a single resource is assigned to a number of alternatives with the aim of maximizing the total return. Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem. The study was about how to select contending data/processes to be loaded to memory to enhance maximization of memory utilization and efficiency. The instance is modeled as 0 – 1 single knapsack problem. In this thesis a Dynamic Programming (DP) algorithm is proposed for the 0/1 one dimensional knapsack problem. Problem-specific knowledge is incorporated in the algorithm description and evaluation of parameters, in order to look into the performance of finite-time implementation of Dynamic Programming. Computer implementation considerations played an important role in its development. We test the presented method with a set of benchmark data and compare the obtained results with other existing heuristics. The proposed method appears to give good results when solving these problems unravelling all instance considered in this study to optimality in "reasonable" computation times. Computational results also shows that the more the number of items or processes, the higher the time to produce optimal results. Conclusively, when the curse of dimensionality can be dismissed, dynamic programming can be a useful procedure for large sequencing problems
Description
A thesis submitted in partial fulfilment of the Requirement for the degree Master of Philosophy (Information Technology).
Keywords
Citation