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.

Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach / Ghirardi, Marco; C. N., Potts. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 165:2(2005), pp. 457-467. [10.1016/j.ejor.2004.04.015]

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

GHIRARDI, MARCO;
2005

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/1400713
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo