55125

Автор(ы): 

Автор(ов): 

3

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

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

Книга (брошюра, монография, стандарт)

Название: 

A general approximation approach for multi-machine scheduling problems with minimizing the maximum penalty

Сведения об издании: 

Preprint № 04 2019

Сведения об издании: 

1-ое издание

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

Да

DOI: 

10.13140/RG.2.2.13768.67846

Город: 

  • Magdeburg

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

  • Otto-von-Guericke-Universitaet Magdeburg

Год издания: 

2019

Объём, стр.: 

25
Аннотация
We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest instance for which a polynomial or pseudo-polynomial algorithm is known. For this determined instance, we construct a schedule which is then applied to the original instance. It is shown how this approach is applied to di_erent scheduling problems.

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

Лазарев А.А., Лемтюжникова Д.В., Werner F.?. A general approximation approach for multi-machine scheduling problems with minimizing the maximum penalty. Preprint № 04 2019. Magdeburg: Otto-von-Guericke-Universitaet Magdeburg, 2019. – 25 с.