GRASP algorithms for the unrelated parallel machines scheduling problem with additional resources during processing and setups

Abstract

This paper addresses an unrelated parallel machines scheduling problem with the need of additional resources during the processing of the jobs, as well as during the setups that machines need between the processing of any two jobs. This problem is highly complex, and therefore in this paper we propose several constructive heuristics to solve it. To improve the performance of these heuristics, we propose several variations, including randomisation with different probability distributions and a local search phase, having this way GRASP algorithms. The results of extensive experiments over randomly generated instances show several findings on the different parameters that characterise our constructive algorithms. In particular, we highlight the fact that non-uniform probability distributions might be advisable for choosing elements of a restricted candidate list in GRASP algorithms.