Generating experimental data for the generalized assignment problem

Romeijn, H. Edwin and Romero-Morales, Dolores (2001) Generating experimental data for the generalized assignment problem. Operations Research, 49 (6). pp. 866-878.

[img]
Preview
PDF
Download (174kB) | Preview

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.

Item Type: Article
Keywords: Programming; integer: generalized assignment problem; Statistics: generation of random data
Subject(s): Management science
Centre: Faculty of Management Science
Date Deposited: 09 Sep 2010 14:29
Last Modified: 23 Oct 2015 14:05
URI: http://eureka.sbs.ox.ac.uk/id/eprint/434

View statistics

Actions (login required)

Edit View Edit View