Dual-Space Co-Evolutionary Memetic Algorithm for Scheduling Hybrid Differentiation Flowshop With Limited Buffer Constraints

This article proposes a novel and efficient dual-space co-evolutionary memetic algorithm (DCMA) to tackle a practical hybrid differentiation flowshop scheduling problem with limited buffer constraints. In this scheduling problem, jobs are divided into different types and each job consists of multiple parts. The manufacturing of a job involves three stages: 1) parts fabrication on first-stage parallel machines; 2) parts assembly on second-stage single machine; and 3) job differentiation on one of third-stage dedicated machines. Due to the assembly operation and limited buffers between adjacent stages, deadlock and blocking will occur. We formulate the problem and present a deadlock handling policy to guarantee all schedules feasible. Then, we propose the DCMA metaheuristic to approximate the optimal solutions in acceptable time. Global exploration of DCMA is performed by a hybrid of three parts: 1) a continuous optimizer to be executed in continuous search space; 2) a discrete optimizer to be executed in combinatorial solution space; and 3) a meta-Lamarckian learning-based selection mechanism for adaptively determining that which optimizer is more suitable for current global exploration campaign. To balance exploration and exploitation, three problem-special local search strategies are presented, which collaborates with each other and are adaptively started to avoid high computational costs. The effect of parameter setting on DCMA is checked by the Taguchi method of design of experiment. The computational experiments demonstrate the effectiveness of DCMA special designs, and show that DCMA performs better than the existing algorithms for the considered problem.