A Multiperiod Minimax Resource Allocation Problem with Substitutable Resources

Quynh C. Nguyen and Richard E. Stone
Additional contact information
Quynh C. Nguyen: AT&T Bell Laboratories, Room 3/311, Crawfords Corner Road, Holmdel, New Jersey 07733-1988
Richard E. Stone: AT&T Bell Laboratories, Room 3/311, Crawfords Corner Road, Holmdel, New Jersey 07733-1988

Management Science, 1993, vol. 39, issue 8, 964-974

Abstract: In this paper we consider a multiperiod resource allocation model in which the resources are storable and substitutable. A specific application of this model relates to the multiperiod production planning for electronic circuit board assembly factories. In this case, resources are electronic components, which are storable, that is, excess components in one period can be used in subsequent periods. Components that can be used in the same function on a circuit board are considered substitutable. Substitutability between components, however, may be dependent upon the specific circuit board on which they reside. Given that there are certain production requirements for the circuit boards, and that some components are in short supply, our algorithm (a) revises the production levels of the affected circuit boards, and (b) efficiently allocates the available components according to the revised production, so as to minimize the maximum weighted deviation from the original production plans. The weights reflect the relative importance of the circuit boards. The objective function uses cumulative production levels and cumulative demands to allow for back-scheduling. We present a primal-dual algorithm that is very efficient. An implementation of the algorithm compares favorably with a standard linear programming code. We solved a problem with 300 components, 20 different circuit boards (average of 10 functions/board) for 10 time periods (approximately 30,000 variables) in less than one minute on a VAX 11/785. We also discuss upper and lower bound extensions, and a lexicographic algorithm to ensure that less critical resources are also allocated effectively.

Keywords: resource allocation; substitutable resources; manufacturing systems; multi-period analysis (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.39.8.964 (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:39:y:1993:i:8:p:964-974

Access Statistics for this article

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