A note on minimum makespan assembly plans

An important class of problems in manufacturing are those in which there is an item to be produced, a set of components which can be assembled together to produce the item, and a set of identical machines capable to perform the assembly operations. After discussing several optimality criteria, we address the problem in which we want to select a sequence of assembly operations (assembly plan), and schedule the selected operations on the machines, in such a way to minimize the makespan. This problem generalizes P|tree|Cmax, i.e., the minimum makespan machine scheduling problem with tree-type precedence constraints, where the list of operations to be scheduled is known a priori. We show that the problem can be quite naturally modelled making use of Directed Hypergraphs, and describe a general heuristic, showing that in a particular but still relevant case it yields solutions with a bounded relative error. Computational results are presented.