25437

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

Algorithms for some maximization scheduling problems on a single machine

Электронная публикация: 

Да

ISBN/ISSN: 

ISSN 0005-1179; 1608-3032/e

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

  • Automation and Remote Control

Обозначение и номер тома: 

71, No.10

Город: 

  • Москва

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

  • SP MAIK Nauka/Interperiodica

Год издания: 

2010

Страницы: 

2070-2084. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a
Аннотация
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.

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

Гафаров Е.Р., Лазарев А.А., Werner F. Algorithms for some maximization scheduling problems on a single machine // Automation and Remote Control. 2010. 71, No.10. С. 2070-2084. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a.