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

Weidong Li and Jinwen Ou

European Journal of Operational Research, 2025, vol. 327, issue 2, 420-431

Abstract: 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,13] 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.

Keywords: Scheduling; Generalized assignment problem; Bin packing; Approximation algorithm; Worst-case bound analysis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004151
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:327:y:2025:i:2:p:420-431

DOI: 10.1016/j.ejor.2025.05.031

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().