Viral mutation-inspired evolutionary algorithm for permutation flowshop scheduling

Efficient algorithms for solving the Non-deterministic Polynomial-time (NP-) hard problems are essential in various manufacturing industries, where even minute optimisation gains in scheduling large-scale tasks on industrial machines can lead to considerable economisation of resources. We present an original evolutionary algorithm for solving a well-known common NP-hard problem, the Permutation Flowshop Scheduling. Taking inspiration from the occurrence patterns of eight known types of viral mutations, MuVE (Mutation-inspired Viral Evolutionary algorithm) focuses the computing power of its search process toward optimal solutions on narrow areas rather than the entire possible search domain. Renewing the population of individuals by circular composition of permutations is triggered by the algorithm’s convergence and does not necessarily occur with each iteration. The diversity of the population is ensured by an exclusion criterion based on the distance calculation given by the Kendall-Tau correlation. Through detailed statistical analysis of the results, we demonstrate that MuVE, given limited processing time and resources, is capable of outperforming prime examples of related methods in most instances and also, in a considerable proportion of cases, of equalising benchmark upper bounds in the problem sets of Taillard, Carlier, Heller, Reeves and Lahiri.