A weighted assembly precedence graph for assembly sequence planning

Assembly sequence planning is one of the well-known combinatorial optimization problems in manufacturing. An assembly is often represented as an assembly relation graph or precedence graph. The traditional methods are used to generate a large number of feasible assembly sequences and then find the optimal sequence through evaluation. A lot of computation resources are needed. To reduce the complexity of assembly sequence planning, the assembly is converted into a weighted assembly precedence graph considering multiple assembly constraints, i.e., the qualitative and quantitative constraints. The vertices in the weighted precedence graph are the parts or components. The qualitative constraints including the topological and geometrical assembly constraints guarantee to derive the feasible assembly sequences. Some process constraints are also taken as the qualitative constraints. They are represented as the directed edges in the weighted assembly precedence graph. The other assembly constraints, such as the stable support, connector strength, changes of assembly directions, and tools and so forth, are quantified as indices to compute the cost of assembly relations with the fuzzy analytical hierarchy process. The costs are taken as the heuristic information to find the optimal or near-optimal assembly sequences. With the weighted assembly precedence graph, the search space of the optimal assembly sequence will be reduced. We design a minimum spanning tree-based algorithm to detect the optimal assembly sequence based on the weighted assembly precedence graph. The optimal assembly sequences are found in O(n (3)) computation time, where n is the number of the discrete parts.