Speeding up a Rollout algorithm for complex parallel machine scheduling
| Autor: | Carlo Meloni, Marco Pranzo, Michele Ciavotta |
|---|---|
| Přispěvatelé: | Ciavotta, M, Meloni, C, Pranzo, M |
| Rok vydání: | 2016 |
| Předmět: |
Job scheduler
0209 industrial biotechnology Engineering Mathematical optimization Strategy and Management media_common.quotation_subject Strategy and Management1409 Tourism 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research job scheduling parallel machines Pilot method Rollout algorithm Industrial and Manufacturing Engineering Strategy and Management1409 Tourism Leisure and Hospitality Management computer.software_genre Modularity Constructive Adaptability Reduction (complexity) 020901 industrial engineering & automation Pruning (decision trees) Metaheuristic media_common 021103 operations research business.industry Leisure and Hospitality Management parallel machine business Heuristics computer Algorithm Job scheduling |
| Zdroj: | International journal of production research 54 (2016): 4993–5009. doi:10.1080/00207543.2016.1157276 info:cnr-pdr/source/autori:Ciavotta M.; Meloni C.; Pranzo M./titolo:Speeding up a Rollout algorithm for complex parallel machine scheduling/doi:10.1080%2F00207543.2016.1157276/rivista:International journal of production research (Print)/anno:2016/pagina_da:4993/pagina_a:5009/intervallo_pagine:4993–5009/volume:54 |
| ISSN: | 1366-588X 0020-7543 |
| DOI: | 10.1080/00207543.2016.1157276 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |