A HEURISTIC APPROACH TO MINIMISING MAXIMUM LATENESS ON A SINGLE MACHINE

Abstract

This paper focuses on the problem of scheduling on a single machine to minimise the maximum lateness when each job has a different ready time, processing time, and due date. A simple procedure is developed to find a better solution than the early due date (EDD) algorithm. The new algorithm suggested in this paper is called Least Slack Time Look Ahead (LST-LA), which minimises the maximum lateness problem. Computational results show that when the number of jobs increases, LST-LA outperforms EDD.