Minimizing Arbitrary Earliness/Tardiness Penalties with Common Due Date in Single-Machine Scheduling Problem Using a Tabu-Geno-Simulated Annealing

In this paper, the single machine scheduling problem for a common due date with arbitrary earliness/tardiness penalties is discussed. The objective is to determine the common due date and processing sequence of new jobs together with the re-sequencing of old jobs to minimize the sum of total earliness/tardiness (E/T), completion time, and due date (dd) related penalties. We propose a new approach Tabu-Geno-Simulated Annealing (TGSA) by hybridization of three well-known metaheuristics, which have proven to be effective for this non deterministic polynomial time (NP) hard scheduling problem, namely, genetic algorithms (GA), tabu search, and simulated annealing (SA). Computational results have shown the effectiveness of the proposed approach in comparison with the ad-hoc heuristics on various single-machine scheduling problems. The assessment of the proposed hybridization indicates the efficiency in both the result and the time versus the other methods.