An efficient heuristic for scheduling on identical parallel machines to minimize total tardiness. Issue 12 (2016)

• Record Type: Journal Article
• Authors: Vincent, B.; Duhamel, C.; Ren, L.; Tchernev, N.
• Is Part Of: IFAC-PapersOnLine. Volume 49:Issue 12(2016)
• Page Start: 1737
• Page End: 1742
• Publication Date: 2016
• Subjects: Scheduling -- Identical parallel machines -- Total tardiness -- simulated annealing; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2016.07.833
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: This paper deals with the identical parallel machine scheduling problem to minimize total tardiness where each machine cannot have more than one job at a time. An efficient heuristic algorithm is proposed. It relies on a simulated annealing algorithm aimed at searching for a better solution during the schedule construction stage. The heuristic uses some well-known dominance properties for this problem which are usually used by exact methods and particularly by branch and bound algorithms. Some instances of the literature are used to show the effectiveness of this heuristic on computational results.