Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm

摘要

In this paper a novel evolutionary-based approach is utilised for efficiently solving the NP-hard problem of scheduling numerous common-due-date jobs on a single machine. Minimising the sum of earliness and tardiness penalties for all jobs is considered as the target function. The performance of the proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs where the numerical results indicate that it can produce 'better' solutions in less computational time when compared to benchmark results and the methods available in the literature, namely genetic algorithm (GA), Tabu search (TS) and differential evolution (DE).