×

zbMATH — the first resource for mathematics

Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities. (English) Zbl 1403.90654
Summary: This paper deals with a stochastic multi-period task-resource allocation problem. A team of agents with a set of resources is to be deployed on a multi-period mission with the goal to successfully complete as many tasks as possible. The success probability of an agent assigned to a task depends on the resources available to the agent. Unsuccessful tasks can be tried again at later periods. While the problem can in principle be solved by dynamic programming, in practice this is computationally prohibitive except for tiny problem sizes. To be able to tackle also larger problems, we propose a construction heuristic that assigns agents and resources to tasks sequentially, based on the estimated marginal utility. Based on this heuristic, we furthermore propose various approximate dynamic programming approaches and an evolutionary algorithm. All suggested approaches are empirically compared on a number of randomly generated problem instances. We show that the construction heuristic is very fast and provides good results. For even better results, at the expense of longer computational time, approximate dynamic programming seems a suitable alternative.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C39 Dynamic programming
90C40 Markov and semi-Markov decision processes
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahner, D. K.; Parson, C. R., Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming, Optimization Letters, 9, 8, 1689-1701, (2015) · Zbl 1335.90109
[2] Ahuja, R. K.; Kumar, A.; Jha, K. C.; Orlin, J. B., Exact and heuristic algorithms for the weapon-target assignment problem, Operations Research, 55, 6, 1136-1146, (2007) · Zbl 1167.90555
[3] Alighanbari, M.; How, J. P., A robust approach to the UAV task assignment problem, International Journal of Robust and Nonlinear Control, 18, 2, 118-134, (2008) · Zbl 1282.93185
[4] Angalakudati, M.; Balwani, S.; Calzada, J.; Chatterjee, B.; Perakis, G.; Raad, N.; Uichanco, J., Business analytics for flexible resource allocation under random emergencies, Management Science, 60, 6, 1552-1573, (2014)
[5] Bellingham, J., Tillerson, M., Richards, A., How, J. P., (2003). Multi-task allocation and path planning for cooperating UAVs, in: Cooperative control: Models, applications and algorithms. Springer. pp. 23-41.
[6] Bertsimas, D.; Gupta, S.; Lullic, G., Dynamic resource allocation: a flexible and tractable modeling framework, European Journal of Operational Research, 236, 1, 14-26, (2014) · Zbl 1338.90158
[7] Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y., (2002). Improved approximation algorithms for resource allocation, in: Integer programming and combinatorial optimization. Springer. pp. 401-414. · Zbl 1049.90035
[8] Castanon, D. A.; Wohletz, J. M., Model predictive control for dynamic unreliable resource allocation, Proceedings of the 41st IEEE conference on decision and control, (2002), Las Vegas, Nevada USA
[9] Chandler, P.; Pachter, M.; Rasmussen, S.; Schumacher, C., Multiple task assignment for a UAV team, Proceedings of the AIAA guidance, navigation, and control conference, (2002)
[10] Chao, X.; Liu, L.; Zheng, S., Resource allocation in multisite service systems with intersite customer flows, Management Science, 49, 12, 1739-1752, (2003) · Zbl 1232.91362
[11] Chen, J.; Xin, B.; Peng, Z.; Dou, L.; Zhang, J., Evolutionary decision-making for the dynamic weapon-target assignment problem, Science in China Series F: Information Sciences, 52, 11, 2006-2018, (2009) · Zbl 1182.93093
[12] Davis, M. T.; Robbins, M. J.; Lunday, B. J., Approximate dynamic programming for missile defense interceptor fire control, European Journal of Operational Research, 259, 3, 873-886, (2017) · Zbl 1402.90203
[13] Deng, Q.; Yu, J.; Wang, N., Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes, Chinese Journal of Aeronautics, 26, 5, 1238-1250, (2013)
[14] Eiben, A. E.; Smith, J. E., Introduction to evolutionary computing, (2007), Springer · Zbl 1028.68022
[15] Ernst, A.; Jiang, H.; Krishnamoorthy, M., Exact solutions to task allocation problems, Management Science, 52, 10, 1634-1646, (2006) · Zbl 1232.90254
[16] Farias, V.; Roy, B. V., Approximation algorithms for dynamic resource allocation, Operations Research Letters, 34, 2, 180-190, (2006)
[17] Gulpinar, N.; Canakoglu, E.; Thoms, Jo, Robust team decision making under uncertainty, International Journal of. Applied Decision Sciences, 3, 3, 206-220, (2010)
[18] Haslum, P.; Geffner, H., Heuristic planning with time and resources, Proceedings of the European conference on planning, 107-112, (2014)
[19] Hong, S. A.; Gordon, G. J., Decomposition-based optimal market-based planning for multi-agent systems with shared resources, Proceedings of the workshop and conference proceedings, 15, 351-360, (2015)
[20] Koenig, S.; Tovey, C.; Zheng, X.; Sungur, I., Sequential bundle-bid single-Sale auction algorithms for decentralized control, Proceedings of the international joint conference on artificial intelligence, 1359-1365, (2007)
[21] Liu, N.; Truong, V. A., Multi-resource allocation scheduling in dynamic environments, Manufacturing and Service Operations Management, 15, 2, 280-291, (2013)
[22] Murphey, R. A., Approximation and complexity in numerical optimization: continuous and discrete problems, 42, 406-421, (2000), Kluwer Academic Publishers · Zbl 0976.90061
[23] Nwozo, C. R.; Nkeki, C. I., On a dynamic optimization technique for resource allocation problems in a production company, American Journal of Operations Research, 2, 357-363, (2012)
[24] Nygard, K.; Chandler, P.; Pachter, M., Dynamic network flow optimization models for air vehicle resource allocation, Proceedings of the american control conference, Arlington, Virginia, USA, 1853-1858, (2001)
[25] Pekka, M.; Ahti, S., Combining a multiattribute value function with an optimization model: an application to dynamic resource allocation for infrastructure maintenance, Decision Analysis, 139-152, (2009)
[26] Pendharkar, C., An ant colony optimization heuristic for constrained task allocation problem, Journal of Computational Science, 7, 37-47, (2015)
[27] Powell, W., A stochastic formulation of the dynamic assignment problem with an application to truckload motor carriers, Transportation Science,, 30, 3, 195-219, (1996) · Zbl 0884.90078
[28] Powell, W., Approximate dynamic programming, (2011), John Wiley and Sons
[29] Powell, W.; Shapiro, J. A.; Simão, H. P., An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem, Transportation Science, 36, 2, 231-249, (2002) · Zbl 1134.90528
[30] Powell, W.; Topaloglu, H., Approximate dynamic programming for large-scale resource allocation problems, INFORMS Tutorials in Operations Research, 123-147, (2006)
[31] Samuel, A.; Guikema, S. D., Resource allocation for homeland defense: dealing with the team effect, Decision Analysis, 238-252, (2012) · Zbl 1355.91050
[32] Spivey, M.; Powell, W., The dynamic assignment problem, Transportation Science, 38, 4, 399-419, (2004)
[33] Spivey, M.; Powell, W. B., Some fixed-point results for the dynamic assignment problem, Annals of Operations Research, 124, 15-33, (2003) · Zbl 1053.90086
[34] Tharumarajah, A., Survey of resource allocation methods for distributed manufacturing systems, Production Planning and Control, 12, 1, 58-68, (2001)
[35] Topaloglu, H.; Powell, W., A distributed decision-making structure for dynamic resource allocation using nonlinear functional approximations, Operations Research, 53, 2, 281-297, (2005) · Zbl 1165.90549
[36] Tovey, C.; Lagoudakis, M. G.; Jain, S.; Koenig, S., The generation of bidding rules for auction-based robot coordination, (Parker, L. E.; Schneider, F. E.; Schultz, A. C., Multi-robot systems: From swarms to intelligent automata, 3, (2005), Springer), 3-14
[37] Wacholder, E., A neural network-based optimization algorithm for the static weapon-target assignment problem, ORSA Journal on Computing, 1, 4, 232-246, (1989) · Zbl 0825.90671
[38] de Weerdt, M. M.; Clement, B. J., Introduction to planning in multiagent systems, Multiagent and Grid Systems, 5, 3, 1359-1365, (2009)
[39] Wiesemann, W.; Kuhn, D.; Rustem, B., Multi-resource allocation in stochastic project scheduling, Annals of Operations Research, 193, 1, 193-220, (2012) · Zbl 1254.90080
[40] Xin, B.; Chen, J.; Peng, Z.; Dou, L.; Zhang, J., An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem, IEEE Transactions on Systems, Man and Cybernetics - Part A: Systems and Humans, 41, 3, 598-606, (2011)
[41] Zhen, L., Task assignment under uncertainty: stochastic programming and robust optimisation approaches, International Journal of Production Research, 53, 5, 1487-1502, (2015)
[42] Zheng, X.; Koenig, S., K-swaps: cooperative negotiation for solving task-allocation problems, Proceedings of the international joint conference on artificial intelligence, 373-379, (2009)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.