**Generating experimental data for the Generalized Assignment Problem**

**H.E. Romeijn, D. Romero Morales**

The Generalized Assignment Problem (GAP) is the problem
of finding the minimal cost assignment of jobs to machines such that each job is
assigned to exactly one machine, subject to capacity restrictions on the
machines. We propose a new stochastic model for the GAP. A tight condition on
this stochastic model under which the GAP is feasible with
probability one when the number of jobs
goes to infinity is derived. This
new stochastic model enables us to analyze the adequacy of
most of the random generators given for the GAP in the literature.
We demonstrate that the random generators commonly used
to test solution procedures for the GAP tend to create
easier problem instances when the number of machines *m* increases.
We describe a greedy heuristic for the GAP, and use it to illustrate the results from the paper.