Probabilistic Memetic Algorithm for Flowshop Scheduling

The flowshop scheduling problem (FSP) is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem with strong engineering background in semiconductor manufacturing, assembly line, and ship building et al. In the last decade, Memetic Algorithms (MAs) have been demonstrated to achieve superior performance to their counterparts on FSP. Recently, a Probabilistic Memetic Framework (PrMF) has been presented to balance global exploration and local exploitation by governing the learning intensity of each individual according to a theoretical upper bound at runtime. In contrast to PrMF dedicated for continuous optimization problems, in this paper we extend the PrMF for solving combinatorial FSP. In particular, a novel distance metric, called Job Precedence Rule (JPR), is defined for permutation based FSP which serves as a suitable measure on closeness or similarity between two permutation solutions. Then, an estimation scheme of the upper bound for local search intensity of each individual is used to control the level of global exploration versus local exploitation by comparing with its expected local search intensity. In principle, any MAs for FSP could be equipped with the proposed combinatorial version of PrMF, and in this study we consider the MA (PSOSA) in which the ranked-order value (ROV) rule based Particle Swarm Optimization (PSO) acts as the global search strategy, while Simulated Annealing (SA) with INSERT neighborhood structure acts as the individual learning scheme. Simulation results based on well-known FSP benchmarks and comparisons demonstrate that the combinatorial version of PrMF could yield improved search performances when embedded into the PSOSA, which suggests that in contrast to MA with fixed local search frequency, the adaptive individual learning intensity could achieve better balance between global stochastic search and local individual learning.