刘齐浩，李新宇*，高亮

State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

1. 引言

智能制造包含智能制造技术和智能制造系统[1-3]。智能工艺规划（process planning, PP）属于重要的智能制造技术，在智能制造系统中扮演着重要的角色[4,5]。PP能够有效地缩短生产周期，提高产品质量，并进一步降低资源和能源的消耗[6]。因此，PP在工业应用与研究中获得了较多的关注。然而，因为PP问题内部存在着大量的柔性，导致在实际生产场景中很难得到最优的工艺规划路线[7]。

解决传统的PP问题通常需要三个步骤：工艺选择、资源分配和工序排序[5]。通过第一步的工艺选择来确定不同加工特征所需要的工艺及工序，并基本确定工艺路线的总长度。然后，通过分配机器、刀具等资源，来确定各工序的加工资源分配，预获取相关加工参数，例如加工时间等。最关键的工序排序一般是最后执行，且排序过程必须遵循该工件工艺网络图中的优先关系约束[8]。例如，粗铣工序和粗磨工序必须安排在精铣工序和精磨工序之前执行，镗孔工序必须排在钻工工序后[9]。

PP问题已经被证明是非确定性多项式时间困难（nondeterministic polynomial-time-hard, NP-hard）问题[6,10]，这也意味着仅仅依靠传统的梯度下降法、图论法和仿真方法很难实现PP问题的求解。因此，多数研究者试图引入元启发式算法来求解PP问题[11]。当前主要的求解方法包括遗传算法（genetic algorithm, GA）[7,12]、禁忌搜索算法（tabu search, TS）[13]、粒子群优化算法（particle swarm optimization, PSO）[8]、蚁群优化算法（ant colony optimization, ACO）[14]和蜜蜂配合优化算法（honey-bees mating optimization, HBMO）[10]。这些算法能够在较短时间内获得近优解，更侧重算法的求解效率而不是解的最优性。

在此研究背景下，大部分公开PP问题的最优解至今还未找到[8,15]。……