|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
NP-hard Cases in Scheduling Deteriorating Jobs on Dedicated Machinesстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Gawiejnowicz S., Kononov A.
- Журнал: Journal of the Operational Research Society
- Том: 52
- Год издания: 2001
- Издательство: Palgrave Macmillan Ltd.
- Местоположение издательства: United Kingdom
- Первая страница: 708
- Последняя страница: 717
- DOI: 10.1057/palgrave.jors.2601117
- Аннотация: In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless P=NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have got equal deterioration rates on the third machine.
- Добавил в систему: Кононов Александр Вениаминович