Weighted tardiness: 

This directory contains the benchmark instances for Weighted Tardiness
scheduling from the OR-Library, of J. E. Beasley.  See 
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/wtinfo.html 
for the definitive version.

License link: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/legal.html

*** LICENSE FROM OR-LIBRARY SITE ***

All of the material available from OR-Library is freely available 
for use. As such the MIT licence, reproduced below, applies:

Copyright (c) (2010) (J E Beasley} Permission is hereby granted, 
free of charge, to any person obtaining a copy of this software 
and associated documentation files (the "Software"), to deal in 
the Software without restriction, including without limitation 
the rights to use, copy, modify, merge, publish, distribute, 
sublicense, and/or sell copies of the Software, and to permit 
persons to whom the Software is furnished to do so, subject to 
the following conditions: The above copyright notice and this 
permission notice shall be included in all copies or substantial 
portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
OTHER DEALINGS IN THE SOFTWARE. 


*** START OF ORIGINAL DOCUMENTATION FROM OR-LIBRARY ***

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).