An Exact Algorithm for the Unbounded Knapsack Problem with Minimizing Maximum Processing Time
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.
DOI: https://doi.org/10.3844/jcssp.2007.138.143
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.
- 3,906 Views
- 5,412 Downloads
- 8 Citations
Download
Keywords
- Integer programming
- bounded and unbounded knapsack problems