Single-machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs

This research considers a single-machine scheduling problem with the objective of minimizing the summation of the weighted earliness and tardiness, subject to the number of tardy jobs. There are n jobs with a given common due date and each job has different weights for earliness and tardiness. We propose a pareto-optimal solution algorithm, by which we can efficiently generate pareto-optimal solutions for any possible number of tardy jobs. We also work with the benchmark problems discussed in Biskup and Feldmann [2001. Benchmarks for scheduling on a single-machine against restrictive and unrestrictive common due dates. Computers and Operations Research 28, 787-801] to show the superior accuracy and run time of our algorithm. The computational analysis also shows that approximately 47.15% of the nodes in the branching tree can be eliminated. (c) 2007 Elsevier B.V. All rights reserved.