A new crossover operator for single machine total weighted tardiness problem with sequence dependent setup times

Abstract

The single machine total weighted tardiness problem with sequence dependent setup times is a challenging and heavily studied problem. This problem is NP-hard, so several heuristics have been proposed in the literature so far. One of them is the genetic algorithm. The genetic algorithm is both powerful solution technique and applicable to wide range of different problem types, although its performance is heavily parameter and operator dependent. It is seen in literature that the well-conducted and adapted genetic algorithm operators and parameters increase the solution quality. In this study, a new crossover operator is proposed for the single machine with sequence dependent setup times problem to minimize the total weighted tardiness. The proposed crossover operator improves the relative positions by using apparent tardiness cost with setups (ATCS) heuristic while preserving the absolute positions. These are the two main aspects of the permutation type crossover operators for scheduling problems. The performance of the proposed crossover operator is tested by comparing it with partially mapped crossover (PMX) in different test cases using benchmark instances from literature. It is shown that the proposed ATCS based crossover operator gives better results than PMX in all test problems.