|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penaltyстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 9 декабря 2020 г.
- Авторы: Lazarev Alexander A., Pravdivets Nikolay, Werner Frank
- Журнал: Mathematics
- Том: 8
- Номер: 7
- Год издания: 2020
- Издательство: MDPI
- Местоположение издательства: Basel, Switzerland
- Первая страница: 1131
- DOI: 10.3390/math8071131
- Аннотация: In this paper, we consider the single-machine scheduling problem 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 use the optimal function value of a sub-problem of the dual problem in 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.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | mathematics-08-01131.pdf | mathematics-08-01131.pdf | 340,1 КБ | 4 декабря 2020 [Lazarev] | |
| 2. | Mathematics___July_2020_-_Browse_Articles.pdf | Mathematics___July_2020_-_Browse_Articles.pdf | 164,6 КБ | 4 декабря 2020 [Lazarev] |