A rescheduling heuristic for the single machine total tardiness problem
AbstractIn 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.
The following license applies:
Attribution CC BY
This license lets others distribute, remix, tweak, and build upon your work, even commercially, as long as they credit you for the original creation.