Algorithms for specialcases of the single machine total tardiness problem and an application to the even-odd partition problemстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 18 июля 2013 г.
Аннотация: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 pj and the due dates dj of the jobs j; j 2 N D f1; 2; : : : ; ng,
are oppositely ordered: p1 p2 pn and d1 d2 dn. It is
shown that already this special case is NP-hard in the ordinary sense, too. The set of
jobs N is partitioned into k; 1 k n, subsets M1;M2; : : : ;Mk, M
T
M D ; for
6D ; N D M1
S
M2
S
S
Mk, such that maxi;j2M
jdi ���� djj minj2M pj for each
D 1; 2; : : : ; k. We propose algorithms which solve the problem: in O.kn
P
pj/ time if
1 k < n; in O.n2/ time if k D n; and in O.n2/ time if maxi;j2N jdi ���� djj 1. The
polynomial algorithms do neither require the conditions p1 p2 pn mentioned
above nor integer processing times to construct an optimal schedule. Finally, we apply the
idea of the presented algorithm for the case k D 1 to the evenodd partition problem.