Applying tabu search with influential diversification to multiprocessor scheduling

Applying tabu search with influential diversification to multiprocessor scheduling

0.00 Avg rating0 Votes
Article ID: iaor1995554
Country: United Kingdom
Volume: 21
Issue: 8
Start Page Number: 877
End Page Number: 884
Publication Date: Oct 1994
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

The authors describe a tabu search approach to the scheduling problem of minimizing the makespan on n tasks on m equivalent processors. This problem is isomorphic to a variant of the multiple bin packing problem. The authors 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. They also introduce an influential diversification component to overcome an entrenched regionality phenomenon that represents a ‘higher order’ difficulty encountered by local search methods. Influential diversification notably improves the behavior and quality of the solutions of the present tabu search procedure as the search horizon grows. Results are presented for a range of problems of varying dimensions, and the method is also compared to an extended simulated annealing approach that previously has produced the best solutions for the isomorphic bin packing problem.

Reviews

Required fields are marked *. Your email address will not be published.