58825

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

A metric approach for scheduling problems with minimizing the maximum penalty

ISBN/ISSN: 

0307-904X

DOI: 

10.1016/j.apm.2020.07.048

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

  • Applied Mathematical Modelling

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

89

Город: 

  • Oxford, Great Britain

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

  • Elsevier

Год издания: 

2021

Страницы: 

1163-1176
Аннотация
NP-hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is determined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems.

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

Лемтюжникова Д.В., Лазарев А.А., Werner F.?. A metric approach for scheduling problems with minimizing the maximum penalty // Applied Mathematical Modelling. 2021. 89. С. 1163-1176.