A Heuristic Algorithm for Resource Allocation/Reallocation Problem
This paper presents a 1-opt heuristic approach to solve resource allocation/reallocation problem which is known as 0/1 multichoice multidimensional knapsack problem (MMKP). The intercept matrix of the constraints is employed to find optimal or near-optimal solution of the MMKP. This heuristic appro...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2011/218078 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832565087106236416 |
|---|---|
| author | S. Raja Balachandar K. Kannan |
| author_facet | S. Raja Balachandar K. Kannan |
| author_sort | S. Raja Balachandar |
| collection | DOAJ |
| description | This paper presents a 1-opt heuristic approach to solve resource allocation/reallocation problem which is known as 0/1 multichoice multidimensional knapsack problem (MMKP). The intercept matrix of the constraints is employed to find optimal or near-optimal solution of the MMKP. This heuristic approach is tested for 33 benchmark problems taken from OR library of sizes upto 7000, and the results have been compared with optimum solutions. Computational complexity is proved to be 𝑂(𝑘𝑙𝑚𝑛2) of solving heuristically MMKP using this approach. The performance of our heuristic is compared with the best state-of-art heuristic algorithms with respect to the quality of the solutions found. The encouraging results especially for relatively large-size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems. |
| format | Article |
| id | doaj-art-315d4c7ec2aa40829a0d0aa4e39b6aa6 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2011-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-315d4c7ec2aa40829a0d0aa4e39b6aa62025-02-03T01:09:13ZengWileyJournal of Applied Mathematics1110-757X1687-00422011-01-01201110.1155/2011/218078218078A Heuristic Algorithm for Resource Allocation/Reallocation ProblemS. Raja Balachandar0K. Kannan1Department of Mathematics, School of Humanities & Sciences, SASTRA University, Tamil Nadu, Thanjavur 613401, IndiaDepartment of Mathematics, School of Humanities & Sciences, SASTRA University, Tamil Nadu, Thanjavur 613401, IndiaThis paper presents a 1-opt heuristic approach to solve resource allocation/reallocation problem which is known as 0/1 multichoice multidimensional knapsack problem (MMKP). The intercept matrix of the constraints is employed to find optimal or near-optimal solution of the MMKP. This heuristic approach is tested for 33 benchmark problems taken from OR library of sizes upto 7000, and the results have been compared with optimum solutions. Computational complexity is proved to be 𝑂(𝑘𝑙𝑚𝑛2) of solving heuristically MMKP using this approach. The performance of our heuristic is compared with the best state-of-art heuristic algorithms with respect to the quality of the solutions found. The encouraging results especially for relatively large-size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems.http://dx.doi.org/10.1155/2011/218078 |
| spellingShingle | S. Raja Balachandar K. Kannan A Heuristic Algorithm for Resource Allocation/Reallocation Problem Journal of Applied Mathematics |
| title | A Heuristic Algorithm for Resource Allocation/Reallocation Problem |
| title_full | A Heuristic Algorithm for Resource Allocation/Reallocation Problem |
| title_fullStr | A Heuristic Algorithm for Resource Allocation/Reallocation Problem |
| title_full_unstemmed | A Heuristic Algorithm for Resource Allocation/Reallocation Problem |
| title_short | A Heuristic Algorithm for Resource Allocation/Reallocation Problem |
| title_sort | heuristic algorithm for resource allocation reallocation problem |
| url | http://dx.doi.org/10.1155/2011/218078 |
| work_keys_str_mv | AT srajabalachandar aheuristicalgorithmforresourceallocationreallocationproblem AT kkannan aheuristicalgorithmforresourceallocationreallocationproblem AT srajabalachandar heuristicalgorithmforresourceallocationreallocationproblem AT kkannan heuristicalgorithmforresourceallocationreallocationproblem |