| 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: the collectively capacitated GAP (CCGAP) and the generalized snatching problem (GMP). We explore two alternative methodologies to address capacity uncertainty in these generalizations: a deterministic formulation-based methodology and a stochastic programming methodology. We compare and analyze the performance of these methodologies on a large number of test problems, using an experimental setup that focuses on a specific generalization of the assignment problem. The computational results indicate that our stochastic programming-based approximate solution strategy dominates deterministic formulation-based approaches, and takes less computational effort. We also present an application in air traffic management that can benefit from these methodologies, and demonstrate how to address this application using an example problem. Results indicate high expected efficiency for flight schedules that are generated using stochastic programming-based approaches. |
