Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20121290
Volume: 39
Issue: 9
Start Page Number: 2223
End Page Number: 2231
Publication Date: Sep 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: integer, heuristics, combinatorial optimization
Abstract:

In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered. The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances. The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.

Reviews

Required fields are marked *. Your email address will not be published.