A genetic algorithm for operation sequencing in CAPP using edge selection based encoding strategy
A genetic algorithm for operation sequencing in CAPP using edge selection based encoding strategy
复制标题
DOI：
10.1007/s10845-015-1109-6
复制
发表时间：
2015-06
影响因子：
8.3
通讯作者：
Yuliang Su;Xuening Chu;Dongping Chen;Xiwu Sun
中科院分区：
文献类型：
--
作者：
Yuliang Su;Xuening Chu;Dongping Chen;Xiwu Sun
CAPP中的工序排序是指在满足所有优先约束的前提下，以最小的加工成本确定加工工序的最优顺序。遗传算法因其高效性和并行处理能力而被广泛应用于求解优先约束工序排序问题。如何保证约束的优先性一直是研究的热点，主要有两类方法。第一种方法使用额外的调整方法来修复打破优先约束的不可行解。它是不可靠和低效率的。第二类算法通过拓扑存储等编码方法避免了初始化过程中的不可行解，但对于复杂的PCOSPs算法可能会出现早熟收敛问题。为了解决这些问题，提出了一种基于遗传算法的边缘选择策略。基于边选择的策略能在初始化阶段产生可行解，并保证每个可行解都以可接受的概率产生，从而提高了遗传算法的收敛效率。然后通过顺序交叉保持优先约束。设计了改进的变异算子，对每道工序的机床、进刀方向和刀具进行优化选择。实验结果表明，该算法是有效的.
Operation sequencing in CAPP aims at determining the optimal order of machining operations with minimal machining cost and satisfying all the precedence constraints. The genetic algorithm (GA) is widely used to solve precedence constrained operation sequencing problem (PCOSP) due to its efficiency and parallel processing capability. How to guarantee the precedence constraints is always a hot research topic and there are mainly two classes of methods. The first ones use additional adjustment approaches to repair the infeasible solutions that break precedence constraints. It is unreliable and low efficient. The second ones avoid infeasible solutions in initialization through some encoding approaches such as topological storing based encoding approach, but the premature convergence problem may occur facing some complicated PCOSPs. To solve these problems, an edge selection strategy based GA is proposed. The edge selection based strategy could produce feasible solutions in initialization, and assures that every feasible solution will be generated with acceptable probability so as to improve GA’s converging efficiency. Then the precedence constraints are kept by order crossover. Modified mutation operator is designed to optimize the selection of machine tool, tool access direction and cutting tool for each operation. The experiments illustrate that the proposed algorithm is effective and efficient.