Полиэдральная структура и алгоритмы решения задач обслуживания единичных требований параллельными приборами

• Автор: Уразова, Инна Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Омск
• Количество страниц: 102 с. : ил.

Оглавление
Введение
1. Построение ЦЛП-модели для задачи обслуживания единичных требований параллельными приборами
1.1. Полиэдральная теория
1.2. Полиэдральная релаксация многогранника
расписаний
1.3. Построение целевой функции для задачи обслуживания единичных требований параллельными приборами
1.4. Условия существования расписаний
2. Классы правильных неравенств для многогранника расписаний
2.1. Построение правильных неравенств
2.2. Некоторые условия опорности
2.3. Сравнение построенных неравенств
2.4. Полиэдральные свойства неравенств
2.5. Решение задачи идентификации
3. Алгоритмы анализа и решения задачи обслуживания еди-

ничных требований параллельными приборами и их апробация
3.1. Алгоритмы отсечения
3.2. Применение дихотомии для решения задачи обслуживания единичных требований параллельными приборами
3.3. Выбор коэффициентов целевой функции
Заключение
Литература

Введение
В настоящее время задачи теории расписаний имеют большое прикладное значение. Стремительное развитие техники и связи, появление новых технологий все чаще вызывает необходимость построения расписаний, связанных с функционированием промышленных предприятий и сферы обслуживания, образованием, транспортной развязкой, распределением ресурсов, инвестиционной политикой и многими другими областями.
Свое развитие теория расписаний получила в середине прошлого века. Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Веллман Р., Бруккер П., Джонсон Д., Джонсон С. и другие превратили теорию расписаний в отдельное направлениие в области оптимизации [1, 24, 48, 51, 68, 76, 78, 84, 90, 101]. В настоящее время теория расписаний активно развивается в работах Гимади Э.Х., Гордона B.C., Ковалева М.Я., Кононова A.B., Лазарева A.A., Севастьянова С.В., Серваха В.В. и многих других российских и зарубежных ученых [3, 4, 15, 26, 31, 33, 46, 49, 50, 108].
Помимо прикладного значения, задачи теории расписаний представляют значительный теоретический интерес. Проблематика теории расписаний охватывает исследование вычислительной сложности задач, разработку точных, приближенных и эвристических алгоритмов их решения [22, 34, 70, 75, 109] и др. При этом подавляющее количество работ посвяще-

2.1. Построение правильных неравенств
В настоящем разделе будут описаны классы неравенств, правильных относительно многогранника Мг- Неравенства этих классов, вообще говоря, усиливают ограничения полиэдра в том смысле, что в М,] существуют точки, "отсекаемые" этими неравенствами.
Следующая теорема описывает класс правильных относительно М^ неравенств, который мы обозначим через I.
Теорема 2.1. Пусть Р С £7 - путь, {г'х,г'г,..., гД С У(Р) и к £ Б. Тогда неравенство

^ ] хг3к 5: 1 (2-1)

является правильным к многограннику Мд.
Доказательство. Утверждение достаточно доказать для вершин многогранника Мг- Пусть х £ Мг вершина. Тогда а; расписание. Предположим,

что х^к > 2. Тогда, без ограничения общности, получаем, что

хчк = хг2к — 1- Однако, так как % и принадлежат одному пути, то между ними есть отношение предшествования, и, следовательно, к < к, что не имеет смысла. Теорема доказана.
Приведем пример нецелочисленной точки х £ М^, отсекаемой неравенством из теоремы 2.1, при д = п.
Пример 2.1. Рассмотрим орграф Б с множеством вершин V = {1, 2, 3, 4,..., 10} и множеством дуг Е(С) =
{ 12, 17, 23, 34, 45, 47, 56, 69, 79, 89, 910 } (см. Рис. 2.1). Пусть