The single machine total weighted tardiness problem (SMTWTP) is a well-known planning problem from operations research, engineering and computer science.

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 TWT, i. e. min TWT = ∑ wj Tj.

Proposition of new large benchmark instances

Looking at the scientific literature, it becomes clear, that the well-known benchmark instances (see the OR Library) do not pose a challenge to state-of-the-art algorithms any longer. Therefore, and on the basis of our previous research, novel and considerable larger instances have been proposed (n=1000).

Proposition of new ‚prime‘ bechmark instances

In addition to the large instances above, we generated new instances with processing times and weights based on prime numbers. Identical to the instances from the OR Library, each instance comprises 100 jobs, but excludes the symmetries found in the old data sets.

Related key publications

K43D6k80o9dBochPMartin Josef Geiger (2010):
On Heuristic Search for the Single Machine Total Weighted Tardiness Problem – Some Theoretical Insights and their Empirical Verification.
European Journal of Operational Research, Volume 207, Issue 3, December 2010, Pages 1235–1243, ISSN 0377-2217.

3CrGtat92awuc3xxMartin Josef Geiger (2010):
New Instances for the Single Machine Total Weighted Tardiness.
Research Report RR-10-03-01, Helmut-Schmidt-University, University of the Federal Armed Forces Hamburg, Logistics Management Department, Hamburg, Germany, March 2010, ISSN 2192-0826.


Letzte Änderung: 25. November 2017