A Novel Modified Discrete Differential Evolution Algorithm to Solve the Operations Sequencing Problem in CAPP Systems

Abstract

Operation Sequencing (OS) is one of the most critical tasks in a CAPP system. This process could be modelled as a combinatorial problem where finding a suitable solution within a reasonable time interval is difficult. This work implements a novel Discrete Differential Evolution Algorithm (DDEA) to solve the OS problem, focusing on parts of up to 76 machining operations; the relationships among operations are represented as a directed graph; the contributions of the DDEA are as follows: (1) operates with a discrete representation in the space of feasible solutions; (2) employs mutation and crossover operators to update solutions and to reduce machining and setup costs, (3) possess a local search strategy to achieve better solutions, and (4) integrates a statistical method based on quantiles to measure the quality and likelihood for an achieving a solution. To demonstrate the efficiency and robustness of the DDEA, five prismatic parts with different numbers of machining operations as benchmarks to address the OS problem were selected. The results generated the same OS for parts with a few machining operations (up to 23 machining operations). Conversely, for parts with more machining operations, the DDEA needs more runs to achieve the best solution.

Keywords

• Discrete Differential Evolution
• operation sequencing
• statistical method based on quantiles
• combinatorial optimisation
• feasible operation sequences