Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
Journal of Computer Science
Year: 2007  |  Volume: 3  |  Issue: 3  |  Page No.: 138 - 143

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.

View Fulltext    |   Related Articles   |   Back
  Related Articles

Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility