A class of greedy algorithms for the generalized assignment problem
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 function...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
2000
|
| _version_ | 1826279233192722432 |
|---|---|
| author | Romeijn, H Romero-Morales, D |
| author_facet | Romeijn, H Romero-Morales, D |
| author_sort | Romeijn, H |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:55:41Z |
| format | Journal article |
| id | oxford-uuid:74228705-fc49-4b20-85c9-c10514370eba |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:55:41Z |
| publishDate | 2000 |
| record_format | dspace |
| spelling | oxford-uuid:74228705-fc49-4b20-85c9-c10514370eba2022-03-26T20:00:49ZA class of greedy algorithms for the generalized assignment problemJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:74228705-fc49-4b20-85c9-c10514370ebaSaïd Business School - Eureka2000Romeijn, HRomero-Morales, DThe 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. |
| spellingShingle | Romeijn, H Romero-Morales, D A class of greedy algorithms for the generalized assignment problem |
| title | A class of greedy algorithms for the generalized assignment problem |
| title_full | A class of greedy algorithms for the generalized assignment problem |
| title_fullStr | A class of greedy algorithms for the generalized assignment problem |
| title_full_unstemmed | A class of greedy algorithms for the generalized assignment problem |
| title_short | A class of greedy algorithms for the generalized assignment problem |
| title_sort | class of greedy algorithms for the generalized assignment problem |
| work_keys_str_mv | AT romeijnh aclassofgreedyalgorithmsforthegeneralizedassignmentproblem AT romeromoralesd aclassofgreedyalgorithmsforthegeneralizedassignmentproblem AT romeijnh classofgreedyalgorithmsforthegeneralizedassignmentproblem AT romeromoralesd classofgreedyalgorithmsforthegeneralizedassignmentproblem |