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

ABSTRACT

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.

GRAPHICAL ABSTRACT

KEYWORDS:

• Operation sequencing
• operation precedence graph
• hybrid algorithm

Acknowledgements

The authors would like to thank the National Natural Science Foundation of China [grant number 51405179] for financial support.

ORCID

Weijun Huang http://orcid.org/0000-0003-0015-4790

Weiguo Lin http://orcid.org/0000-0002-4138-1714

Shengyong Xu http://orcid.org/0000-0003-4442-1168