Hypergraph models and algorithms for the assembly problem

Abstract

We consider the problem of finding an optimal set of feasible assembly operations in order to derive a desired product from a given set of parts. We show that optimal solutions, under different objective functions, can be obtained by means of computationally efficient hypergraph algorithms. In particular, we consider the case in which one wants to minimize the duration with an unlimited degree of parallelism. Finally, a new fast algorithm is presented in order to assign operations to robots in an optimal way when the degree of parallelism is bounded. Technical Report TR-6/92 March, 1992 (revised: July, 1992) This research has been supported by "Ministero dell'Universit e della Ricerca Scientifica e Tecnologica", National Project on "Gestione dei flussi nei sistemi flessibili di produzione". 2 Introduction In robotic assembly systems, one or more types of items are produced by assembling together several parts given in input, according to a properly defined assembly plan. An asse...