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 the probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal value, normalized by dividing by the number of jobs, converges almost surely to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.