### Abstract

Original language | English |
---|---|

Journal | Operations Research |

Volume | 49 |

Issue number | 6 |

Pages (from-to) | 866-878 |

ISSN | 0030-364X |

DOIs | |

Publication status | Published - 2001 |

Externally published | Yes |

### Cite this

*Operations Research*,

*49*(6), 866-878. https://doi.org/10.1287/opre.49.6.866.10021

}

*Operations Research*, vol. 49, no. 6, pp. 866-878. https://doi.org/10.1287/opre.49.6.866.10021

**Generating Experimental Data for the Generalized Assignment Problem.** / Romeijn, H. Edwin; Romero Morales, Dolores .

Research output: Contribution to journal › Journal article › Research › peer-review

TY - JOUR

T1 - Generating Experimental Data for the Generalized Assignment Problem

AU - Romeijn, H. Edwin

AU - Romero Morales, Dolores

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

KW - Programming

KW - Integer: Generalized assignment problem

KW - Statistics: Generation of random data

U2 - 10.1287/opre.49.6.866.10021

DO - 10.1287/opre.49.6.866.10021

M3 - Journal article

VL - 49

SP - 866

EP - 878

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 6

ER -