Decomposition in single-machine scheduling

This paper discusses the recent research on decomposition techniques in single-machine scheduling. A variety of orderings between adjacent and nonadjacent jobs in an optimal scheduling are presented. A list of decomposition rules is given that enable one to solve large size instances of six single-machine models. A partition technique is also developed to determine the optimal completion times of a general earliness–tardiness model for a given arrangement of jobs.