Single machine scheduling for minimising earliness and tardiness penalties by scatter search approach

This paper proposes a new evolutionary technique named scatter search for scheduling a number of jobs on a single machine against a restrictive common due date. Individual earliness and tardiness penalties for the jobs are under consideration and the objective is to find an optimal schedule, which jointly minimises the sum of the earliness and tardiness costs. In this paper, the results are obtained for numerous benchmark problems generated by Biskup and Feldmann (2001) for common due date (CDD) problems. The best results of each of the benchmark problems of the three meta-heuristic techniques used by Feldmann and Biskup (2003) are selected and they are compared with the results of SS. This methodology provides substantially better results than the benchmark problems. At the same time, this method holds almost the same result as the best results (best-FB) of three meta-heuristic approaches of Feldmann and Biskup (2003).