Abstract: Before performing assembly operations at each level,a flexible assembly job-shop needs to meet the completeness requirement of materials,which makes more complex the production planning,organization and control.To solve the multi-level flexible assembly job-shop scheduling problem,a Tabu Search algorithm embedded with Domain Knowledge (DKTS) was proposed to minimize the completion time and hence improve the performance of algorithm.Gene expression programming was utilized to discover production sequencing/machine selection rules on the ground of problem attributes to enhance the performance of the initial solution.Based on critical paths and critical processes,neighborhood structures that could effectively reduce the target value was meticulously designed to enable the targeted search and refine the search space.In addition,the tabu objects were precisely set and the length of the tabu list was adjusted adaptively to strengthen the exploration and exploitation ability of the algorithm.Experimental results showed that DKTS improved the convergence and stability to a large extent attributed to the guidance of domain knowledge.

Key words: multi-level flexible assembly job-shops, tabu search algorithm, domain knowledge, gene expression programming, adaptive tabu list

摘要： 柔性装配作业车间在进行每一层级装配前,均需满足齐套性要求,导致生产计划、组织和控制变得更加复杂。针对多层级柔性装配作业车间调度问题,以最小化最大完工时间为目标,提出一种融合领域知识的禁忌搜索算法(DKTS)。其中,利用基因表达式编程,挖掘与问题属性相关的工序排序/机器选择规则,提升初始解性能;基于关键路径和关键工序,设计可有效减少目标值的邻域结构,促成靶向搜索、精炼搜索空间。此外,精准设置禁忌对象,适应性调整禁忌表长度,加强算法的前期探索及后期开发能力。实验表明DKTS在领域知识引导下大幅提高了解的收敛性和稳定性。

关键词: 多层级柔性装配作业车间, 禁忌搜索算法, 领域知识, 基因表达式编程, 自适应禁忌表