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.