Addressing capacity uncertainty in resource-constrained assignment problems
Resource-constrained assignment problems typically assume capacities are known. We focus on the situation when capacities are uncertain. In addition to the well-known generalized assignment problem (GAP) and the assignment problem with side-constraints (APSC), we discuss two other resource-constrained generalizations of the assignment problem. We identify two alternative approaches to utilize deterministic solution strategies while addressing capacity uncertainty, and illustrate how these approaches can be applied to a specific generalization. We also report the performance of these alternatives on a number of random test problems.
capacity uncertainty assignment problem generalized assignment problem resource constraints approximation