邓燕兰，熊菊霞，郑宏宇，姚光磊

（广西民族大学数学与物理学院，广西南宁530006）

0 引言

计算机辅助工艺设计(Computer Aided Process Planning, CAPP)在计算机工艺规划等方面有重要的应用。[1]CAPP 主要分为三步：第一，特征识别，即对零件的特征进行分类和识别；[2]第二，确定提取出来的特征的加工操作和加工资源；[3]第三，在设计和制造实践的条件约束下，确定加工成本最低的操作顺序及其对应的加工资源。[4]工序排序优化问题属于第三步，在已知加工特征,及其每个特征的加工操作和候选加工资源的基础上，通过规划得到最优加工方案。它以最小化总成本为目标；以确定满足优先关系约束的加工工序的顺序，以及每个加工工序使用的加工资源为主要任务。

工序排序优化问题的可行方案包括可行工序序列(Feasible Operation Sequence, FOS),及FOS 中每个工序对应使用的机床资源、刀具资源和进刀方向(Tool Approach Direction, TAD)。工序的排序，候选加工资源的选择是相互联系、相互制约的，因此工序排序优化问题已被证明是一类具有NP-hard 性质的组合优化问题。[5]它的求解方法主要分为两类：一类是精确方法，主要包括分枝定界法[6]和线性规划法[7]；另一类是近似方法。近几年来随着智能优化算法的发展，很多专家和学者都开始利用智能优化算法求解组合优化问题。[8]针对工序排序的优先级限制，Li等人[9]提出了求解工序排序优化问题的混合遗传算法和模拟退火算法，使用优先约束调整算法对交叉和变异后生成的不可行解进行修复。Huang 等人[10]将图论与矩阵理论相结合，提出了一种混合图遗传算法，采用启发式算法将变异算子生成的不可行方案调整到可行域。……