A decomposition scheme for single stage scheduling problems

This paper introduces a general decomposition scheme for single stage scheduling problems with jobs that have arbitrary release dates. We assume that the objective function is monotone in the completion time of each job. The decomposition scheme has significant theoretical and practical relevance. When assuming equal processing times, we can reduce the number of steps required to solve several well-known nonpreemptive single machine scheduling problems by 𝒪(n³), provided the processing time p is constant. Specifically, we develop new approaches that solve the problems 1∣r i,pi=p∣Σf i(C i) and 1∣r i ,p i =p∣Σw i U i in 𝒪(n⁴) time; the algorithms that have been described in the literature for these problems operate in 𝒪(n⁷). Moreover, solution approaches for NP-hard problems with unequal processing times may also benefit from our decomposition rule. This is particularly true if p max/p min is close to 1. Using the decomposition rule, either the problem size is reduced or additional information about the maximal schedule length is obtained.