Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach

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 optimiztion 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.