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.

KEYWORDS:

• Parallel machines
• scheduling
• sequence dependent setup times
• additional resources
• metaheuristics
• GRASP

Acknowledgments

Finally, special thanks are due to Luis Fanjul-Peyro, who kindly provided us with the solutions to the benchmark, which have been used for assessing the quality of our algorithm.

Data availability statement

The authors confirm that the data supporting the findings of this study are available within the article [and/or] its supplementary materials.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The authors would like to acknowledge the support from Ministerio de Ciencia e Innovación under grant PID2020-114594G Optimisation on data science and network design problems: large scale network models meet optimisation and data science tools, from the Junta de Andalucía under grant AT21_00032 Optimización Aplicada al Tejido Productivo Andaluz, and from the Generalitat Valenciana under grant NUevos REtos en SEcuenciación (No.  AICO/2020/049). Juan C. Yepes-Borrero acknowledges financial support by COLFUTURO under program Crédito-Beca grant number 201503877 and from El Instituto Colombiano de Crédito Educativo y Estudios Técnicos en el Exterior – ICETEX under program Pasaporte a la ciencia – Doctorado, Foco-reto país 4.2.3, grant number 3568118.

Notes on contributors

Axel Lopez-Esteve

Axel-López Esteve received Master's degree in Computer Science at the Universitat Politècnica de València (Spain) in 2020. He is currently a software engineer at Minisait (Spain).

Federico Perea

Federico Perea received Bachelor's degree in Mathematics, and PhD in Operations Research at the Universidad de Sevilla (Spain) in 2007. He is currently an associate professor at the Department of Applied Mathematics II, and general secretary of the Institute of Mathematics, at the same university. He has published over 30 research papers in different areas of operations research.

Juan C. Yepes-Borrero

Juan C. Yepes-Borrero received Bachelor's degree in Industrial Engineering, Master's degree in Statistics and Operations Research, and PhD in Operations Research at the Universitat Politècnica de València (Spain) in 2020. He is currently an assistant professor at the School of Engineering, Science and Technology at the Universidad del Rosario (Colombia). He has published several papers on scheduling.