55127

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty

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

1-ое издание

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

Да

DOI: 

10.13140/RG.2.2.16282.08649

Город: 

  • Magdeburg

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

  • Otto-von-Guericke Universitaet Magdeburg

Год издания: 

2019

Объём, стр.: 

11
Аннотация
In this paper, we consider single machine scheduling problems with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem gives a lower bound on the optimal objective function value of the original problem, we incorpo- rate the optimal function value of a sub-problem of the dual problem into a branch and bound algorithm for the original single machine scheduling problem. We present some initial computational results for instances with up to 20 jobs.

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

Лазарев А.А., Правдивец Н.А., Werner F.?. On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty. Magdeburg: Otto-von-Guericke Universitaet Magdeburg, 2019. – 11 с.