A Class of Greedy Algorithms for the Generalized Assignment Problem

H. Edwin Romeijn, Dolores Romero Morales

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
Originalsprog Engelsk Discrete Applied Mathematics 103 1-3 209–235 0166-218X https://doi.org/10.1016/S0166-218X(99)00224-3 Udgivet - 2000 Ja

Emneord

• Generalized Assignment Problem
• Greedy heuristic
• Asymptotic feasibility
• Asymptotic optimality

Citer dette

@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",

}

I: Discrete Applied Mathematics, Bind 103, Nr. 1-3, 2000, s. 209–235.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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 -