基于符号编码的装配可行解域大小求解算法研究

在运筹学的分层思想指导下，应用组合数学理论，提出一种求解基于符号编码的装配作业调度问题可行解域大小的算法，适用于计算任意装配层次结构、任意数量零件和任意数量工序的树状装配型结构的可行解域大小，明确了可行解域的大小和问题的复杂性，为进一步提高遗传算法的效率和保证调度实时性提供有价值的参考。最后对装配结构中同结构不同工序数和同工序数不同结构两种情况进行了实例计算。结果表明，可行解域仅占整个解域的极小部分，为搜索域只限于可行解域内的高效遗传算法提供了研究基础。

Study of Computing Algorithm of Size of Assembly Constrained Feasible Solution Field Based on Symbolic Encoding

Under the guidance of hierarchical thinking in operational research, a new algorithm for calculating the feasible solution field size of assembly job shop scheduling problem based on symbolic encoding was proposed by using the combinatorial theory, which is applicable for computing feasible solution field size of tree-like assembly structures that may have arbitrary assembly hierarchy structure, any number of parts and any number of operations. The results make the scale and complexity of the problem be solved definitely. Furthermore, these results are useful references for efficiency in improvement of genetic algorithm and satisfaction of real-time scheduling. In the end, two computation instances were given, one has the same structure but different number of operations, and the other has the same number of operations, however, different structure. And the study of effective genetic algorithm search domain which is only in feasible solution field, will be the foundation because the results show that feasible solution field only takes a very small portion of the whole feasible solution field.