A branch-and-bound algorithm for identical parallel machine total tardiness scheduling problem with preemption. (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: 426
• Page End: 434
• Publication Date: 2016-08-17
• Subjects: scheduling -- parallel machine -- branch-and-bound -- preemption; Industrial engineering -- Periodicals; Production engineering -- Periodicals; 620
• DOI: 10.1080/21681015.2016.1147088
• Languages: English
• ISSNs: 2168-1015

Abstract

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.