A branch-and-bound algorithm for identical parallel-machine total completion time scheduling problem with preemption and release times

This article examines the problem of scheduling preemptive jobs with release times on identical parallel machines to minimize total completion time. 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 11 jobs and 4 machines in size within a reasonable amount of time. The solution obtained by the heuristic has an average percentage deviation of less than 0.18% from the optimal value, while the initial lower bound has an average percentage deviation of less than 5.36% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 80% of the problem instances completely solved.