![Sample our Engineering & Technology journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5933/TOC-Subject-Sample-2021-Engineering-Tech.jpg"})
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.