Abstract
The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep ij and incurs a cost ofc ij ; each machinei is available forT i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T i time units.
We also extend this result to a variant of the problem where, instead of a fixed processing timep ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.L. Bruno, E.G. Coffmann Jr. and R. Sethi, “Scheduling independent tasks to reduce mean finishing time,”Communications of the ACM 17 (1974) 382–387.
W.A. Horn, “Minimizing average flow time with parallel machines,”Operations Research 21 (1973) 846–847.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, “Sequencing and scheduling: algorithms and complexity,” in: A.H.G. Rinnooy Kan and P. Zipkin, eds.,Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory (North-Holland, Amsterdam, 1993) pp. 445–522.
J.K. Lenstra, D.B. Shmoys and É. Tardos, “Approximation algorithms for scheduling unrelated parallel machines,”Mathematical Programming 46 (1990) 259–271.
J.-H. Lin and J.S. Vitter, “ε-approximations with minimum packing constraint violation,” in:Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (1992) pp. 771–782.
L. Lovász and M. Plummer,Matching Theory (Akademiai Kiado, Budapest, and North-Holland, Amsterdam, 1986).
S.A. Plotkin, D.B. Shmoys and É. Tardos, “Fast approximation algorithms for fractional packing and covering problems” Technical Report 999, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1992).
M.A. Trick, “Scheduling multiple variable-speed machines,” in:Proceedings of the 1st Conference on Integer Programming and Combinatorial Optimization (1990) pp. 485–494.
M.A. Trick, “Scheduling multiple variable-speed machines,” unpublished manuscript (1991).
Author information
Authors and Affiliations
Additional information
Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.
Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.
Rights and permissions
About this article
Cite this article
Shmoys, D.B., Tardos, É. An approximation algorithm for the generalized assignment problem. Mathematical Programming 62, 461–474 (1993). https://doi.org/10.1007/BF01585178
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585178