An approximation algorithm for the generalized assignment problem

摘要: The generalized assignment problem can be viewed as the following of scheduling parallel machines with costs. Each job is to processed by exactly one machine; processing jobj on machinei requires timep ij and incurs a cost ofc ; each available forT i time units, objective minimize total incurred. Our main result follows. There polynomial-time algorithm that, given valueC, either proves that no feasible schedule costC exists, or else finds at mostC where used for most 2T units. We also extend this variant where, instead fixed , there range possible times machine—job pair, linearly increases decreases. show these results imply 2-approximation weighted sum makespan, i.e., maximum completion time. consider minimizing mean valuesM andT, timeM makespanT mostM makespan 2T.