An approximation algorithm for the generalized assignment problem
type: Item
instance of: scholarly article
title: An approximation algorithm for the generalized assignment problem
zbMATH Open document ID: 0804.90077
DOI: 10.1007/BF01585178
author: David B. Shmoys
author: Éva Tardos
published in: Mathematical Programming. Series A. Series B
publication date: 1995-01-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 549153
zbMATH Keywords: generalized assignment problem
zbMATH Keywords: approximation algorithms
zbMATH Keywords: parallel machines
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: mean job completion time
Wikidata QID: Q56519775
reviewed by: Ivan Martinec
MaRDI profile type: Publication
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Technical Note—Minimizing Average Flow Time with Parallel Machines
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: Matching theory
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Scheduling Multiple Variable-Speed Machines
Recommended article: An efficient approximation for the generalized assignment problem
Recommended article: A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
Recommended article: Q3609290
Recommended article: A survey of algorithms for the generalized assignment problem
Recommended article: A class of greedy algorithms for the generalized assignment problem
Recommended article: Q3372332
Recommended article: Q3693266
Recommended article: A hybrid algorithm for the generalized assignment problem
Recommended article: An algorithm for the bottleneck generalized assignment problem
Recommended article: Approximation algorithms for the partial assignment problem
description: scientific article; zbMATH DE number 549153