Pareto optima for total weighted completion time and maximum lateness on a single machine

We consider the single-machine bicriterion scheduling problem of enumerating the Pareto-optimal sequences with respect to the total weighted completion time and the maximum lateness objectives. We show that the master sequence concept originally introduced for 1|rj|∑wjUj1|rj|∑wjUj by Dauzère-Pérès and Sevaux is also applicable to our problem and a large number of other sequencing problems. Our unified development is based on exploiting common order-theoretic structures present in all these problems. We also show that the master sequence implies the existence of global dominance orders for these scheduling problems. These dominance results were incorporated into a new branch and bound algorithm, which was able to enumerate all   the Pareto optima for over 90% of the 1440 randomly generated problems with up to n=50n=50 jobs. The identification of each Pareto optimum implicitly requires the optimal solution of a strongly NP-hard problem. The instances solved had hundreds of these Pareto solutions and to the best of our knowledge, this is the first algorithm capable of completely enumerating all Pareto sequences within reasonable time and space for a scheduling problem with such a large number of Pareto optima.