A Multiperiod Minimax Resource Allocation Problem with Substitutable Resources
研究资源可存储且可替代的多周期分配模型，应用于电路板装配厂的生产规划，通过算法最小化与原计划的最大加权偏差，并高效分配短缺组件。
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.