Skip to main content


Corporate InformationResearch & Development

Near Optimal Assembly Sequence Generation

— Presentation at SII2016 —

February 2, 2017

Report from Presenter

SII was held on December 13th to 15th at Sapporo Convention Center in Hokkaido, Japan. This international symposium widely covers system integration technologies such as, control, robotics, network system, hardware, software and platform system. 153 papers were presented in 22 sessions including 5 organized sessions.

Fig. 1 Disassembly state graph

The first day, due to unexpected heavy snow, Shin Chitose airport was closed. Not a few presenters could not arrived by the time of their sessions. The schedule was rearranged for them. The author changed the destination from Chitose to Asahikawa and arrived the session fifteen minutes delay, managed to present "Near optimum assembly sequence generation" in the original session, Automation systems. In this research, near optimal assembly sequence is automatically derived from an input 3D-CAD assembly model in practical time. There are over thirty people in the session mostly from Asian counties such that India, China, Korea, etc. Many questions were raised from viewpoints of business strategy or some technical issues such like assemble motion generation. It impressed that computer aided process planning is highlighted recently as one of the important technologies for IoT. Following is technical explanation for the presentation.

Fig. 2 Calculation of disassembly motion

Fig. 3 Graphical collision check on disassembly motion

Assembly sequence generation is known as NP complete problem which time complexity is factorial order of the number of the assembly components. Novel near optimal algorithm is proposed in order to compute assembly sequence with practical computation time. The proposed algorithm guarantees linear increase of computation time with regard to number of candidate assembly processes. Computation time and objective function values with respect to search space size are examined with a practical assembly product. Disassembly state graph which represents transition of disassembly process is proposed. Shortest path search Dijkstra algorithm is applied on the proposed disassembly state graph in order to find minimize objective function of assembly sequence. For the purpose to reduce size of disassembly state graph, a method which eliminate infeasible assemble process is proposed. Candidates of disassembly motion are derived from geometrical constraints in assembled components. Interference in each candidate disassemble motion is detected by graphic processing method to eliminate infeasible disassembly process. Evaluation indexes of disassembly process are introduced to reduce size of disassembly state graph. Edges of disassembly state graph is pruned based on scores of the evaluated indexes in order to reduce computation time. Computation time of proposed algorithm linearly increases with respect to maximum number of the brunch edges on each disassembly process. In 147 components assembly product, to find near optimal assembly sequence, proposed algorithm computes in 900 sec on the condition of 38 edges of maximum number of the brunch edges on each disassembly process. Convergence of the objective function value with respect to maximum number of branched edges is demonstrated. Computation time is controllable by maximum number of branched edges on each disassembly process.

Fig. 4 Total execution times

Fig. 5 Time comparison with linear programming vs. Dijkstra algorithm

(By ENOMOTO Atsuko)

  • Page top