Polyhedral structure and properties of a model for layout design

In flexible manufacturing systems, the type of materials-handling system strongly influences the machine layout. This paper studies the problem of determining a machine layout for uni-directional loop-networks which minimizes the maximum number of loop-traversals for a family of parts, which we show to be NP-complete. We also show that the polyhedral structure of its integer-programming formulation is closely related to that of the maximum-weight acyclic subgraph problem. We introduce inequalities that define facets and faces of the convex hull of solutions for the layout problem, which also define corresponding facets and faces for the acyclic subgraph polytope. Preliminary computational results are also presented.