Generating Experimental Data for the Generalized Assignment Problem

H. Edwin Romeijn () and Dolores Romero Morales ()
Additional contact information
H. Edwin Romeijn: Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, Florida 32611-6595
Dolores Romero Morales: Faculty of Economics and Business Administration, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands

Operations Research, 2001, vol. 49, issue 6, 866-878

Abstract: 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.

Keywords: Programming; integer: generalized assignment problem; Statistics: generation of random data (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.6.866.10021 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:6:p:866-878

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().