|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Algorithms for special cases of the single machine total tardiness problem and an application to the even–odd partition problemстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 14 сентября 2013 г.
- Авторы: Лазарев А.А., Werner F.
- Журнал: Mathematical and Computer Modelling
- Том: 49
- Номер: 9-10
- Год издания: 2009
- Издательство: Pergamon Press Ltd.
- Местоположение издательства: United Kingdom
- Первая страница: 2061
- Последняя страница: 2072
- DOI: 10.1016/j.mcm.2009.01.003
- Аннотация: 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 |; 1 | n, subsets M1;M2; : : : ;M|, M T M D ; for 6D ; N D M1 S M2 S S M|, such that maxi;j2M jdi ���� djj minj2M pj for each D 1; 2; : : : ; |. We propose algorithms which solve the problem: in O.|n P pj/ time if 1 | < n; in O.n2/ time if | 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 | D 1 to the evenodd partition problem.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | 1-s2.0-S0895717709000089-main.pdf | 1-s2.0-S0895717709000089-main.pdf | 908,4 КБ | 11 сентября 2013 [Lazarev] |