# The Single Machine Total Weighted Tardiness Problem— Is It (For Metaheuristics) A Solved Problem ?

Martin Josef Geiger∗
∗**Logistics Management Department,**
Helmut Schmidt University - University of the Federal Armed **Forces Hamburg**
Holstenhofweg 85, 22043 Hamburg, Germany mjgeiger@hsu-hh.de

1 Introduction

![0_image_1.png](0_image_1.png)

 2009

![0_image_0.png](0_image_0.png)

The single machine total weighted tardiness problem (SMTWTP) is a well-known planning problem from operations research, engineering and computer science. It is characterized by the assignment of starting times for a given set of jobs on a single processor, minimizing the (weighted) tardy completion of the jobs with respect to given due dates. In this sense, the tardiness is given an economical interpretation, referring to the consideration of costs which consequently have to be avoided as much as possible.

Although most practical problems involve multiple resources (e. g. machines), many problems can be decomposed into a subsequently solved series of single-machine problems, as for example done in the famous shifting bottleneck heuristic [2]. The effective solution of each single-machine subproblem is therefore a relevant aspect for solving more complex models.

MIC
Besides the problem's relevance with respect to the applicability in real-world situations, the SMTWTP is computationally challenging, as it has been proven to be strongly N P**-hard [13].**
While some exact methods are available, many successful solution approaches are based on heuristics [1]. More recently, several different metaheuristics have been developed for the SMTWTP,
successfully solving benchmark instances from the scientific literature. Important work includes simple local search [15], Evolutionary Algorithms [9], Ant **Colony Optimization [5, 10, 17], Iterated**
Local Search [11], and Simulated Annealing [18]. A particularly successful neighborhood search technique for the SMTWTP is Iterated Dynasearch **[8], which uses dynamic programming to determine an optimal series of moves to be executed simultaneously.**
While it has been pointed out that available benchmark instances are comparably easily solvable by local search [11], several recent publications aim to push the scientific knowledge even further by proposing more refined metaheuristics [3, 6, 7, 14, 19, 20]. Common to these approaches is the fact that they lead to rather impressive results within the chosen experimental settings. From this perspective, and taking into account the remarks of [11], we **need to raise the question whether** recent results are so surprising after all. Or is it possible **that, despite the problem's complexity,** the SMTWTP is a 'solved' problem for metaheuristics? Are there 'difficult' instances, and if so, Hamburg, Germany, June 13–16, 2009