Speeding up a Rollout algorithm for complex parallel machine scheduling

Michele Ciavotta, Carlo Meloni and Marco Pranzo

International Journal of Production Research, 2016, vol. 54, issue 16, 4993-5009

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.

Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2016.1157276 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:54:y:2016:i:16:p:4993-5009

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2016.1157276

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().