A New Solution Approach to the General Min-Max Sequencing Problem

We present a simple, elegant algorithm for finding an optimal solution to a general min-max sequencing problem. This problem assumes many well-known scheduling problems as special cases, including problems with regular objectives (e.g., maximum lateness, maximum tardiness) as well as ones with non-regular objectives (e.g., maximum earliness-tardiness). Our algorithm is a dichotomy procedure in which highly efficient methods for the single-machine min-max lateness problem are leveraged. Despite the NP-hard nature of the problem in question, our method proves to be effective even for large-scale problem instances with hundreds of jobs. Through extensive numerical experiments, we demonstrate the working of our method on three different problem types, i.e., the maximum weighted completion time problem, the maximum weighted lateness problem, and the maximum weighted earliness-tardiness problem. The results show that the proposed method is effective for min-max sequencing problems.