Abstract

Scheduling to meet set due dates is one of the most critical issues in modern production systems. One measure of schedule effectiveness in the presence of due dates is weighted tardiness since it can capture the cost of contractual penalties and other losses to an organization. This research work concentrates on the problem of minimizing the total weighted tardiness in classical job shops. Job shop scheduling problems are among the hardest known combinatorial optimization problems. In particular the problem of minimizing tardiness in job shops is strongly NP-hard, which makes finding optimal solutions to it impractical in most realistic situations. We approach this problem using two well known heuristics, namely the shifting bottleneck procedure and tabu search. Both heuristics are known to perform very well for minimizing makespan in job shops. Here we adapt them for the objective of minimizing weighted tardiness and test both under different parameter settings in order to select implementations that give the best results for a given computational effort. We test our algorithms with problem instances taken from the literature and with randomly generated instances. We present our observations and conclusions regarding the relative performance of these heuristics and their performance in comparison with dispatching rules. In particular, we find that the shifting bottleneck procedure outperforms tabu search for this problem.