Minimizing the sum of squares lateness on a single machine

This paper proposes a new procedure that considers the use of inserted idle time to optimally solve the single machine scheduling problem where the objective is to minimize the sum of squares lateness. A heuristic procedure is also proposed for this problem. These procedures and an existing procedure developed by Gupta and Sen are tested using problems of various sizes in terms of the number of jobs to be scheduled and for different degrees of due date tightness. The performance measures are CPU time and sum of squares lateness of the solutions generated. The results show that a simple descent procedure yields very good results and is efficient even on large problems.