A branch-and-bound algorithm for identical parallel-machine total completion time scheduling problem with preemption and release times. (17th August 2016)

• Record Type: Journal Article
• Authors: Liaw, Ching-Fang
• Is Part Of: Journal of industrial and production engineering. Volume 33:Number 6(2016)
• Page Start: 383
• Page End: 390
• Publication Date: 2016-08-17
• Subjects: scheduling -- parallel-machine -- branch-and-bound -- preemption -- release time; Industrial engineering -- Periodicals; Production engineering -- Periodicals; 620
• DOI: 10.1080/21681015.2016.1147087
• Languages: English
• ISSNs: 2168-1015

Abstract

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.