Abstract: Aiming at the problem that the process-based coding method cannot guarantee the feasibility of the solution when the intelligent optimization algorithm solves the assembly job shop scheduling problem,a right-shift repair coding method was proposed.The coding method could not only meet the constraints of assembly relationship of the product to ensure the solution feasibility when the algorithm iterated through the right-shift operation of a specific region,but also ensure that the relative order of the underlying work processes unchanged in the process of repair,which minimizes the damage to the original solution as much as possible,improve the diversity of the initial solution and realize the efficient search of the solution space.In addition,a block-based insertion variation operator for the coded solution was designed to enlarge the search range of the solution.Finally,the coding method and mutation operator were realized in the classical genetic algorithm and compared with the existing algorithms,and the experimental results verified the effectiveness of the proposed method.

Key words: assembly job shop scheduling, right-shift repair code, genetic algorithms

摘要： 针对智能优化算法求解装配作业车间调度问题时存在的基于工序的编码方法无法保证解的可行性问题,提出一种右移修复编码方法。该编码方法通过特定区域的右移操作,既能满足产品的装配关系约束,保证算法迭代时解的可行性,又能保证修复过程中底层工序的相对顺序不变,尽可能减少对原始解的破坏,提高初始解的多样性,实现对解空间的高效搜索;针对编码解设计了一种基于块的插入变异算子,以扩大解的搜索范围;最后,在经典遗传算法中使用了该编码方法和变异算子,并与已有算法进行对比,验证了所提方法的有效性。

关键词: 装配作业车间调度, 右移修复编码, 遗传算法