Assembly Sequence Planning based on Graduated NonConvexity and Concavity Procedure

Author

Zhipeng Tang ; Peng Wang ; Hong Qiao ; Zhiyong Liu ; Jing Tao

Author_Institution

Inst. of Autom., Beijing, China

fYear

2014

Firstpage

4933

Lastpage

4938

Abstract

Assembly Sequence Planning (ASP) is a NP-hard combinatorial problem. In order to reduce computational complexity, this paper proposes a novel assembly sequence planning approach based on Graduated NonConvexity and Concavity Procedure (GNCPP), a general optimization framework which approximately solve the combinatorial optimization problems defined on the set of partial permutation matrices. The mathematical model of ASP is transformed to matrix form and the gradient of the objective function is deduced to meet the requirement of GNCCP. In addition, an efficient searching algorithm is proposed for GNCCP. The comparison experiments demonstrate the effectiveness of the proposed method.

Keywords

assembling; combinatorial mathematics; computational complexity; concave programming; matrix algebra; production planning; ASP problem; GNCPP; NP-hard combinatorial problem; assembly sequence planning approach; combinatorial optimization problem; computational complexity reduction; general optimization framework; graduated nonconvexity and concavity procedure; objective function; partial permutation matrix; Algorithm design and analysis; Assembly; Genetic algorithms; Interference; Linear programming; Optimization; Planning; Assembly sequence planning; Combinatorial optimization; GNCCP;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Control and Automation (WCICA), 2014 11th World Congress on

Type

conf

DOI

10.1109/WCICA.2014.7053550

Filename

7053550