A particle swarm optimization approach to the nonlinear resource allocation problem. (English) Zbl 1127.90417
Summary: The resource allocation problem seeks to find an optimal allocation of a limited amount of resource to a number of activities for optimizing the objective under the resource constraint. Most existing methods use mathematical programming techniques, but they may fail to derive exact solutions for large-sized problems with reasonable time. An alternative is to use meta-heuristic algorithms for obtaining approximate solutions. This paper presents a particle swarm optimization (PSO) algorithm for conquering the nonlinear resource allocation problem. To ensure the resource constraint is satisfied, we propose adaptive resource bounds for guiding the search. The experimental results manifest that the proposed method is more effective and efficient than a genetic algorithm. The convergence behavior of the proposed method is analyzed by observing the variations of particle entropy. Finally, a worst-case analysis is conducted to provide a reliable performance guarantee.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B90 | Case-oriented studies in operations research |
Keywords:
nonlinear resource allocation problem; adaptive resource bounds; particle swarm optimization; genetic algorithm; mathematical programmingReferences:
| [1] | Luss, H.; Gupta, S. K., Allocation of effort resource among competing activities, Operations Research, 23, 360-366 (1975) · Zbl 0298.90015 |
| [2] | Basso, A.; Peccati, L. A., Optimal resource allocation with minimum activation levels and fixed costs, European Journal of Operational Research, 131, 536-549 (2001) · Zbl 1161.91423 |
| [3] | Dai, Y. S.; Xie, M.; Poh, K. L.; Yang, B., Optimal testing – resource allocation with genetic algorithm for modular software systems, The Journal of Systems and Software, 66, 47-55 (2003) |
| [4] | Berman, O.; Cutler, M., Resource allocation during tests for optimally reliable software, Computers and Operations Research, 31, 1847-1865 (2004) · Zbl 1068.68046 |
| [5] | A. Ernst, H. Hiang, M. Krishnamoorthy, Mathematical programming approaches for solving task allocation problems, in: Proceedings of the 16th National Conference of Australian Society of Operations Research, 2001.; A. Ernst, H. Hiang, M. Krishnamoorthy, Mathematical programming approaches for solving task allocation problems, in: Proceedings of the 16th National Conference of Australian Society of Operations Research, 2001. |
| [6] | Yin, P. Y.; Yu, S. S.; Wang, P. P.; Wang, Y. T., A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems, Computer Standards and Interfaces, 28, 441-450 (2006) |
| [7] | Johannesson, M.; Weinstein, M. C., On the decision rules of cost-effectiveness analysis, Journal of Health Economics, 12, 459-467 (1993) |
| [8] | Stinnett, A. A.; Paltiel, A. D., Mathematical programming for the efficient allocation of health care resource, Journal of Health Economics, 15, 641-653 (1996) |
| [9] | Ibaraki, T.; Katoh, N., Resource Allocation Problems: Algorithmic Approaches (1988), MIT Press: MIT Press Boston · Zbl 0786.90067 |
| [10] | Birch, S.; Gafni, A., Cost effectiveness analysis: Do current decision rules lead us where we want to be?, Journal of Health Economics, 11, 279-296 (1992) |
| [11] | Lai, K. K.; Li, L., A dynamic approach to multiple-objective resource allocation problem, European Journal of Operational Research, 117, 293-309 (1999) · Zbl 0998.90516 |
| [12] | Morales, D.; Almeida, F.; Garcia, F.; Roda, J. L.; Rodriguez, C., Design of parallel algorithms for the single resource allocation problem, European Journal of Operational Research, 126, 166-174 (2000) · Zbl 0969.90058 |
| [13] | Bretthauer, K. M.; Shetty, B., The nonlinear resource allocation problem, Operations Research, 43, 670-683 (1995) · Zbl 0857.90090 |
| [14] | Bretthauer, K. M.; Shetty, B., A pegging algorithm for the nonlinear resource allocation problem, Computers and Operations Research, 29, 505-527 (2002) · Zbl 0995.90057 |
| [15] | Mathur, K.; Salkin, H.; Mohanty, B., A note on a general non-linear knapsack problem, Operations Research Letters, 79-81 (1986) · Zbl 0601.90114 |
| [16] | Hochbaum, D. S., A nonlinear knapsack problem, Operations Research Letters, 103-110 (1995) · Zbl 0838.90092 |
| [17] | Hou, Y. C.; Chang, Y. H., A new efficient encoding mode of genetic algorithms for the generalized plant allocation problem, Journal of Information Science and Engineering, 20, 1019-1034 (2004) |
| [18] | Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1997), Addison Wesley: Addison Wesley Reading, MA |
| [19] | Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [20] | Glover, F., Tabu search - Part I, ORSA Journal of Computing, 1, 190-206 (1989) · Zbl 0753.90054 |
| [21] | M. Dorigo, Optimization, learning, and natural algorithms, Ph.D. Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy, 1992.; M. Dorigo, Optimization, learning, and natural algorithms, Ph.D. Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy, 1992. |
| [22] | J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Conference on Neural Networks, vol. IV, 1995, pp. 1942-1948.; J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Conference on Neural Networks, vol. IV, 1995, pp. 1942-1948. |
| [23] | R.C. Eberhart, Y. Shi, Evolving artificial neural networks, in: Proceedings of the International Conference on Neural Networks and Brain, 1998, pp. PL5-PL13.; R.C. Eberhart, Y. Shi, Evolving artificial neural networks, in: Proceedings of the International Conference on Neural Networks and Brain, 1998, pp. PL5-PL13. |
| [24] | V. Tandon, Closing the gap between CAD/CAM and optimized CNC end milling, Master thesis, Purdue School of Engineering and Technology, Indiana University, Purdue University, Indianapolis, 2000.; V. Tandon, Closing the gap between CAD/CAM and optimized CNC end milling, Master thesis, Purdue School of Engineering and Technology, Indiana University, Purdue University, Indianapolis, 2000. |
| [25] | H. Yoshida, K. Kawata, Y. Fukuyama, Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage stability, in: Proceedings of the International Conference on Intelligent System Application to Power Systems, 1999, pp. 117-121.; H. Yoshida, K. Kawata, Y. Fukuyama, Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage stability, in: Proceedings of the International Conference on Intelligent System Application to Power Systems, 1999, pp. 117-121. |
| [26] | Shigenori, N.; Takamu, G.; Toshiku, Y.; Yoshikazu, F., A hybrid particle swarm optimization for distribution state estimation, IEEE Transaction on Power Systems, 18, 60-68 (2003) |
| [27] | Clerc, M.; Kennedy, J., The particle swarm explosion, stability, and convergence in a multidimensional complex space, IEEE Transaction on Evolutionary Computation, 6, 58-73 (2002) |
| [28] | J.Y. Wang, A study on the resource allocation problem using swarm intelligence, Master thesis, National Chi-Nan University, Taiwan, 2005.; J.Y. Wang, A study on the resource allocation problem using swarm intelligence, Master thesis, National Chi-Nan University, Taiwan, 2005. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
