|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Efficient approximation algorithms for the routing open shop problemстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Chernykh I., Kononov A., Sevastyanov S.
- Журнал: Computers and Operations Research
- Том: 40
- Номер: 3
- Год издания: 2013
- Издательство: Pergamon Press Ltd.
- Местоположение издательства: United Kingdom
- Первая страница: 841
- Последняя страница: 847
- DOI: 10.1016/j.cor.2012.01.006
- Аннотация: We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.
- Добавил в систему: Кононов Александр Вениаминович