Generalized Assignment with Nonlinear Capacity Interaction

Joseph B. Mazzola
Additional contact information
Joseph B. Mazzola: Fuqua School of Business, Duke University, Durham, North Carolina 27706

Management Science, 1989, vol. 35, issue 8, 923-941

Abstract: The utility of the generalized assignment problem (GAP) is well known in regard to resource allocation problems arising in the areas of production planning, scheduling, and facility location. This paper introduces an important generalization of the GAP, which is called the 0-1 generalized assignment problem with nonlinear capacity constraints (NLGAP) and which allows for capacity interaction among tasks assigned to the same agent. For example, NLGAP can be used to model the hierarchical production planning problem involving the assignment of product families to production facilities in the case where process changeover gives rise to nonlinear capacity interaction among product families assigned to be produced at the same facility. Other applications of NLGAP occur readily throughout the areas of production planning and scheduling. We define a branch-and-bound algorithm for the NLGAP. This algorithm draws upon the underlying structure of the problem by combining in a novel manner recent advances in both nonlinear 0-1 programming and bounding techniques for the GAP. A heuristic for obtaining approximate solutions to NLGAP is also defined. We discuss computational experience with both the exact algorithm and the heuristic. The computational results demonstrate that the heuristic is extremely effective in obtaining near-optimal solutions and that the branch-and-bound algorithm can solve to optimality NLGAPs with 5 agents, 20 tasks, and over 1000 nonlinear terms per constraint.

Keywords: nonlinear 0-1 programming; assignment and allocation (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.35.8.923 (application/pdf)

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:inm:ormnsc:v:35:y:1989:i:8:p:923-941

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().