Journal of Computer Science

An Exact Algorithm for the Unbounded Knapsack Problem with Minimizing Maximum Processing Time

Chanin Srisuwannapa and Peerayuth Charnsethikul

DOI : 10.3844/jcssp.2007.138.143

Journal of Computer Science

Volume 3, Issue 3

Pages 138-143

Abstract

We address a variant of the unbounded knapsack problem (UKP) into which the processing time of each item is also put and considered, referred as MMPTUKP. The MMPTUKP is a decision problem of allocating amount of n items, such that the maximum processing time of the selected items is minimized and the total profit is gained as at least as determined without exceeding capacity of knapsack. In this study, we proposed a new exact algorithm for this problem, called MMPTUKP algorithm. This pseudo polynomial time algorithm solves the bounded knapsack problem (BKP) sequentially with the updated bounds until reaching an optimal solution. We present computational experience with various data instances randomly generated to validate our ideas and demonstrate the efficiency of the proposed algorithm.

Copyright

© 2007 Chanin Srisuwannapa and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.