Title: Dominance orders for scheduling problems

A partial order on the set of jobs in a scheduling problem is a dominance order if there is an optimal sequence for the jobs which is a linear extension of the order. We consider a new technique, called subset-restricted pairwise interchange, which can be used to interchange pairs of jobs around subsets of jobs satisfying certain conditions, without increasing the cost of the schedule. We use a new interchange operator, we call Shuffle Interchange, which generalizes well-known interchange operators used in scheduling theory. Using SI, we derive dominance orders for various one- and two-machine scheduling problems and give a unified treatment of all these dominance orders. These orders allow us to reduce the search space for solution algorithms, and result in substantial reductions in running time.