SMTWTP

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 = {J₁,…, J_n} needs to be processed on a single machine. Each job J_j consists of a single operation only, involving a processing time p_j > 0 ∀ j = 1, …, n. The relative importance of the jobs is expressed via a nonnegative weight w_j > 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 J_j is supposed to be finished before its due date D_j. If this is not the case, a tardiness T_j occurs, measured as T_j = max {s_j+ p_j – D_j; 0}, where s_j 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 = ∑ w_j T_j.

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

• A technical description of their computation is available here: [urn:nbn:de:gbv:705-opus-28088].
• The instances as such may be downloaded from here (archive containing all 25 large data sets).
• Optimal results.

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.

• The instances may be downloaded from here (archive containing all 25 ‚prime‘ data sets).
• Optimal results.

Related key publications

Martin 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.
[doi:10.1016/j.ejor.2010.06.031]

Martin 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