Читать онлайн «Теория расписаний. Задачи и алгоритмы»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА Лазарев Александр Алексеевич Гафаров Евгений Рашидович ТЕОРИЯ РАСПИСАНИЙ ЗАДАЧИ И АЛГОРИТМЫ МОСКВА – 2011  2 УДК 519. 854. 2 ББК Л Рецензенты: д. т. н. , профессор В. Н. Бурков; д. ф. -м. н. , профессор В. В. Шкурба Под редакцией академика РАН С. Н. Васильева В данном учебном пособии приводятся базовые сведения о специальном разделе дискретной математики - Теории расписаний. Описаны этапы становления теории, свойства и классификации задач теории расписа- ний, методы их решения. На примерах классических задач представлены приемы доказательства их трудоемкости и алгоритмы решения. Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для студентов и преподавателей вузов математи- ческих специальностей, специалистов в области управления и практиков, сталкивающихся с задачами объемно-календарного планирования. Оглавление Предисловие редактора 7 Введение 9 1 Общие сведения о теории расписаний 13 1. 1 Предмет теории расписаний . . . . . . . . . . . . . . . . . . 13 1. 1. 1 Возникновение и этапы развития теории расписаний 19 1. 1. 2 Способы представления расписаний . . . . . . . . . 23 1. 2 Классификация задач ТР . . . . . . . . . . . . . . . . . . . 25 1. 2. 1 Дополнительные условия в задачах ТР . . . . . . . 27 1. 2. 2 Целевые функции в задачах ТР . . . . . . . . . . . 28 1. 2. 3 Построение расписания для проекта. Project scheduling (P S) . . . . . . . . . . . . . . . . 30 1. 2. 4 Построение расписания для приборов. Machine scheduling (M S) . . . . . . . . . . . . . . . 33 1. 2. 5 Система обозначений для задач Machine Scheduling 36 1. 2. 6 Составление временны́х таблиц (Time Tabling) . . . 38 Библиографическая справка . . . . . . . . . . . . . . . . . . . . 39 2 Методы решения задач комб. оптимизации 40 2. 1 Классические задачи дискретной оптимизации . . . . . . . 40 3 Оглавление 4 2. 2 Некоторые сведения о сложности (трудоёмкости) задач ком- бинаторной оптимизации . . . . . . . . . . . . . . . . . . . 45 2. 2. 1 Трудоемкость алгоритмов и полиномиально разре- шимые задачи . . . . . . . . . . . . . . . . . . . . . . 45 2. 2. 2 Класс N P и труднорешаемые задачи . . . . . . . . 47 2. 2. 3 Классификация алгоритмов решения . . . . . . . . 49 2. 3 Методы решения задач дискретной оптимизации . . . . . . 52 2. 3. 1 Эвристические алгоритмы . . . . . . . . . . . . . . . 52 2. 3. 2 Метаэвристические методы . . . . . . . . . . . . . . 55 2. 3. 3 Метод динамического программирования . . . . . . 56 2. 3. 4 Графический метод . . . . . . . . . . . . . . . . . . 59 2. 3. 5 Алгоритм динамического программирования для за- дачи о двух конвейерах . . . . . . . . . . . . . . . . 67 2. 3. 6 Метод Ветвей и Границ . . . . . . . . . . . . . . . . 72 2. 4 Задача о назначениях . . . . . . . . . . . . . . . . . . . . . 76 2. 5 Некоторые сведения из теории графов . . . . . . . . . . . . 81 Библиографическая справка . . . . . . . . . . . . . . . . . . . . 83 3 Одноприборные задачи ТР 84  3. 1 Одноприборные задачи 1|rj , pj = 1, pmtn| fj . . . . . . . 87 3. 2 Минимизация числа запаздывающих  требований 1|| Uj . . . . . . . . . . . . . . . . . . . . . . 88 3. 3 Минимизация взвешенного числа  запаздывающих требований 1|| wj Uj . . . . . . . . . . . 91  3. 3. 1 Графический алгоритм для задачи 1|| wj Uj . . . 95  3. 4 Минимизация суммарного запаздывания 1|| Tj . . . . . . 97  3. 4. 1 Точный алгоритм решения задачи 1|| Tj . . . . . 97 Оглавление 5 3. 4. 2 Аппроксимационный алгоритм . . . . . . . . . . . . 102 3. 4. 3 Алгоритм Муравьиные Колонии . . . . . . . . . . . 104 3. 4. 4 Гибридный алгоритм решения . . . . . . . . . . . . 107 3. 4. 5 Эффективность алгоритмов для тестовых примеров Поттса и ван Вассенхова . . . . . . . . . . 109 3. 5 Минимизация обобщенной функции запаздывания . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3. 6 Одноприборные задачи с обратными критериями оптимизации . . . . . . . . . . . . . . . . . . . 114  3. 6. 1 Доказательство NP-трудности задачи 1(nd)|| max wj Tj 120 3. 6. 2 Псевдополиномиальный алгоритм решения  задачи 1(nd)|| max Tj . . . . . . . . . . . . . . . . 126  3. 6. 3 Графический алгоритм решения задачи 1(nd)|| max Tj 128 3. 7 Задачи с одним невозобновимым ресурсом . . . . . . . . . 138 Библиографическая справка . . . . . . . . . . . . . . . . . . . . 141 4 Задачи цеха (Shop problems) 142 4. 1 Задачи F ||Cmax . . . . . . . . . . . . . . . . . . . . . . . . . 142 Библиографическая справка . . . . . . . . . . . . . . . . . . . . 144 5 Построение расписания для проекта 146 5. 1 Практическая задача составления расписания проекта . . . . . . . . . . . . . . . . . . . . . . 147 5. 2 Алгоритм диспетчеризации для задачи RCPSP . . . . . . . 149 5. 3 Задача RCPSP с прерываниями обслуживания требований 152 5. 4 Нижние оценки для задачи RCPSP . . . . . . . . . . . . . 154 5. 4. 1 Нижняя оценка Mingozzi . . . . . . . . . . . . . . . 157 Оглавление 6 5. 5 Соотношение оптимальных значений для задачи RCPSP с прерываниями и без прерываний . . . . . . . . . 159 5. 6 Алгоритмы вычисления верхних оценок для задачи RCPSP . . . . . . . . . . . . . . . . . . . . . . . 163 5. 7 Алгоритм Муравьиные Колонии для задачи RCPSP . . . . . . . . . . . . . . . . . . . . . . . 172 5. 8 Частные случаи задачи RCPSP c одним ресурсом . . . . . . . . . . . . . . . . . . . . . . . . 174 5. 8. 1 Частный случай LSPP . . . . . . . . . . . . . . . . . 175 5. 8. 2 Частный случай UPT . . . . . . . . . . . . . . . . . 177 5. 8. 3 Частный случай PMS . . . . . . . . . . . . . . . . . 179 5. 9 Сложности приближенного решения задачи RCPSP . . . . . . . . . . . . . . . . . . . . . . . . . 182 5. 10 Планарность сетевого графика для задач RCPSP и PMS . . . . . . . . . . . . . . . . . . . 184 Библиографическая справка . . . . . . . . . . . . . . . . . . . . 190 6 Приложения 191  Доказательство NP-трудности задачи 1|| Tj . . . . . . . . . . 191 Таблица терминов и обозначений . . . . . . . . . . . . . . . . . . 209 Кто есть кто в Теории Расписаний . . . . . . . . . . . . . . . . . 210 Литература 213 Предисловие редактора Уважаемый читатель!