A decomposition theory based on a dominance relation and composite jobs (Q1820683)

A decomposition theory which includes Sidney's decomposition theory as a special case is constructed by using new fundamentals such as a dominance relation which solves a sequencing problem without precedence constraints, a unique interpretation rule which restricts application of the dominance relation and a composite job (for a sequence of jobs) which plays a central role in developing a new decomposition algorithm. It applies to all problems involved in Sidney's theory. Moreover, it involves a problem which Sidney's theory does not involve, i.e., a class of problems equivalent to a one-machine minimum total weighted-completion time problem. The theory shows also that a variety of tie-breaking rules can be used in the decomposition algorithm, though it was uniquely determined in the previous theory.