A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem

We study the generalized assignment problem, under a probabilistic model for its cost and requirement parameters. First we address the issue of feasibility by deriving a tight condition on the probabilistic model that ensures that the corresponding problem instances are feasible with probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal solution value, normalized by dividing by the number of jobs, converges with probability one to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.