We consider the problem of scheduling n multi-operation jobs on a single machine. Each job comprises up to F operations that belong to different families. Changeovers of production from one family to another have associated set-up times. A job completes when all of its operations have been processed. This type of problem arises in the manufacture of food products. It combines the batching aspect of the well-known family scheduling models with an assembly element (where the job's operations are assembled to make the final product). Our analysis covers three classic optimality criteria: the maximum lateness, the weighted number of late jobs, and the sum of job completion times. We show that the problem of minimizing the maximum lateness is equivalent to its counterpart without assembly. This enables us to derive extensions of known complexity results and to indicate appropriate algorithms. The number of late jobs problem is shown to be binary NP-hard when there are two families, and unary NP-hard when there are an arbitrary number of families, even when all set-up times are identical. For a fixed number of families, we give a dynamic programming algorithm to minimize the weighted number of late jobs, which requires pseudo-polynomial running time. A similar algorithm solves the sum of completion times problem in polynomial time, under the additional assumption that the processing times of operations between families are agreeable.
