The complexity of scheduling job families about a common due date

Family scheduling problems are characterized by a setup time structure where setups are only required between jobs from different families. We consider the problem of scheduling job families on parallel machines to minimize weighted deviation about a common due date. Various special cases of this problem have been considered in the literature. This note summarizes known complexity results and introduces new complexity results. We show that the total earliness/tardiness problem is unary NP-hard when the number of machines and families are arbitrary, thus generalizing an earlier result and answering a longstanding open question in the literature.