how can they be described in terms of their technical properties? Can we draw conclusions on how to organize future research?

The article is organized as follows. Section 2 presents a quantitative model for the SMTWTP and describes an appropriate representation (coding) for the alternatives. Besides, benchmark instances from the literature are briefly introduced. The following Sections 3 and 4 revisit local search for the SMTWTP, namely hillclimbing and Variable Neighborhood **Search [12]. The identification of** comparable 'difficult' instances is derived from the experiments, and a closer analysis of these data sets follows in Section 5. Conclusions are presented in Section 6.

## 2 Problem Statement And Benchmark Data 2.1 Quantitative Model

 2009

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

In the SMTWTP, a set of jobs J = {J1, . . . , Jn} **needs to be processed on a single machine. Each job**
Jj consists of a single operation only, involving a processing time pj > 0 ∀j = 1, . . . , n**. The relative**
importance of the jobs is expressed via a nonnegative weight wj > 0 ∀j = 1, . . . , n**. Processing on**
the machine is only possible for a single job at a time, excluding parallel processing of jobs. Each job Jj is supposed to be finished before its due date Dj . If this is not the case, a tardiness Tj **occurs,** measured as Tj = max {sj + pj − Dj ; 0}, where sj denotes the starting time of job j**. The overall**
objective of the problem is to find a feasible schedule x **minimizing the total weighted tardiness**
TW T, i. e. min **TW T** =Pn j=1 wjTj .

A schedule for a particular problem can be interpreted as a vector of starting times of the jobs, x = (s1, . . . , sn). We assume that processing starts at time 0, thus sj ≥ 0 ∀j = 1, . . . , n**. A possible**
overlapping of jobs on the machine is avoided by the formulation of disjunctive side constraints:
sj ≥ sk + pk ∨˙ sj + pj ≤ sk ∀j, k = 1**, . . . , n, j** 6= k.

MIC
As the objective function of the single machine total weighted tardiness problem is a **regular**
function [4], it is known that at least one active schedule exists which is also optimal. A schedule is called active **if, for a given sequence of jobs, all operations are started as early as possible, thus** avoiding all unnecessary in-between waiting times (delays). The problem of finding an optimal schedule may therefore be reduced to the problem of finding an **optimal sequence of jobs. A given**
sequence is represented by a permutation π = {π1, . . . , πn} **of the job indices. Each element** πiin π stores the index of the job which is to be processed as the i**th job in the processing sequence. The**
permutation of indices is then 'decoded' into a schedule by assigning sπ1 **= 0 and computing the**
values of sπi = sπi−1 + pπi−1 ∀i = 2**, . . . , n**.

Obviously, this leads to an active schedule without any waiting times between jobs.

## 2.2 Benchmark Instances From The Literature

Optimization approaches for the SMTWTP are commonly verified using the benchmark instances of [9]. The authors presented 375 data sets with varying characteristics. For values of n **= 40,**
n = 50, and n **= 100, 125 instances are each proposed. The computation of the processing times**
pj is randomly drawn from a uniform distribution [1, 100], while the weights are taken from [1, **10].**
Depending on the relative range of due dates RDD and the average tardiness factor T F**, the due**

## Hamburg, Germany, July 13–16, 2009
