|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Complexity and approximability of scheduling resumable proportionally deteriorating jobsстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Gawiejnowicz S., Kononov A.
- Журнал: European Journal of Operational Research
- Том: 200
- Номер: 1
- Год издания: 2010
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 305
- Последняя страница: 308
- DOI: 10.1016/j.ejor.2008.12.014
- Аннотация: A set of independent, resumable and proportionally deteriorating jobs is to be executed on a single machine. The machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. The criterion of schedule optimality is the maximum completion time. It is proved that the decision version of theproblem with a single non-availability period is ordinarily NP-complete. It is also proved that for the problem with a single non-availability period there exists a fully polynomial-time approximation scheme. Finally, it is proved that for the problem with two or more non-availability periods there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio, unless P = NP.
- Добавил в систему: Кононов Александр Вениаминович