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

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