Earliness/tardiness scheduling with a common due date and family setups

We examine the problem of scheduling jobs, on a single processor to minimise the total earliness and tardiness costs about a common due date. Jobs belong to mutually exclusive families and a sequence independent setup task is required when processing switches from a job of one family to a job of another. We extend earlier results to obtain necessary optimal conditions for this problem. These are then used to generate a fast heuristic. Its performance is compared with a lower bound, a greedy heuristic, a genetic algorithm and for small problems, the optimal solution.