Abstract: 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. 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. 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 others have considered desirable. Together with this, we define 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. In this "virtual assembly sequencing" model, we are still able to explain the success of previous algorithms in finding feasible sequences efficiently.
At this point, we begin to consider the approximability of the various cost measures for sequencing, and we examine the lack of success in optimizing the costs. 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 show how these problems capture the combined difficulty of several covering, scheduling, and sequencing problems from the literature. We use techniques common to the theory of approximability to prove the hardness of finding even near--optimal sequences for most cost measures in our generalized framework. Our strongest lower bounds prove that finding any solution within a 2log1-γn-factor of the optimal cost solution is quasi-NP-hard for any γ>0. 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.
In the face of our results, the overwhelming open problem is to design any non-trivial approximation algorithms for minimizing the cost of assembly sequencing. In our general setting, we give strong lower bounds, however there is still a gap between the trivial upper bound, and so it would be interesting to develop an algorithm that is able to match the lower bounds. Furthermore, it would be quite valuable to identify any practical geometric settings not considered by us, that would allow for approximation-algorithms which are able to break our generalized lower bounds.