Asset-Task Assignment Algorithms in the Presence of Execution Uncertainty

作者：Timotheou Stelios^*

来源：Computer Journal, 2011, 54(9): 1514-1525.

DOI：10.1093/comjnl/bxq063

• optimum asset assignment
• execution uncertainty
• random neural networks
• nonlinear combinatorial optimization
• network flow problems
• piecewise linear approximation
• lower bounds

We investigate the assignment of assets to tasks where each asset can potentially execute any of the tasks, but assets execute tasks with a probabilistic outcome of success. There is a cost associated with each possible assignment of an asset to a task, and if a task is not executed there is also a cost associated with the non-execution of the task. As we proposed in [Gelenbe, E., Timotheou, S., and Nicholson, D. (2010). Fast distributed near optimum assignment of assets to tasks. Comput. J., doi:10.1093/comjnl/bxq010], we formulate the allocation of assets to tasks in order to minimize the overall expected cost, as a nonlinear combinatorial optimization problem. We propose the use of network flow algorithms which are based on solving a sequence of minimum cost flow problems on appropriately constructed networks with estimated arc costs. We introduce three different schemes for the estimation of the arc costs and we investigate their performance compared with a random neural network algorithm and a greedy algorithm. We also develop an approach for obtaining tight lower bounds to the optimal solution based on a piecewise linear approximation of the considered problem.

• 出版日期2011-9