# Minimum Makespan Assembly Plans

An important class of problems in manufacturing system are those in
which there is an item to be produced, a set of components which can
be assembled together in order to obtain the wanted item, and a set of
machines which are capable to perform the assembly operations.
Here we consider the case in which one wants to find an optimal
list of assembly operations. After discussing several optimality
criteria, we address the problem in which the assembly operations
are to be chosen in such a way that they can be scheduled on the
available machines at minimum makespan.
We show that these problems can be quite naturally modelled making use
of Directed Hypergraphs, and describe a general heuristics, showing
that in a particular but still relevant case, it yields solutions
whose relative error is bounded. We present also a special class of
assembly problems which can be solved in polynomial time by means of
hyperpath computations.