An approximation algorithm for the generalized assignment problem (Q1319018): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Scheduling independent tasks to reduce mean finishing time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Technical Note—Minimizing Average Flow Time with Parallel Machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation algorithms for scheduling unrelated parallel machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling Multiple Variable-Speed Machines / rank | |||
Normal rank |
Latest revision as of 14:28, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An approximation algorithm for the generalized assignment problem |
scientific article |
Statements
An approximation algorithm for the generalized assignment problem (English)
0 references
19 January 1995
0 references
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.
0 references
generalized assignment problem
0 references
approximation algorithms
0 references
parallel machines
0 references
polynomial-time algorithm
0 references
mean job completion time
0 references