Treffer: The generalized assignment problem with fixed processing times and uniform processing costs to minimize total cost.

The generalized assignment problem (GAP) is a foundational problem in operations research, but its progress is quite limited. In this paper we study an important special case of the GAP with fixed processing times and uniform processing costs, where the upper bound of the makespan is given, and the objective to minimize the total processing cost. We prove a critical technical lemma, which enables us to develop an approximation algorithm with an improved performance ratio of 1 + (γ − 1) ϵ , where ϵ ∈ (0 , 1 3 ] can be any small constant and γ is the maximum to the minimum processing cost per unit time on a machine, improving on the existing performance ratio of 2 + γ 3 in the literature. For the general problem when γ is arbitrarily, we show that it is NP-hard to approximate within a constant performance ratio. For the special case when γ is a constant, we present an efficient PTAS (polynomial time approximation scheme) by applying the technical lemma. Our techniques and results bring new insights into the GAP research. • The GAP with fixed processing times and uniform processing costs. • A technical lemma for comparing total costs of schedules. • A simple proof for the best known approximation ratio. • An improved approximation ratio is obtained. • A linear-time PTAS if the maximum unit processing cost is fixed. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)