Research Article Open Access

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

Chanin Srisuwannapa and Peerayuth Charnsethikul

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.

Journal of Computer Science
Volume 3 No. 3, 2007, 138-143

DOI: https://doi.org/10.3844/jcssp.2007.138.143

Submitted On: 21 December 2006 Published On: 31 March 2007

How to Cite: Srisuwannapa, C. & Charnsethikul, P. (2007). An Exact Algorithm for the Unbounded Knapsack Problem with Minimizing Maximum Processing Time . Journal of Computer Science, 3(3), 138-143. https://doi.org/10.3844/jcssp.2007.138.143

  • 3,301 Views
  • 5,016 Downloads
  • 8 Citations

Download

Keywords

  • Integer programming
  • bounded and unbounded knapsack problems