A branch-and-bound algorithm for identical parallel-machine total completion time scheduling problem with preemption and release times. (17th August 2016) - Liaw, Ching-Fang
Abstract : 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.