Solving the Single Machine Total Earliness and Tardiness Problem with a Common Due Date by Differential Evolution

摘要

A differential evolution (DE) is presented for Minimizing earliness and tardiness penalties in a single machine problem with a common due date. Some control parameters of DE such as population, termination, and crossover factor, are selected according to the dynamic process of evolution, so the DE is very effective and efficient on finding optimum or near-optimal solutions. In order to improve solution quality, we combine DE with simulated annealing, local search and iterated local search respectively, and three hybrid heuristics, DE1, DE2 and DE3, are derived. Computational results based on the well known benchmark suites in the literature show that all the hybrid heuristics produce slightly better results than the GA of Hino et al.