¹Hanyang University, Seoul, South Korea

Correspondence: D-H Lee, Department of Industrial Engineering, Hanyang University, Sungdong-gu, Seoul 133-791, South Korea. E-mail: leman@hanyang.ac.kr

Received January 2007; Accepted June 2008; Published online 17 September 2008.

Abstract

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.