Close-Form Exact Algorithm for Minimizing Maximum Processing Time in the Unbounded Knapsack Problem

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 problem. The problem is a decision 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 (budget). In this paper, we proposed two new modified exact algorithms for this problem. The first algorithm, CFMMPTUKP algorithm, has applied the close-form method with the original algorithm. MMPTUKP, and the second one, CTCFMMPTUKP algorithm, has applied the coordinate transformation with CFMMPTUKP algorithms. We present computational experiments with 7 different type of problems for which data were generated to validate our ideas and demonstrate the efficiency of the proposed algorithms. It can be concluded that, for all type of problems, the proposed CTCFMMPTUKP algorithms performs in term of solution time better than the 5 other algorithms.

Keywords: Linear programming, Simplex method, Integer linear programming, Branch and bound algorithm, Unbounded and bounded knapsack problem, Processing time

Corresponding author: E-mail:  chanin_sri@yahoo.com