制造单元设计中心半边图与拆分重组算法

Half Edge Graph and Disassemble Assemble Algorithm for Manufacturing Cell Design

提出了半边自组图理论,半边附属于顶点,一对半边可结合为边。用半边图来描述复杂组合优化问题的可能解,在此基础上设计了针对图的拆分重组算法,用此算法求解了一个典型的复杂组合优化问题,制造单元设计问题。示例表明,半边图语言能够准确地表达可能解中的复杂结构和各种约束,20台机器50种零件分组实验证明,7次迭代计算即可达到优化目标。

This paper proposes half edge self assemble graph theory, half edge belongs to vertex, a couple of half edges could assemble one edge. The probably solutioo of complex combination optimizm problem can be described by half edge graphs, the paper designes a disassemble assemble algorithm for graph, this algorithm can solve manufacturing cell design problem. Half edge graph theory can represent complex structure and various constraint accurately. For a 20×50 example, only 7 times disassemble and assemble can get the optimizm solution.