机器可选制造单元设计的半边图划分模型

机器可选制造单元设计问题是一类含有多种局部约束的复杂组合优化问题,用图划分算法解决此类问题将会面临指数级个图的划分。论文提出半边图理论,半边附属于顶点,一对半边可结合为边。用半边及其结合性表示各种局部约束,将机器可选制造单元设计问题转化为基于半边图的组合优化问题,即计划路径可选的半边图划分问题。

机器可选制造单元设计的半边图挤出吸入算法

计划路径可选的半边图划分问题是一类含有多种局部约束的复杂组合优化问题。设计了针对半边图划分问题的半边图挤出吸入算法,用此算法求解了机器可选制造单元成组设计问题。示例表明,半边图语言能够准确地表达可能解中的复杂结构和各种约束。20台机器20种零件分组实验证明,平均12.4次迭代计算即可达到优化目标。