Performance enhancements to tabu search for the early/tardy scheduling problem

Tabu search (TS) has been used to solve a number of NP-hard problems including the single machine early/tardy scheduling problem. Previous research has solved this particular problem using two different solution spaces. One solution space manipulates the order of jobs in the schedule to create new neighbours, while the other uses a binary solution space to specify which jobs are early and which jobs are tardy. This paper presents techniques for improving the performance of TS in solving large early/tardy scheduling problems, with a view to developing generalized TS enhancement strategies. Three specific techniques are investigated. The first uses a combination of two previously published candidate selection strategies. The second incorporates an extra diversification phase in the search and the third uses a hybrid TS method that uses two different solution spaces. Results show that these performance enhancement strategies produce similar results, all consistently better by at least 5% on the original TS methods used to solve this problem. The applicability of these enhancements to TS generally is discussed.