A Class of Greedy Algorithms 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 class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.
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 class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.
LanguageEnglish
JournalDiscrete Applied Mathematics
Volume103
Issue number1-3
Pages209–235
ISSN0166-218X
DOIs
StatePublished - 2000
Externally publishedYes

Keywords

    Cite this

    @article{39552395caaa49339865fd810dd8129a,
    title = "A Class of Greedy Algorithms 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 class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.",
    keywords = "Generalized Assignment Problem, Greedy heuristic, Asymptotic feasibility, Asymptotic optimality",
    author = "Romeijn, {H. Edwin} and Morales, {Dolores Romero}",
    year = "2000",
    doi = "10.1016/S0166-218X(99)00224-3",
    language = "English",
    volume = "103",
    pages = "209–235",
    journal = "Discrete Applied Mathematics",
    issn = "0166-218X",
    publisher = "Elsevier BV North-Holland",
    number = "1-3",

    }

    A Class of Greedy Algorithms for the Generalized Assignment Problem. / Romeijn, H. Edwin; Morales, Dolores Romero.

    In: Discrete Applied Mathematics, Vol. 103, No. 1-3, 2000, p. 209–235.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A Class of Greedy Algorithms for the Generalized Assignment Problem

    AU - Romeijn,H. Edwin

    AU - Morales,Dolores Romero

    PY - 2000

    Y1 - 2000

    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 class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.

    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 class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.

    KW - Generalized Assignment Problem

    KW - Greedy heuristic

    KW - Asymptotic feasibility

    KW - Asymptotic optimality

    U2 - 10.1016/S0166-218X(99)00224-3

    DO - 10.1016/S0166-218X(99)00224-3

    M3 - Journal article

    VL - 103

    SP - 209

    EP - 235

    JO - Discrete Applied Mathematics

    T2 - Discrete Applied Mathematics

    JF - Discrete Applied Mathematics

    SN - 0166-218X

    IS - 1-3

    ER -