Abstract :
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 rankedorder 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.
Keywords :
combinatorial mathematics; computational complexity; flow shop scheduling; particle swarm optimisation; search problems; simulated annealing; FSP; INSERT neighborhood structure; JPR; MA; NP; PSO; PSOSA; PrMF; ROV; SA; assembly line; combinatorial FSP; flowshop scheduling problem; global exploration; global stochastic search; job precedence rule; local exploitation; local individual learning; local search intensity; nondeterministic polynomial-time hard combinatorial optimization problem; permutation solutions; probabilistic memetic algorithm; probabilistic memetic framework; ranked-order value rule based particle swarm optimization; semiconductor manufacturing; ship building; simulated annealing; Job shop scheduling; Measurement; Memetics; Optimization; Probabilistic logic; Processor scheduling; distance metric; flowshop scheduling; memetic algorithm (MA); particle swarm optimization (PSO); probabilistic memetic framework (PrMF); simulated annealing (SA);