The formulation of some allocation and connection problems as integer programs
作者:
Melvin A. Breuer,
期刊:
Naval Research Logistics Quarterly
(WILEY Available online 1966)
卷期:
Volume 13,
issue 1
页码: 83-95
ISSN:0028-1441
年代: 1966
DOI:10.1002/nav.3800130107
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractIn this paper a component placement problem and a digital computer backboard wiring problem are formulated as integer linear programs. The component placement problem consists of making a unique assignment of components to column positions such that wireability is maximized. The backboard wiring problem consists of three interrelated subproblems, namely, the placement, the connection, and the routing problems. The placement and connection problems are combined and solved as one, thereby giving the optimal circuit connections as well as minimizing the total lead length. It is shown that under certain assumptions, the number of inequalities and variables in the problem can be greatly reduced. Further simplifying assumptions lead to a near optimal solution.Examples of other allocation problems to which the models presented here are applicable are given.The following concepts are formulated as linear inequalities: (1) the absolute magnitude of the difference between two variables; (2) minimize the minimum function of a set of functions; and (3) counting the number of (0, 1) adjacent component pairs in a vector.
点击下载:
PDF
(625KB)
返 回