A class of greedy algorithms for the generalized assignment problem

The Generalized Assignment Problem (GAP) is the problem of finding the mini mal cost assignment of jobs to machines such that each job is assigned to e xactly one machine, subject to capacity restrictions on the machines. We pr opose a class of greedy algorithms for the GAP. A family of weight function s 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 e ach job to each of the machines. The greedy algorithm then schedules jobs a ccording to a decreasing order of desirability. A relationship with the par tial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probab ilistic sense. (C) 2000 Elsevier Science B.V, All rights reserved.