A rescheduling heuristic for the single machine total tardiness problem

Nyirenda, J C

A rescheduling heuristic for the single machine total tardiness problem

Journal Article

2006

Journal Title

ORION: Operations Research in South Africa

Link to Journal

http://orion.journals.ac.za/pub

Publisher

University of Cape Town

Department

Department of Statistical Sciences

Faculty

Faculty of Science

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.