by Federico Pagnozzi and Thomas Stützle
2018
| Table of Contents |
Stochastic local search methods are at the core of many effective
heuristics for tackling different permutation flowshop problems
(PFSPs). Usually, such algorithms require a careful, manual
algorithm engineering effort to reach high performance. An
alternative to the manual algorithm engineering is the automated
design of effective SLS algorithms through building flexible
algorithm frameworks and using automatic algorithm configuration
techniques to instantiate high-performing algorithms. In this
paper, we automatically generate new high-performing algorithms for
some of the most widely studied variants of the PFSP. More in
detail, we (i) developed a new algorithm framework, EMILI, that
implements algorithm-specific and problem-specific building blocks;
(ii) define the rules of how to compose algorithms from the building
blocks; and (iii) employ an automatic algorithm configuration tool
to search for high performing algorithm configurations. With these
ingredients, we automatically generate algorithms for the PFSP with
the objectives makespan, total completion time and total tardiness,
which outperform the best algorithms obtained by a manual algorithm
engineering process.
Keywords: Scheduling, Stochastic Local Search, Automatic algorithm
design.