Report Number: CS-TN-95-25
Institution: Stanford University, Department of Computer Science
Title: Complexity Measures for Assembly Sequences
Author: Goldwasser, Michael
Author: Latombe, Jean-Claude
Author: Motwani, Rajeev
Date: October 1995
Abstract: Our work examines various complexity measures for two-handed assembly sequences. Many present assembly sequencers take a description of a product and output a valid assembly sequence. For many products there exists an exponentially large set of valid sequences, and a natural goal is to use automated systems to attempt 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 plan 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 seems hard. In fact in the most general case, our results suggest that even finding an approximate solution is hard. Future work is directed towards using this model to study how the original geometric assumptions can be reintroduced to prove stronger approximation results.
http://i.stanford.edu/pub/cstr/reports/cs/tn/95/25/CS-TN-95-25.pdf