shkolaput.ru 1 2 ... 129 130

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Сибирское отделение
Институт математики
На правах рукописи
СЕВАСТЬЯНОВ СЕРГЕЙ ВАСИЛЬЕВИЧ
УДК 519.854
ГЕОМЕТРИЧЕСКИЕ МЕТОДЫ
И ЭФФЕКТИВНЫЕ АЛГОРИТМЫ
В ТЕОРИИ РАСПИСАНИЙ
01.01.09 — математическая кибернетика
Диссертация на соискание ученой степени
доктора физико-математических наук
Новосибирск — 2000


Оглавление
Неформальное введение

4
1
“Откуда есть пошла . . .” Исторический экскурс . . . . . . . . . . . . . . .
4
2
О названии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3
Область исследования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4
Объект и цели исследования . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5
Методы исследования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Вполне формальное введение

26

6
Общая характеристика работы . . . . . . . . . . . . . . . . . . . . . . . . . 26
7
Обзор результатов диссертации . . . . . . . . . . . . . . . . . . . . . . . . 32
8
Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . . 41
I Задачи суммирования векторов

44

9
Определения и обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . 45
10
Алгоритмы нахождения подсемейств векторов, ребер и операций . . . . . 46
11
Компактное суммирование векторов . . . . . . . . . . . . . . . . . . . . . . 69
12
Оценки и свойства функций Штейница . . . . . . . . . . . . . . . . . . . . 80
13
Нестрогое суммирование векторов на плоскости . . . . . . . . . . . . . . . 88
14
Экстремальные задачи о нестрогом суммировании векторов в семействах
полупространств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
15

Суммирование векторов в специальных областях пространства . . . . . . 121

16
Заключение (открытые вопросы и гипотезы) . . . . . . . . . . . . . . . . . 127
II Экстремальные комбинаторные задачи
129
17
Ранги целых чисел и их свойства . . . . . . . . . . . . . . . . . . . . . . . 130
18
Задачи о равномерных разбиениях . . . . . . . . . . . . . . . . . . . . . . . 135
19
Задачи о максимальном потоке, равномерном по стокам, и о распределе-
нии камней с запретами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
20
Связи между комбинаторными задачами . . . . . . . . . . . . . . . . . . . 145
21
Заключение (открытые вопросы и гипотезы) . . . . . . . . . . . . . . . . . 154
2


3
III Многостадийные системы теории расписаний
156
22
Общие определения и предварительные замечания . . . . . . . . . . . . . 157
1 Системы с нефиксированными маршрутами
165
23
Понятие нормальности в системах open shop . . . . . . . . . . . . . . . . . 167
24
Минимальные нормализующие векторы в R3 . . . . . . . . . . . . . . . . . 169
25
Нахождение эффективно нормальных классов с использованием нестро-
гого суммирования векторов . . . . . . . . . . . . . . . . . . . . . . . . . . 181
26
Построение эффективно нормального класса методом Фиалы . . . . . . . 185
27
Оценки функций ηn(m) и ηe(m) . . . . . . . . . . . . . . . . . . . . . . . . 189
28
Жадные алгоритмы построения допустимых расписаний с постоянными
приоритетными порядками операций . . . . . . . . . . . . . . . . . . . . . 193
29
Свойства жадных расписаний . . . . . . . . . . . . . . . . . . . . . . . . . 196
30
Жадные алгоритмы точного и приближенного решения задачи open shop 199
31
Схема AGC жадной достройки расписания многопроцессорной системы
открытого типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

32

Метод последовательной достройки нормального расписания . . . . . . . 209
33
k-нормализующие и k-достраивающие векторы в Rm . . . . . . . . . . . . 211
34
Эффективно нормализующие векторы в Rm . . . . . . . . . . . . . . . . . . 217
35
Полиномиальная аппроксимационная схема для многопроцессорной зада-
чи open shop с фиксированным числом машин . . . . . . . . . . . . . . . . 219
36
Барьер точности для задачи open shop с нефиксированным числом машин 227
37
Точный и приближенный алгоритмы для многопроцессорных систем от-
крытого типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
38
Заключительные замечания и открытые вопросы . . . . . . . . . . . . . . 232
2 Системы поточного типа

234

39
Приближенное решение задачи flow shop с использованием нестрогого
суммирования векторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
40
Интервалы локализации оптимумов задачи flow shop . . . . . . . . . . . . 238
41
Многопроцессорная задача flow shop . . . . . . . . . . . . . . . . . . . . . 241
3 Задача о сборочной линии
249
4 Системы с различными маршрутами
251
42
Задача Акерса-Фридман для трех машин . . . . . . . . . . . . . . . . . . . 251
43
Двухмаршрутные задачи трех машин . . . . . . . . . . . . . . . . . . . . . 255
44
Задача Job Shop и общая задача G . . . . . . . . . . . . . . . . . . . . . . 266
45
Открытые вопросы и проблемы . . . . . . . . . . . . . . . . . . . . . . . . . 270
Литература
271



следующая страница >>