17769

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Доклад

Название: 

Метрика для приближенного решения задач теории расписаний

Электронная публикация: 

Да

ISBN/ISSN: 

978-5-91450-100-3

Наименование конференции: 

  • 3-я Всероссийская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения» (УКИ-2012, Москва)

Наименование источника: 

  • Труды 3-й Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (УКИ-2012, Москва)

Город: 

  • Москва

Издательство: 

  • ИПУ РАН

Год издания: 

2012

Страницы: 

267-274
Аннотация
Задачи формирования составов и расписания движения грузовых поездов могут быть сформулированы как задач и теории расписаний. Многие из этих задач являются NP-трудными, в связи с чем возникает проблема поиска приближенного решения таких задач. Предлагается метод, основанный на введении метрики для пространства параметров задачи, позволяющий за полиномиальное время находить решение задачи с гарантированной абсолютной погрешностью целевой функции. Метод подробно рассматривается на примере задачи минимизации суммарного запаздывания. Эффективность метода подтверждается численными экспериментами.

Библиографическая ссылка: 

Лазарев А.А., Коренев П.С. Метрика для приближенного решения задач теории расписаний / Труды 3-й Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (УКИ-2012, Москва). М.: ИПУ РАН, 2012. С. 267-274.