A modified evolutionary programming for flow shop scheduling

In order to avoid premature convergence and to balance the exploration and exploitation abilities of simple evolutionary programming, this paper proposes a Modified Evolutionary Programming (MEP) for flow shop scheduling. Firstly, multiple populations are designed to perform a parallel search with random initialisation in divided solution spaces. Secondly, multiple mutation operators are designed to enhance the search templates. Thirdly, selection with a probabilistic updating strategy based on an annealing schedule like simulated annealing is applied to avoid the dependence on fitness functions and to avoid being trapped in a local optimum. Lastly, a re-assignment strategy for individuals is designed for every sub-population to fuse information and enhance population diversity. Simulation results based on some flow shop scheduling benchmarks show that the MEP is superior to the simple evolutionary programming and the well-known NEH constructive method. In addition, the MEP is general and can be applied for any classes of optimisation problems by suitable adjustment.