Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний

М.: МФТИ, 2008. — 222 с. — ISBN 978-5-7417-0257-4. 600 dpi, OCR.Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения (Lmax) и быстродействия (Сmax). Предлагается качественно новая схема нахождения приближенного решения. Вводится понятие метрики (расстояния) между примерами R. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удается найти оптимальное или приближенное решение с минимальным расстоянием до исходного примера во введенной метрике. Результаты работы могут быть полезны специалистам по дискретному программированию, а также студентам математических факультетов.