Теория расписаний. Минимизация максимального временного смещения и суммарного взвешенного числа запаздывающих требований для одного прибора

М. : Вычислительный центр им. А.А. Дородницына РАН, 2007.

Лазарев А. А., Садыков Р. Р.

Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | r_j | L_max) и суммарного взвешенного числа запаздывающих требований (1 | r_j | Σw_jU_j). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. Предложенные методы также могут быть использованы для разработки алгоритмов решения других теоретических задач теории расписаний. Результаты работы могут быть полезны специалистам по дискретному программированию, а также студентам математических факультетов.

Ключевые слова: оптимизация, оптимальные системы, модели, теория графов, теория расписаний, приближенные алгоритмы, комбинаторный анализ, методы исследования операций, исследование операций, нелинейные детерминированные системы, математическая кибернетика