| Applying Tabu Search with In uential Diversi cation to Multiprocessor Scheduling (2007) | |||||||||||||
Abstract | |||||||||||||
| We describe a tabu search approach tothescheduling problem of minimizing the makespan on n tasks on m equivalent processors. This problem is isomorphic to a variant ofthemultiple bin packing problem. We make use of a candidate list strategy that generates only a small subset of all possible moves, and employ a dynamic tabu list for handling tabu restrictions. We also introduce an in uential diversi cation component toovercome an entrenched regionality phenomenon that represents a \higher order " di culty encountered by local search methods. In uential diversi cation notably improves the behavior and quality of the solutions of our tabu search procedure as the search horizon grows. Results are presented for a range of problems of varying dimensions, and our method is also compared to an extended simulated annealing approach that previously has produced the best solutions for the isomorphic bin packing problem. 1 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||