DESIGN AND EVALUATION OF TABU SEARCH ALGORITHMS FOR MULTIPROCESSOR SCHEDULING

Using a simple multiprocessor scheduling problem as a vehicle, we expl ore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected mo ves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the mo st effective length of the tabu list depended on features of the algor ithm being used, but not on the size and complexity of the problem bei ng solved. The best combination of features included random blocking o f the tabu list, tasks as tabus and a greedy local search. An algorith m using these features was found to outperform a recently published al gorithm solving a similar problem.