Abstract
This article examines the problem of scheduling preemptive jobs on identical parallel machines to minimize total tardiness. The problem is known to be NP-hard. An efficient heuristic is developed for solving large-sized problems. A lower bound scheme is also presented. Both of the proposed heuristic and lower bound are incorporated into a branch-and-bound algorithm to optimally solve small-sized problems. Computational results are reported. The branch-and-bound algorithm can handle problems of up to 16 jobs and 5 machines in size within a reasonable amount of time. The solution obtained by the heuristic has an average percentage deviation of 4.01% from the optimal value, while the initial lower bound has an average percentage deviation of 41.55% from the optimal value. Moreover, the heuristic finds approved optimal solutions for more than 45% of the problem instances tested.