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 n...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(97)00261-0