CHARLA SEMI PLANARIA: Scheduling with simple Iterated Greedy Algorithms

Autores UPV
Año
CONGRESO CHARLA SEMI PLANARIA: Scheduling with simple Iterated Greedy Algorithms

Abstract

Nowadays scheduling problems are mainly solved with modern metaheuristics. These methods are capable of producing close to optimal solutions for instances of realistic size in a matter of minutes. Metaheuristics have matured and evolved with hundreds of papers being published every year with applications to most domains. Most regrettably, some of these methods are complex in the sense that they have many parameters that affect performance and hence need careful calibration. Furthermore, many times published results are hard to reproduce due to specific speed-ups being used or complicated software constructs. These complex methods are difficult to transfer to industries in the case of scheduling problems. Another important concern is the recently recognized ¿tsunami¿ of novel metaheuristics that mimic the most bizarre natural or human processes, as for example intelligent water drops, harmony search, firefly algorithms and the like. See K. Sörensen ¿Metaheuristics¿The Metaphor exposed¿ (2015), ITOR 22(1):3-18. In this presentation, we will introduce Iterated Greedy (IG) algorithms. These methods are inherently simple with very few parameters. They are easy to code and results are easy to reproduce. We will show that for all tested problems so far they show state-of-the-art performance despite their simplicity. As a result, we will defend the choice of simpler, yet good performing approaches over complicated metaphor-based algorithms. We will explain the foundations of the IG, the simple destruction-reconstruction loop and we will comment on the advantages and drawbacks of the IG. We will show comparisons with other methods from the literature, with special emphasis on scheduling problems and more precisely on flowshop scheduling and parallel machine settings.