Title

An Effective Heuristic for Minimizing Makespan on Unrelated Parallel Machines

Document Type

Article

Language

eng

Format of Original

9 p.

Publication Date

1998

Publisher

Palgrave Macmillan

Source Publication

The Journal of the Operational Research Society

Source ISSN

0160-5682

Abstract

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.

Comments

The Journal of the Operational Research Society, Vol. 49, No. 8 (August, 1998): 886-894 . Permalink.