Two hybrid algorithms for single-machine total weighted tardiness scheduling problem with sequence-dependent setup

This paper addresses Single-machine total weighted tardiness scheduling problem with dependent setup time. The problem, even in absence of setup time, is strongly NPhard and cannot be solved using common optimization methods in reasonable time. In this paper, first a mathematical model for solving the problem is presented and then, two metaheuristics; Genetic Algorithm (GA) and Simulated Annealing (SA), as well as a hill climbing heuristic are suggested. Each algorithm is examined individually and then two hybrid models are considered. The computational result shows that SA performs more efficient among the non-hybrid models while the hybrid of SA and Hill climbing is the best solution in general.

Hybrid algorithm; scheduling; single-machine; sequence-dependent setup;