|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Метрика для приближенного решения задач теории расписанийтезисы доклада
- Авторы: Лазарев А.А., Коренев П.С.
- Сборник: Труды и пленарные доклады участников конференции УКИ'12
- Тезисы
- Год издания: 2012
- Место издания: ИПУ РАН Москва
- Первая страница: 267
- Последняя страница: 274
- Аннотация: Задачи формирования составов и расписания движения грузовых поездов могут быть сформулированы как задач и теории расписаний. Многие из этих задач являются NP-трудными, в связи с чем возникает проблема поиска приближенного решения таких задач. Предлагается метод, основанный на введении метрики для пространства параметров задачи, позволяющий за полиномиальное время находить решение задачи с гарантированной абсолютной погрешностью целевой функции. Метод подробно рассматривается на примере задачи минимизации суммарного запаздывания. Эффективность метода подтверждается численными экспериментами.
- Добавил в систему: Лазарев Александр Алексеевич