Research On Identical Parallel Machine Scheduling Based On Improved Discrete Differential Evolution

The research on production scheduling has gained much prominence over the past decades, and a bunch of studies have been carried out on models and methods of scheduling problems. Due to the NP-hard nature of most scheduling problems, the classic scheduling theory and methods for scheduling problems have lots of problems. The intelligent optimization scheduling method springing up recently is a kind of simple yet powerful method for scheduling problems. It utilizes an artificial intelligent algorithm to yield a satisfactory schedule without a complex mathematical formulation, and it is one of the most effective ways to solve practical scheduling problems.This paper mainly focuses on the scheduling problem of identical parallel machines. Firstly, an improved discrete differential evolution algorithm, called DDE_VND, which is formed by hybridization of DDE with a local search algorithm, variable neighbourhood descent search (VND), is proposed for the identical parallel machine problem with makespan criterion. DDE_VND has advantages of both DDE and VND, and thus can strike a balance in both global exploration and local exploitation. The effectiveness of VND can be validated by experimental comparison of DDE_VND with DDE. Comprehensive computational experiments based on a benchmark set are conducted under the same running condition, and the computational results can significantly reveal the effectiveness of DDE_VND.Moreover, the DDE_VND algorithm is further improved to solve the parallel machine scheduling model with total tardiness criterion. A modified due date rule (MDD) is embedded into the DDE_VND algorithm in the initialization phase to form an improved algorithm MDDE_VND. Computational results of several problem instances illustrate the effectiveness of the rule. Furthermore, comprehensive computational experiments based on a benchmark set are conducted under the same software and hardware condition for MDDE VND, DDE and clonal selection particle swarm optimization (CSPSO), and optimal rates and evolutionary convergence curves reveal clearly the advantages of MDDE_VND. It is worth noting that the parameter setting of the algorithm is discussed for both the two parallel machine scheduling models. The analysis of variance (ANOVA) is performed to select a better parameter combination to use in comparative study.