Abstract

This talk considers a problem associated with the assignment of assets to tasks where each asset can potentially execute any of the tasks, but with a probabilistic outcome of success. There is a cost associated with each possible asset-task assignment, as well as a cost associated with the non-execution of the tasks. We formulate the allocation of assets to tasks in order to minimize the overall expected cost, as a nonlinear combinatorial optimization problem. For its solution, 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. Three different schemes for the estimation of the arc costs are introduced and their performance is investigated. An approach for obtaining tight lower bounds to the optimal solution is also developed, which is based on a piecewise linear approximation of the considered problem.