|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Algorithms for some maximization scheduling problems on a single machineстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 14 сентября 2013 г.
- Авторы: Гафаров Е.Р., Лазарев А.А., Werner F.
- Журнал: Automation and Remote Control
- Том: 71
- Номер: 10
- Год издания: 2010
- Издательство: Pleiades Publishing, Ltd
- Местоположение издательства: Road Town, United Kingdom
- Первая страница: 2070
- Последняя страница: 2084
- DOI: 10.1134/S0005117910100061
- Аннотация: In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT j and for the problem of maximizing the number of tardy jobs 1‖maxΣU j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT j is polynomially solvable. For several special cases of problem 1‖maxΣT j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | 10.1134_S0005117910100061.pdf | 10.1134_S0005117910100061.pdf | 291,0 КБ | 11 сентября 2013 [Lazarev] |