1. ¹Department of Information Management, Huafan University, Taipei, Taiwan
2. ²Department of Industrial Engineering and Management Information, Huafan University, Taipei, Taiwan

Correspondence: S-W Lin, Department of Information Management, Huafan University, No. 1 Huafan Road, Shihtin Hsiang, Taipei Hsien, Taiwan 223, Taiwan. E-mail: swlin@cc.hfu.edu.tw

Received July 2006; Accepted March 2007; Published online 20 June 2007.

Abstract

Scheduling problems in real systems often require sequence-dependent setup times. The topic of sequence-dependent setup times has not been addressed adequately, and improved competitiveness is thus not achieved. This study proposes a hybrid approach that takes advantage of simulated annealing (SA) and tabu search (TS) to solve single-machine tardiness problems with sequence-dependent setup times. To verify the proposed approach, experiments were conducted on benchmark problem sets that included both the weighted and un-weighted tardiness problems. The results show that the performance of the hybrid approach is superior to that of the SA, genetic algorithm, TS and ant colony optimization approaches, and is comparable with the Tabu-VNS approach. And the proposed approach found new upper bound values for many benchmark problems with an acceptable computational time.