Rollout methodology is a constructive metaheuristic algorithm and its main characteristics are its modularity, the adaptability to different objectives and constraints and the easiness of implementation. Multi-heuristic Rollout extends the Rollout by incorporating several constructive heuristics in the Rollout framework and it is able to easily incorporate human experience inside its research patterns to fulfil complex requirements dictated by the application at hand. However, a drawback for both Rollout and multi-heuristic Rollout is often represented by the required computation time. This paper proposes some alternatives of the full multi-heuristic Rollout algorithm aimed at improving the efficiency by reducing the computational effort while preserving the effectiveness. Namely, we propose dynamic heuristics pruning and candidates reduction strategies. As illustrative case studies, we analyse complex deterministic identical parallel machine scheduling problems showing how Rollout procedures can be used to tackle several additional constraints arising in real contexts. More specifically, we considered both standard (batch production, family set-ups, release, due dates, etc.) and non-standard (machine unavailabilities, maximum campaign size) scheduling constraints. An extensive campaign of computational experiments shows the behaviour of the multi-heuristic Rollout approach and the effectiveness of the different proposed speed-up methods.

Speeding up a Rollout algorithm for complex parallel machine scheduling / Ciavotta, Michele; Meloni, Carlo; Pranzo, Marco. - In: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH. - ISSN 0020-7543. - 54:16(2016), pp. 4993-5009. [10.1080/00207543.2016.1157276]

Speeding up a Rollout algorithm for complex parallel machine scheduling

MELONI, Carlo;
2016

Abstract

Rollout methodology is a constructive metaheuristic algorithm and its main characteristics are its modularity, the adaptability to different objectives and constraints and the easiness of implementation. Multi-heuristic Rollout extends the Rollout by incorporating several constructive heuristics in the Rollout framework and it is able to easily incorporate human experience inside its research patterns to fulfil complex requirements dictated by the application at hand. However, a drawback for both Rollout and multi-heuristic Rollout is often represented by the required computation time. This paper proposes some alternatives of the full multi-heuristic Rollout algorithm aimed at improving the efficiency by reducing the computational effort while preserving the effectiveness. Namely, we propose dynamic heuristics pruning and candidates reduction strategies. As illustrative case studies, we analyse complex deterministic identical parallel machine scheduling problems showing how Rollout procedures can be used to tackle several additional constraints arising in real contexts. More specifically, we considered both standard (batch production, family set-ups, release, due dates, etc.) and non-standard (machine unavailabilities, maximum campaign size) scheduling constraints. An extensive campaign of computational experiments shows the behaviour of the multi-heuristic Rollout approach and the effectiveness of the different proposed speed-up methods.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/11573/1583517
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact