Generating Experimental Data for the Generalized Assignment Problem

H. Edwin Romeijn, Dolores Romero Morales

Research output: Contribution to journalJournal articleResearchpeer-review

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.
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.
LanguageEnglish
JournalOperations Research
Volume49
Issue number6
Pages866-878
ISSN0030-364X
DOIs
StatePublished - 2001
Externally publishedYes

Keywords

    Cite this

    @article{3cf3f80c90a745ae8d0e4e90c0f259d3,
    title = "Generating Experimental Data for the Generalized Assignment Problem",
    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",
    author = "Romeijn, {H. Edwin} and Morales, {Dolores Romero}",
    year = "2001",
    doi = "10.1287/opre.49.6.866.10021",
    language = "English",
    volume = "49",
    pages = "866--878",
    journal = "Operations Research",
    issn = "0030-364X",
    publisher = "Institute for Operations Research and the Management Sciences",
    number = "6",

    }

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

    In: Operations Research, Vol. 49, No. 6, 2001, p. 866-878.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Generating Experimental Data for the Generalized Assignment Problem

    AU - Romeijn,H. Edwin

    AU - Morales,Dolores Romero

    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

    T2 - Operations Research

    JF - Operations Research

    SN - 0030-364X

    IS - 6

    ER -