Minimizing Makespan with Release Dates in a Single Machine Scheduling Problem By Using Tabu Search

Abstract

This paper considers a single machine scheduling problem of minimizing makespan (Cmax)
which takes into consideration of real life aspects that includes release dates and sequence dependent setup
times for industrial size problem. The problem is proven to be NP-hard and therefore the only solution
available in the literature is by constructing heuristics. A metaheuristic which is Tabu search was developed
for solving the problem in this paper. Besides that, three initial solutions for the Tabu search based on
dispatching rules have been developed. Each of these dispatching heuristics serves as an initial solution to
the Tabu search besides playing a role in testing the efficiency of the final results of the Tabu search. Based
on the experiments conducted, tabu search was able to provide an improvement compared to the initial
solution in terms of the objective function although the magnitude of improvement was small.