Вероятностный анализ алгоритмов построения кратчайших расписаний для многостадийных систем

• Автор: Корякин, Роман Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Новосибирск
• Количество страниц: 98 с.

Общая характеристика работы
Главные результаты диссертации
Публикации и апробация результатов исследований
Структура работы
1 Компактное суммирование векторов
1.1 Предварительные сведения
1.2 Формулировки результатов
1.3 Алгоритмы Ai.2, Ai.z
§ 1.3.1 Необходимые обозначения
§ 1.3.2 Описание алгоритма А
§ 1.3.3 Описание алгоритма «4і.з
1.4 Доказательство теоремы 1
§ 1.4.1 Процедура выравнивания
§ 1.4.2 Суммирование больших векторов
§ 1.4.3 Оценка радиуса суммирования
§ 1.4.4 Асимптотическая оптимальность
§ 1.4.5 Вспомогательные доказательства

1.5 Приложения для стохастических задач теории расписаний
§ 1.5.1 Задача Open Shop
§ 1.5.2 Задача Flow Shop
§ 1.5.3 Задача о сборочной линии
§ 1.5.4 Задача Job Shop
1.6 Заключительные замечания к главе
2 Достаточные условия полиномиальной разрешимости задачи Open Shop
2.1 Предварительные сведения
2.2 Описание алгоритма Л2
2.3 Формулировки результатов
2.4 Доказательства
2.5 Заключительные замечания к главе
3 Произвольные перестановочные расписания в задачах о сборочной линии и Flow Shop
3.1 Предварительные сведения
3.2 Формулировки результатов
3.3 Доказательства
3.4 Заключительные замечания к главе
Приложение
Литература

Общая характеристика работы и обзор результатов диссертации
В диссертации рассматриваются задачи, относящиеся к классическим многостадийным моделям теории расписаний. Задачи теории расписаний появляются там, где необходимо упорядочить некоторый процесс в рамках заданных ограничений (т.е. составить допустимое расписание для выполнения этого процесса), с тем чтобы полученное расписание было оптимальным по тем или иным критериям. В настоящее время исследуется множество разнообразных моделей теории расписаний (см., например, обзор [28]), хотя подавляющее большинство этих моделей описывают весьма далекие от реальных условий “идеальные” ситуации. Тем не менее, в течение последних 20 и более лет теория расписаний бурно развивается, и в её рамках создаётся множество практических приложений для оптимизации реальных процессов.
Многостадийные системы теории расписаний в некотором упрощенном обобщении характеризуются наличием множества работ, которые необходимо выполнить на данном множестве машин1. Каждая работа
1Также вместо слов “работа-машина” используются термины “деталь-станок” или “требование-прибор”. В данной диссертации автор ограничивается использованием более привычных ему тер-

Глава 1. Компактное суммирование векторов

Тогда
^(т-1)! / (т-1)! (т—1)!
П АЛ = 1-р и аА ї1- Е р(^)
і=1 / у і=1 / і
Сумма в правой части последнего соотношения состоит из конечного числа слагаемых (не зависящего от п) поэтому для доказательства леммы достаточно показать, что при п —► оо каждое слагаемое этой суммы стремится к нулю. Воспользуемся следующим неравенством Чебышева: Р(|Х — ЕХ| > х) < Е>Х/х2 [3, стр. 81]. В данном случае

X = 'У^ХРііі ~Рі2і)і ЕХ = 0, ОХ = 2пВрц, х = п.

В результате получаем:
2пВрі
Р (Л)
^ ](Ріі1 Ръз) 1
^ /-1 «1 -‘'Ш'РИ „
Лемма 1.7 доказана.
Доказательство леммы 1.8. Покажем, что с высокой вероятностью выполняются неравенства
1/п Ь1-“1 п < Ь П Еп| < /п 1п1+“2 п. (1-47)
Вероятность р того, что вектор ej попадает в множество Ь, равна пГ1'21п п (см. (1.15)). Введём случайные величины
. 1,еслие,-€ Л,
&=< (1-48)
0, если ej Е Еш Ь
и заметим, что
= р, Бп = ^2 Сі = ь П ЕпI, Е5„ - пр.