Геометрические методы и эффективные алгоритмы в теории расписаний

• Автор: Севастьянов, Сергей Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 283 с. : ил.

Оглавление
Неформальное введение
1 “Откуда есть пошла ...” Исторический экскурс
2 О названии
3 Область исследования
4 Объект и цели исследования
5 Методы исследования
Вполне формальное введение
6 Общая характеристика работы
7 Обзор результатов диссертации
8 Основные понятия и определения
I Задачи суммирования векторов
9 Определения и обозначения
10 Алгоритмы нахождения подсемейств векторов, ребер и операций
11 Компактное суммирование векторов
12 Оценки и свойства функций Штейница
13 Нестрогое суммирование векторов на плоскости
14 Экстремальные задачи о нестрогом суммировании векторов в семействах
полупространств
15 Суммирование векторов в специальных областях пространства
16 Заключение (открытые вопросы и гипотезы)
II Экстремальные комбинаторные задачи
17 Ранги целых чисел и их свойства
18 Задачи о равномерных разбиениях
19 Задачи о максимальном потоке, равномерном по стокам, и о распределении камней с запретами
20 Связи между комбинаторными задачами
21 Заключение (открытые вопросы и гипотезы)

III Многостадийные системы теории расписаний
22 Общие определения и предварительные замечания
1 Системы с нефиксированными маршрутами
23 Понятие нормальности в системах open shop
24 Минимальные нормализующие векторы в R3
25 Нахождение эффективно нормальных классов с использованием нестрогого суммирования векторов
26 Построение эффективно нормального класса методом Фиалы
27 Оценки функций rjn(m) и 7?e(m)
28 Жадные алгоритмы построения допустимых расписаний с постоянными приоритетными порядками операций
29 Свойства жадных расписаний
30 Жадные алгоритмы точного и приближенного решения задачи open shop
31 Схема Aqc жадной достройки расписания многопроцессорной системы открытого типа
32 Метод последовательной достройки нормального расписания
33 -нормализующие и /с-достраивающие векторы в RTO
34 Эффективно нормализующие векторы в Rm
35 Полиномиальная аппроксимационная схема для многопроцессорной задачи open shop с фиксированным числом машин
36 Барьер точности для задачи open shop с нефиксированным числом машин
37 Точный и приближенный алгоритмы для многопроцессорных систем открытого типа
38 Заключительные замечания и открытые вопросы
2 Системы поточного типа
39 Приближенное решение задачи flow shop с использованием нестрогого суммирования векторов
40 Интервалы локализации оптимумов задачи flow shop
41 Многопроцессорная задача flow shop
3 Задача о сборочной линии
4 Системы с различными маршрутами
42 Задача Акерса-Фридман для трех машин
43 Двухмаршрутные задачи трех машин
44 Задача Job Shop и общая задача G
45 Открытые вопросы и проблемы
Литература

Моим любимым женщинам Посвящаю этот многострадальный труд
Неформальное введение
Глава “Неформальное введение” является факультативной. Она не содержит строгих определений и утверждений и не является обязательной для понимания последующих доказательств теорем. Однако если прочтение этой главы поможет читателю лучше понять суть полученных в диссертации результатов, то ее предназначение можно будет считать выполненным.
1 “Откуда есть пошла ...” Исторический экскурс
(или благодарности всем тем, без кого эта книга не была бы написана)
По-видимому, в написанной диссертации было бы неправильно не упомянуть (и не поблагодарить — хотя бы с большим опозданием) тех, без кого этой диссертации бы просто не было.
Хотя история не терпит сослагательного наклонения, но вполне возможно, что этой диссертации бы не было на свете, если бы моя школьная учительница (и замечательный педагог) Ксения Тимофеевна Богомазова не подбросила мне в далеком 1965 году “Комсомолку”, в которой на полном развороте были напечатаны задачи Всесоюзной заочной олимпиады по математике (а также по физике и химии), и где красочно описывалось, как в далеком заснеженном Академгородке по улицам мимо беленьких коттеджей бродят академики и физматшкольники и решают задачи. С тех пор целью моей жизни стало попасть в Академгородок, — я заболел им. Кстати, знакомству со своей первой “любимой женщиной” — геометрией - я также обязан Ксении Тимофеевне.
Позже в ФМШ мне посчастливилось попасть на спецкурс В.В. Войтишека по “Неевклидовым геометриям”, который он читал по книге Гильберта и Кон-Фоссена “Наглядная геометрия”. Когда я остался последним слушателем этого спецкурса, Вац.-Вац. просто отдал мне эту книгу “в долгосрочную аренду”, и я целый год с удовольствием читал ее. (Конспект этой книги у меня хранится до сих пор.) Чтобы оценить поступок Вацлава Вацлавовича, нужно знать, что в то время эта книга была огромной библиографической редкостью.
7 Обзор результатов диссертации

пересечение с единичным шаром, должна иметь длину не меньше 1. При выполнении достаточного условия искомая перестановка векторов также находится с трудоемкостью 0(п log п).
В разделе 14 мы переходим от задач нестрогого суммирования в единичных областях к задачам о нестрогом суммировании в семействах областей. Как мы увидим в третьей части диссертации, при анализе задач о нахождении кратчайших расписаний в качестве таких семейств выступают семейства замкнутых полупространств т-мерного пространства. Поэтому далее исследуется именно этот случай. Формулируется б оптимизационных задач о нахождении нестрогого суммирования векторов из исходного 0-семейства в оптимальном (согласно какому-то критерию) семействе полупространств. Задачи различаются критериями и ограничениями на выбор полупространств. В лемме 14.4 показывается, что одна из этих задач без потери точности сводится к другой с понижением размерности пространства на единицу. Далее переходим к решению сформулированных задач в двумерном пространстве. С использованием результатов из предыдущего раздела получаем эффективные алгоритмы приближенного решения этих задач с гарантированными оценками точности, причем показано, что две из полученных оценок являются неулучшаемыми.
В разделе 15 доказываются теорема о суммировании -семейства векторов в прямоугольной области m-мерного пространства, ограниченной единицей по одной координате и константами — по другим координатам48, а также теоремы о суммировании векторов на плоскости внутри минимального угла и в 3-мерном пространстве — внутри октанта49.
Во второй части диссертации рассматриваются комбинаторные задачи различной природы. По большей части они носят вспомогательный характер и используются для решения задач из третьей части. Однако зачастую эти задачи представляют и самостоятельный интерес.
В разделе 17 вводится понятие ранга rm(x) целого числа х € {0,1
В разделе 18 рассматривается задача РРП о равномерном разбиении множества из п предметов на I подмножеств. При этом каждый предмет характеризуется m параметрами, и равномерность разбиения требуется по каждому из m параметров. Экономической интерпретацией этой задачи является известная Задача объемно-календарного планирования (ОКП). В задаче ОКП требуется годовой план предприятия, представленный п наименованиями, разбить по кварталам (или по месяцам) как можно равномернее по
Принадлежащий диссертанту результат из совместной статьи с В. Банащиком [122].
49Результаты из совместной статьи с С.В. Августиновичем [69].