Scheduling identical parallel machines to minimize total tardiness

This paper considers the problem of scheduling a given number of jobs on a specified number of identical parallel machines to minimize total tardiness. In view of its NP-hard nature, we propose a new heuristic approach which is general enough for solving several important types of parallel-machine scheduling problems. Consequently, we develop and evaluate an efficient heuristic algorithms for finding optimal or near-optimal schedules for the identical parallel-machine problem to minimize total tardiness. Computational results of empirical experiments involving the proposed and the three best available heuristics are used to identify the most effective heuristic algorithms for minimizing total tardiness.