Generating experimental data for the Generalized Assignment Problem
成果类型：
Article
署名作者：
Romeijn, HE; Morales, DR
署名单位：
State University System of Florida; University of Florida; Maastricht University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.6.866.10021
发表日期：
2001
页码：
866-878
关键词：
摘要：
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 its 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.