A Tabu Search Algorithm for Single Machine Scheduling with Release Times,Due Dates,and Sequence-Dependent Set-up Times |
| |
Authors: | H J Shin C-O Kim S S Kim |
| |
Affiliation: | (1) Department of Industrial Engineering, Korea University, Anam-dong, Sungbuk-gu, Seoul, Republic of Korea, KR;(2) School of Computer Science and Industrial Engineering, Yonsei University, Shinchon-dong, Seoul, Republic of Korea, KR |
| |
Abstract: | In this paper, we present a tabu search algorithm that schedules N jobs to a single machine in order to minimise the maximum
lateness of the jobs. The release times, due dates, and sequence-dependent set-up times of the jobs are assumed to exist.
We modified the original tabu search method to be suitable for the scheduling problem. The proposed tabu search algorithm
is composed of two parts: a MATCS (modified apparent tardiness cost with set-ups) rule for finding an efficient initial solution,
and the tabu search method to seek a near optimal solution from the initial solution. The experimental results show that the
tabu search algorithm obtains much better solutions more quickly than the RHP (rolling horizon procedure) heuristic suggested
by Ovacik and Uzsoy. |
| |
Keywords: | : Due dates Heuristic algorithm Release times Scheduling Sequence-dependent set-up times Tabu search |
本文献已被 SpringerLink 等数据库收录! |
|