Self-Adaptive Biased Differential Evolution for Scheduling Against Common Due Dates

Differential evolution (DE) is a robust population-based metaheuristic for optimization over continuous spaces. Its performance is affected by two main components, namely, the scheme to generate new offspring solutions and the control parameters which drive its power towards the global optimum. These two components are in turn dependent on the nature of the optimization problem to be solved and the landscape characteristics of the objective function. This paper investigates the performance of a novel self-adaptive DE (saDE) algorithm for solving a classical NP-hard scheduling problem, namely, the common due date single-machine early/tardy scheduling problem (SMETP). Two alternative parameter self-adaptive schemes are proposed which eliminate the need for manual tuning of control parameters and evaluated within the context of a biased DE algorithm. The new algorithm is a variant of the DE algorithm, introducing a bias in selecting parental vectors for mating to ensure that one of them possesses a superior solution quality compared to the other parent. Computational results over existing benchmark datasets show that these schemes outperformed other known in the literature saDE schemes.