A rescheduling heuristic for the single machine total tardiness problem

A rescheduling heuristic for the single machine total tardiness problem

0.00 Avg rating0 Votes
Article ID: iaor200962785
Country: South Africa
Volume: 22
Issue: 1
Start Page Number: 77
End Page Number: 87
Publication Date: Jan 2006
Journal: ORiON
Authors:
Keywords: heuristics
Abstract:

In this paper, we propose a rescheduling heuristic for scheduling N jobs on a single machine in order to minimise total tardiness. The heuristic is of the interchange type and constructs a schedule from the modified due date (MDD) schedule. Unlike most interchange heuristics that consider interchanges involving only two jobs at a time, the newly proposed heuristic uses interchanges that may involve more than two jobs at any one time. Experimental results show that the heuristic is effective at reducing total tardiness producing schedules that either similar or better than those produced by the MDD alone. Furthermore, when applied to some test problems the heuristic found optimal schedules to all of them.

Reviews

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