Layout patterns of packing layout problem and their applications

摘要

Packing layout problem belongs to NP-Complete theoretically. Because it has extensive engineering applications, packing layout problem is concerned more and more in recent years. Layout pattern refers to the relative position relationship between objects in layout scheme. It is one of the important aspects that deserve to be studied in a deep-going way. Taking the layout scheme design of satellite cabins as background, we study layout patterns of packing layout problem in a circular container. The relevant concepts are defined, such as isomorphic and non-isomorphic layout patterns. And we present relation matrix, pattern matrix and their transformations to represent and recognize various layout patterns. We also propose some construction methods of isomorphic and non-isomorphic patterns. Non-isomorphic degree is introduced to measure the difference between two layout patterns. In this paper, several applications based on layout patterns are discussed. All of this work expects to benefit relaxing combinatorial explosion that occurs when solving packing layout problem and constructing efficient algorithm for layout scheme design.