Complexity Measures for Assembly Sequences
		Michael Goldwasser, Ph.D.
                Stanford University, 1997



Our work focuses on various complexity measures for two-handed
assembly sequences.  For many products, there exist an exponentially
large set of valid sequences, and a natural goal is to use automated
systems to select wisely from the choices.  Although there has been a
great deal of algorithmic success for finding feasible assembly
sequences, there has been very little success towards optimizing the
costs of sequences.  We attempt to explain this lack of progress, by
proving the inherent difficulty in finding optimal, or even
near-optimal, assembly sequences.

We begin by introducing a formal framework for studying the
optimization of complexity measures for assembly sequencing.  Based on
the previous work of both researchers and practitioners, we collect a
list of various cost measures, goals, and restrictions that other have
considered desirable.  Together with this, we define, {\em virtual
assembly sequencing}, a graph-theoretic problem that is a
generalization of assembly sequencing, focusing on the combinatorial
aspect of the family of feasible assembly sequences, while temporarily
separating out the specific geometric assumptions inherent to assembly
sequencing.


We examine several intuitive, yet unsuccessful, heuristics for
optimizing the cost of sequences, giving constructions which result in
worst case performance, while also testing these heuristics
experimentally on several products, previously used as a test bed for
research in assembly sequencing.  Because of this lack of success in
designing approximation algorithms, we continue by examining the
source of difficulty in these problems.  We formally prove the
hardness of finding even near--optimal sequences for most cost
measures in our generalized framework.  As a special case, we prove
similar, strong inapproximability results for the problem of
scheduling with AND/OR precedence constraints.


Of course, hardness results in our generalized framework do not
immediately carry over to the original geometric problems.  It may be
that hard instances of our graph-theoretic problem do not
arise from the geometric settings originally part of the assembly
sequencing problems.  Therefore, we re-introduce the geometry, and
continue by realizing several of these hardness results in rather
simple geometric settings.  We are able to show strong
inapproximability results in far simpler settings than the domain of
most assembly sequencers, for example using an assembly consisting
solely of unit disks in the plane.