|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
O(log m)-approximation for the routing open shop problemстатья
- Автор: Kononov A.
- Журнал: RAIRO Recherche Operationnelle
- Том: 49
- Номер: 2
- Год издания: 2015
- Издательство: EDP Sciences
- Местоположение издательства: France
- Первая страница: 383
- Последняя страница: 391
- Аннотация: We consider the routing open shop problem which is a generalization of the open shop and the metric travelling salesman problems. The jobs are located in 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 jobs. The goal is to find a non-preemptive schedule with the minimum makespan. We present a new polynomial-time approximation algorithm with worst-case performance guarantee O(log m), where m is the number of machines.
- Добавил в систему: Кононов Александр Вениаминович