Series: 2008-12, Preprints
Abstract:
The scheduling problem of minimizing total tardiness on a single machine is known
to be NP-hard in the ordinary sense. In this paper, we consider the special case of
the problem when the processing times and the due dates of the jobs are oppositely ordered. This special case is NP-hard in the ordinary sense, too. The set of jobs is partitioned into k subsets. In dependence on the value of k,
we propose pseudopolynomial and polynomial algorithms
to find an optimal solution for particular subcases.
Finally, we apply the idea of the presented algorithm for the case k = 1 to the even-odd partition problem.
Keywords:
Scheduling, Single Machine, Total Tardiness, Even-Odd Partition, NP-Hardness
This paper was published in:
Mathematical and Computer Modelling, Vol. 49, No. 9-10, 2009, 2078 - 2089 (under the title: Algorithms for Special Cases of the Single Machine Total Tardiness Problem and an Application to the Even-Odd Partition Problem).