¹Nanyang Technological University, Singapore

Correspondence: P M E Shutler, Mathematics and Mathematics Education AG, National Institute of Education, Nanyang Technological University, 1 Nanyang Walk, Singapore, 637616, Singapore. E-mail: shutler@nie.edu.sg

Received July 2003; Accepted February 2004.

Abstract

Following a recent paper by the same author, a priority list-based tabu search heuristic is compared with the leading schedule-based tabu search heuristic of Nowicki and Smutnicki. More search neighbourhoods are required to achieve a given average makespan, but each priority list neighbourhood is searched much faster than the corresponding neighbourhood in the space of feasible schedules. Priority list-based tabu search therefore outperforms schedule-based tabu search in terms of elapsed CPU time.