An efficient heuristic for scheduling on identical parallel machines to minimize total tardiness

详细信息    查看全文

• 作者：B. Vincent^* ; ^{vincentb@isima.fr" class="auth_mail" title="E-mail the corresponding author} ; C. Duhamel^* ; ^{christophe.duhamel@isima.fr" class="auth_mail" title="E-mail the corresponding author} ; L. Ren^** ; ^{Libo.Ren@udamail.fr" class="auth_mail" title="E-mail the corresponding author} ; N. Tchernev^*** ; ^{Nikolay.Tchernev@udamail.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Scheduling ; Identical parallel machines ; Total tardiness ; simulated annealing
• 刊名：IFAC-PapersOnLine
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：49
• 期：12
• 页码：1737-1742
• 全文大小：521 K

文摘

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.