08-12
Algorithms for Special Single Machine Total Tardiness Problems
Preprint series: 08-12, Preprints
The paper is published: 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).
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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.