Application of graph theory and hybrid GA-SA for operation sequencing in a dynamic workshop environment

作者：Huang Weijun; Lin Weiguo^*; Xu Shengyong

来源：Computer-Aided Design and Applications, 2017, 14(2): 148-159.

DOI：10.1080/16864360.2016.1223426

• Graph search algorithm
• Hybrid algorithms
• Hybrid genetic algorithms
• Machining operations
• Operation sequencing
• Optimization approach
• Precedence constraints
• Precedence graph

To solve the machining operation sequencing problem in the computer aided process planning, this paper presents a hybrid genetic algorithm and simulated annealing approach for machining operation sequencing optimization in a dynamic workshop environment. The directed graph used as an explicit constraint model is formulated based on precedence constraints among machining operations, and the graph search algorithms is embedded into framework of the optimization system. The initial solutions composed of all feasible operation sequences in GA optimization stage are produced by applying a stochastic topologic sort algorithm to the OPG. Production cost calculating model is taken as the criterion to evaluate the operation sequence quantitatively. The optimization approach can make a dynamical respond to the changes of plant resources and multiple optimal/suboptimal solutions could be obtained. Finally an illustrative example for a complicated part is given, and the test results testify the feasibility and validity of this developed method.

• 出版日期2017
• 单位华中农业大学