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

• Published in: European journal of operational research 1998-04, Vol.106 (2), p.254-265
• Main Authors: James, R.J.W., Buchanan, J.T.
• Format: Article
• Language: English
• Subjects: Algorithms; Early/tardy scheduling; Heuristic; Heuristics; Job shops; Operations research; Production scheduling; Studies; Tabu search
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/S0377-2217(97)00261-0

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.