25446

Автор(ов):

2

Параметры публикации

Тип публикации:

Статья в журнале/сборнике

Название:

Algorithms for special cases of the single machine total tardiness problem and an application to the even–odd partition problem

Да

ISSN 0895-7177

Наименование источника:

• Mathematical and Computer Modelling

49, No.9-10

• Oxford

Издательство:

• Elsevier Science

2009

Страницы:

2061-2072. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a
Аннотация
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 , 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ν⋂Mμ=0̸ for ν≠μ,N=M1⋃M2⋃⋯⋃Mk, such that maxi,j∈Mν|di−dj|≤minj∈Mνpj for each ν=1,2,…,k. We propose algorithms which solve the problem: in O(kn∑pj) time if 1≤k

Библиографическая ссылка:

Лазарев А.А., Werner F. Algorithms for special cases of the single machine total tardiness problem and an application to the even–odd partition problem / Mathematical and Computer Modelling. Oxford: Elsevier Science, 2009. 49, No.9-10. С. 2061-2072. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a.