An approximation algorithm for the generalized assignment problem (Q1319018)

The authors consider the following problem of scheduling parallel machines with costs. Let processing job \(j\) on machine \(i\) require time \(p_{ij}\) and incur a cost \(c_{ij}\). Given costs \(c_{ij}\) and times \(p_{ij}\), for \(i= 1,\dots,m\), \(j=1,\dots,n\), minimize the total cost incurred under the conditions that each job is to be processed by exactly one machine and each machine \(i\) is available for \(T_ i\) units. The main result of the paper is as follows. There is a polynomial-time algorithm that, given a real value \(C\), either proves that no feasible schedule of cost \(C\) exists, or else finds a schedule of cost at most \(C\) where each machine \(i\) is used for at most \(2T_ i\) time units. This result is also extended to a variant of the problem where instead of a fixed processing time \(p_{ij}\), there is a range of possible processing time for each machine-job pair, and the cost linearly increases as the processing time decreases. At last the problem of minimizing the mean job completion time is considered.