Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 165, Issue 2, Pages 457-467Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2004.04.015
Keywords
scheduling; unrelated machines; beam search
Ask authors/readers for more resources
This paper considers the problem of scheduling jobs on unrelated parallel machines to minimize the makespan. Recovering Beam Search is a recently introduced method for obtaining approximate solutions to combinatorial optimization problems. A traditional Beam Search algorithm is a type of truncated branch and bound algorithm approach. However, Recovering Beam Search allows the possibility of correcting wrong decisions by replacing partial solutions with others. We develop a Recovering Beam Search algorithm for our unrelated parallel machine scheduling problem that requires polynomial time. Computational results show that it is able to generate approximate solutions for instances with large size (up to 1000 jobs) using a few minutes of computation time. (c) 2004 Published by Elsevier B.V.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available