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.
Original languageEnglish
JournalDiscrete Applied Mathematics
Volume103
Issue number1-3
Pages (from-to)209–235
ISSN0166-218X
DOIs
Publication statusPublished - 2000
Externally publishedYes

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 {Romero Morales}, Dolores",
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; Romero Morales, Dolores .

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 - Romero Morales, Dolores

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

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -