A Random Key based Estimation of Distribution Algorithm for the Permutation Flowshop Scheduling Problem

Abstract

Random Key (RK) is an alternative representation for permutation problems that enables application of techniques generally used for continuous optimisation. Although the benefit of RKs to permutation optimisation has been shown, its use within Estimation of Distribution Algorithms (EDAs) has been a challenge. Recent research proposing a RK-based EDA (RK-EDA) has shown that RKs can produce competitive results with state of the art algorithms. Following promising results on the Permutation Flowshop Scheduling Problem, this paper presents an analysis of RK-EDA for optimising the total flow time. Experiments show that RK-EDA outperforms other permutation-based EDAs on instances of large dimensions. The difference in performance between RK-EDA and the state of the art algorithms also decreases when the problem difficulty increases.