Читать онлайн «Теория расписаний. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний : учебное пособие для студентов вузов по направлению "Прикладные математика и физика"»

А. А. ЛАЗАРЕВ ТЕОРИЯ РАСПИСАНИЙ ОЦЕНКИ АБСОЛЮТНОЙ ПОГРЕШНОСТИ И СХЕМА ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ 11 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное агентство по образованию Московский физико-технический институт (государственный университет) Институт проблем управления им. В. А. Трапезникова РАН А. А. Лазарев ТЕОРИЯ РАСПИСАНИИ. ОЦЕНКИ АБСОЛЮТНОЙ ПОГРЕШНОСТИ И СХЕМА ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ Рекомендовано Учебно-методическим объединением высших учебных заведений Российской Федерации по образованию в области прикладных математики и физики в качестве учебного пособия для студентов вузов по направлению «Прикладные математика и физика» МОСКВА 2008 УДК 519. 854. 2 ББК 22. 18 Л17 Рецензенты: Кафедра прикладной математики-1 Московского государственного университета путей сообщения (МИИТ) (зав. кафедрой доктор физико-математических наук, профессор А. С. Братусь) Доктор технических наук, профессор В. Н. Бурков Доктор технических наук, профессор И. Х. Сигал Лазарев А. А. Л17 Теория расписаний. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний: Учебное пособие. - М. : МФТИ, 2008. - 222с ISBN 978-5-7417-0257-4 Рассматриваются классические ТУР-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения (Lmax) и быстродействия (С^). Предлагается качественно новая схема нахождения приближенного решения. Вводится понятие метрики (расстояния) между примерами р. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удается найти оптимальное или приближенное решение с минимальным расстоянием до исходного примера во введенной метрике. Результаты работы могут быть полезны специалистам по дискретному программированию, а также студентам математических факультетов. УДК 519. 854. 2 ББК 22. 18 ISBN 978-5-7417-0257-4 © Лазарев А. А. , 2008 © ГОУ ВПО «Московский физико-технический институт (государственный университет)», 2008 Оглавление Введение 6 1 Оценка абсолютной погрешности задач минимизации максимального временного смещения 24 1. 1 Постановка задачи 1 | гj \ Lmax 24 1. 2 Обозначения и определения основных понятий . 27 1. 3 Абсолютная погрешность приближённого решения 29 1. 4 Схема нахождения приближённого решения задачи 1 | r3; | Lmax 34 1. 4. 1 Вариант схемы на основе случая 1 | di < dj,di — Ti — pi > dj — rj — pj I Lmax 37 1. 4. 2 Вариант схемы на основе случая Логевена 45 1. 5 Экспериментальное исследование алгоритмов решения задачи 1 | гj \ Z/max 49 1. 5. 1 Способ генерации примеров 50 1. 5. 2 Оценка экспериментального значения абсолютной погрешности 53 1. 5. 3 Эффективность применения полиномиальных алгоритмов для общего случая задачи 55 1. 6 Свойства оптимальных расписаний общего случая задачи l|7%|Lmax • • • • 60 1. 7 Свойства оптимальных расписаний частных случаев задачи l|rj|Lmax 80 1. 8 Оценки абсолютной погрешности 85 1. 8. 1 Задачи для нескольких приборов 85 1. 8. 2 Оценка абсолютной погрешности 90 1. 8. 3 Схема приближённого решения задачи Р | prec, rj | Lmax 97 3 1. 9 Нормированное пространство примеров задачи Р\ргее,п\Ьтах 99 1. 10 Схемы нахождения приближённого решения . . 103 1. 10. 1 Схема сведения задач OL /3 | Lmax -> ОС | (3 | Стах И a /?, rj I Lmax -> a I /?, rj = 0 I Lmax ... . 103 1. 10. 2 Схема сведения задач a I I Lmax -> « I /?,р, = p I Lmax И a j /?,р,- j Lmax -> « j = 1 j Lmax • • • • Ю4 1. 10. 3 Схема сведения задач {Ry Q}\/3\ Lmax -> P I /?