Complexity measures for assembly sequences

We examine various complexity measures for two-handed assembly sequences. For many products there exists an exponentially large set of valid sequences, and a natural goal is to use automated systems to select wisely from the choices. Since assembly sequencing is a preprocessing phase for a long and expensive manufacturing process, any work towards finding a "better" assembly sequence is of great value when it comes time to assemble the physical product in mass quantities. We take a step in this direction by introducing a formal framework for studying the optimization of several complexity measures. This framework focuses on the combinatorial aspect of the family of valid assembly sequences, while temporarily separating out the specific geometric assumptions inherent to the problem. With an exponential number of possibilities, finding the true optimal cost solution is non-trivial. In the most general case, our results show that even finding an approximate solution is hard. Furthermore, we can show several hardness results, even in simple geometric settings. Future work is directed towards using this model to study how the original geometric assumptions can be reintroduced to prove stronger approximation results.

Authors

• Michael H. Goldwasser
• Jean-Claude Latombe
• Rajeev Motwani 0001

Keywords

• Assembly
• Solid modeling
• Manufacturing processes
• Whales
• Cost function
• Computer science
• Automation
• Humans
• System testing
• Polynomials
• Complexity Measures
• Sequence Assembly
• Valid Sequences
• Hardness Results
• Number Of Steps
• Estimation Algorithm
• Directed Graph
• Problem Instances
• Public Key
• Version Of Problem
• Cost Of Solution
• Single Part
• Decomposition Problem
• NP-complete Problem
• Motion Classification
• Set Cover Problem