ИСТИНА |
Войти в систему Регистрация |
|
ФНКЦ РР |
||
We consider single machine scheduling problems with given release dates. The objective is to minimize the maximum penalty. The problem is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problems and show that both these problems can be solved in polynomial time. The solution of the dual problem provides a lower bound of the optimal objective function value of the initial problem. Because of this, we use the optimal function value of a sub-problem of the dual problem in a branch and bound algorithm for solving the original single machine scheduling problem. Computational experiments have shown a high efficiency of the method in most cases.
№ | Имя | Описание | Имя файла | Размер | Добавлен |
---|---|---|---|---|---|
1. | 1.pdf | 1.pdf | 26,0 КБ | 4 декабря 2020 [Lazarev] | |
2. | BookOfAbstracts_OPTIMA2020.pdf | BookOfAbstracts_OPTIMA2020.pdf | 539,0 КБ | 4 декабря 2020 [Lazarev] |