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

Authors: M. Saravanan; A. Noorul Haq

Addresses: PVP College of Engineering & Technology for Women, K. Sinkarakottai, Dindigul-Batlagundu Highways, Dindigul, Tamil Nadu, 624 702, India. ' Department of Production Engineering, National Institute of Technology, Tiruchirappalli, Tamil Nadu, India

Abstract: 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).

Keywords: single machine scheduling; metaheuristics; scatter search; tardiness; earliness; benchmark; common due dates.

DOI: 10.1504/IJET.2011.043111

International Journal of Electronic Transport, 2011 Vol.1 No.1, pp.5 - 25

Received: 03 Nov 2010
Accepted: 25 Jan 2011
Published online: 11 Jan 2015 *