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

С. 267–274.

Лазарев А. А., Коренев П. С.

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

Ключевые слова: оптимизация, optimization, модели, models, scheduling theory, теория расписаний, приближенные алгоритмы, approximation algorithms

В книге

Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12

М.: ИПУ РАН, 2012.