OR-Library is a collection of test data sets for a variety of OR problems.
A full list of the test data sets available in OR-Library can be found here.
There are 3 data files.
The single-machine total weighted tardiness problem can be stated as
follows. Each of n jobs (numbered 1,...,n) is to be processed without
interruption on a single machine that can handle no more than one job at a time.
Job j (j= 1,...,n) becomes available for processing at time zero,
requires an uninterrupted positive processing time p(j) on the machine,
has a positive weight w(j), and
has a due date d(j) by which it should ideally be finished.
For a given processing order of the jobs, the
earliest completion time C(j)
and the tardiness T(j)=max{C(j)-d(j),0} of
job j (j=1,...,n) can readily be computed. The problem
is to find a processing order of the jobs with minimum
total weighted tardiness SUM{j=1,...,n}w(j)T(j)
125 test instances are available for each problem size n=40, n=50 and n=100.
The instances were randomly generated as follows:
For each job j (j=1,...,n), an integer processing time p{j} was
generated from the uniform distribution [1,100] and integer processing
weight w{j} was generated from the uniform distribution [1,10].
Instance classes of varying hardness were generated by using
different uniform distributions for generating the due dates. For a given
relative range of due dates} RDD (RDD=0.2, 0.4, 0.6,0.8,1.0) and
a given average tardiness factor} TF
(TF=0.2, 0.4, 0.6,0.8,1.0), an integer due date d(j) for each job j
was randomly generated from the uniform distribution
[P(1-TF-RDD/2), P(1-TF+RDD/2)], where P = SUM{j=1,...,n}p(j).
Five instances were generated for each of the 25 pairs
of values of RDD and TF, yielding 125 instances for each value of n.
There are three files wt40, wt50, and wt100 containing the
instances of size 40, 50, and 100 respectively. Each file contains the data
for 125 instances, listed one after the other. The n processing times are
listed first, followed by the n weights, and finally n due dates, for each of the
125 instances in turn.
For example in wt40 the first 40 integers in the file are the processing times for
the 40 jobs in the first instance. The next 40 integers are the first instance's
weights. The next 40 integers are the first instance's due dates. The next 40 integers
are the second instance's processing times, etc.
Optimal and Best known solution values
Optimal values of solutions are available for 124 and 115 of the 40 and 50
job problem instances, respectively.
The unsolved 40 job problem is number 19, and 50 job problems 11, 12,
14, 19, 36, 44, 66, 87, 88 and 111 remain unsolved.
The values for the unsolved problems given in the files wtopt40 and wtopt50 are
the best known to Crauwels, Potts & Van Wassenhove (1996).
The values of the solutions not known to optimality have not been improved
upon since and appear quite likely to be optimal.
The best solution values known to Crauwels, Potts & Van Wassenhove (1998)
for the 100 job problems are given in file wtbest100a.
These solution values were used as the best known by both Crauwels, Potts
& Van Wassenhove (1998) and Congram, Potts & van de Velde (1998).
Therefore using the best solution values known to
Crauwels, Potts & Van Wassenhove (1998) allows results from
future heuristics to be compared directly with the tables given in
these papers.
The local search heuristic dynasearch (Congram, Potts & van de Velde 1998)
has in some cases found better solutions to the 100 job problems than those
known by Crauwels, Potts & Van Wassenhove (1998). The best known solutions
to date are given in the file wtbest100b.
For more information please contact:
Richard K. Congram or Chris N. Potts
Faculty of Mathematical Studies}
University of Southampton}
Southampton SO17 IBJ, U.K
email rkc@maths.soton.ac.uk or cnp@maths.soton.ac.uk
References:
H.A.J. Crauwels, C.N. Potts and L.N. Van Wassenhove (1998).
Local search heuristics for the single machine total weighted
tardiness scheduling problem,
Informs Journal on Computing 10, 341-350.
R.K. Congram, C.N. Potts and S.L. van de Velde (1998).
An iterated dynasearch algorithm for the single-machine total
weighted tardiness scheduling problem. In preparation.
The largest file is wt100 of size 230 Kb (approximately)
The entire set of files is of size 44 0Kb (approximately).
Click here to access these files