Abstract: To solve the operation sequencing problem in CAPP that is a NP-hard problem,a new Feasible Operation Sequence Oriented Genetic Algorithm (FOSOGA) was developed to minimize the total cost.In the FOSOGA,a Feasible Operation Sequence (FOS) satisfying the precedence constraints was encoded by a permutation.The crossover with adaptive crossover probability and the mutation with adaptive mutation probability were designed to evolve FOS and relevant machining resources recorded in any chromosome and keep the feasibility of the chromosomes.In addition,a new elitist-based crossover mechanism was introduced in the FOSOGA.The proposed FOSOGA was applied to two industrial cases and was compared with existing Genetic Algorithm (GA),ant colony optimization (ACO) and particle swarm optimization (PSO).The comparative results showed that FOSOGA was superior than existing GA,ACO and PSO for average solution quality.

Key words: process planning, operation sequencing, genetic algorithms, feasible operation sequence

摘要： 针对CAPP中工序排序优化这一NP-hard问题的求解,以最小化总成本为目标,提出一种新型的面向可行工序序列的遗传算法(FOSOGA)。该算法中,染色体以排列数的形式直接表征满足工序优先关系约束的可行工序序列;设计了可保证染色体可行性的自适应交叉算子和自适应变异算子来演化工序序列和各工序的加工资源;引入新的精英参与的交叉策略。将FOSOGA应用于两个案例,并与现有遗传算法、粒子群算法和蚁群算法进行了对比。结果表明,FOSOGA获取的解的平均质量优于现有遗传算法、粒子群和蚁群算法。

关键词: 工艺规划, 工序排序, 遗传算法, 可行工序序列