Close-Form Exact Algorithm for Minimizing Maximum Processing Time in the Unbounded Knapsack Problem
Article Sidebar
Main Article Content
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 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
Article Details
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
[2] S. Martello, D. Psinger, and P. Toth, Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem, Management Science, 45, 1999, 414-424.
[3] A. Freville and G. Plateau, Heuristics and Reduction Methods for Multiple Constraints Linear Programming, European Journal of Operations Research, 24, 1986, 206-215.
[4] D. Psinger, An Exact Algorithm for Large Multiple Knapsack Problem, European Journal of Operations Research, 114, 1999, 528-541.
[5] S. Martello, and P. Toth, A Branch-and-Bound Algorithm for the Zero-One Knapsack Problem, Discrete Applied Mathematics, 3, 1981, 275-288.
[6] D. Psinger, A Minimal Algorithm for the Multiple-Choice Knapsack Problem, European Journal of Operations Research, 83, 1995, 394-410.
[7] D. Psinger, Budgeting with Bound Multiple-Choice Constraints, European Journal of Operations Research, 129, 2001. 471-480.
[8] R. Andonow, V. Porriez, and S. Rajopadhye, Unbounded Knapsack Problem: Dynamic Programming Revised, European Journal of Operations Research, 123, 2000, 394-407.
[9] C. Srisuwannapa, and P. Charnsettikul, An Exact Algorithm for Solving the Unbounded Knapsack Problem with Minimizing Maximum Processing Time, Proceedings of Seminar in Applied Optimization, A Publication of Industrial Engineering Department, Faculty of Engineering, Kasetsart University, Bangkhen, Thailand, 2001, 83-89.
[10] C. Srisuwannapa, and P. Charnsettikul, Application of Coordinate Transformation with MMPTUKP of Minimzing Maximum Processinf Time in Unbounded Knapsack Problem, Proceedings of The 1st KMITL International Conferences on Integration of Science and Technology for Sustainable Development, KMITL, Ladkrabang, Bangkok, Thailand, 1, 2004, 25-28.
[11] C. Srisuwannapa, and P. Charnsettikul, Modified Exact Algorithms for Minimizing Maximum Processing Time in the Unbounded Knapsack Problem with, Proceedings of Meeting in Operation Researches in 2004, Industrial Engineering Department, Faculty of Engineering, Kasetsart University, Bangkhen, Thailand, 2004, 207-221.
