Свойства оптимальных решений и эффективные алгоритмы построения расписаний в системах открытого типа

• Автор: Черных, Илья Дмитриевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 114 с.

Оглавление
Введение
Общая характеристика работы
Главные результаты диссертации
Публикации и апробация результатов исследований
Структура работы
1 Анализ сложности задачи open shop
1.1 Предварительные сведения
1.2 Задача open shop в обобщенной постановке и 4-параметри-
ческий анализ ее сложности
§ 1.2.1 Постановка задачи
§ 1.2.2 Анализ сложности
§ 1.2.3 Таблица результатов анализа
1.3 Установление сложности базисных классов
§ 1.3.1 Полиномиально разрешимые базисные классы
§ 1.3.2 NP-трудность классов l(xj) (j £ {10,..., 14})
§ 1.3.3 NP-трудность классов 1(хg) и Х(хд)
1.4 Заключительные замечания к главе 1
2 Эффективное построение нормальных расписаний
2.1 Предварительные сведения
2.2 Базовые нормальные классы

Оглавление З
§ 2.2.1 Минимальные нормализующие векторы в R2 и R3 .
§ 2.2.2 Величина доминирования
2.3 Эффективно нормализующие векторы в Rm
§ 2.3.1 Метод последовательной достройки нормального расписания
§ 2.3.2 ^-нормализующие и к-достраивающие векторы в Rw
§ 2.3.3 Построение эффективно нормализующих векторов

2.4 Заключительные замечания к главе
3 Интервал локализации оптимумов задачи open shop
3.1 Предварительные сведения
3.2 Точный интервал локализации оптимумов задачи open shop
с тремя машинами
§3.2.1 Основные формулировки
§ 3.2.2 Процедура “склеивания” работ
§ 3.2.3 Описание доказательства леммы 3.
3.3 Иллюстрация компьютеризированного подхода: локализация оптимумов для задачи о сборочной линии
3.4 Заключительные замечания к главе
Литература

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

Глава 1 Анализ сложности задачи OPEN SHOP

Monotone-Not-All-Equal-3Sat [16].
ВХОД: Множество булевых переменных U и набор С дизъюнкций над U такой, что каждая дизъюнкция с 6 С состоит не более чем из трех литералов, а каждый литерал является переменной из U без отрицания. ВОПРОС: Существует ли такое назначение переменных, доставляющее значение истина всем дизъюнкциям с £ С, что в каждой дизъюнкции найдется по крайней мере один истинный и один ложный литерал?
Для доказательства NP-трудности класса 1(х%) (и симметричного ему класса Х(хд)) воспользуемся той же схемой: искомая NP-трудность будет следовать из NP-полноты задачи распознавания существования расписания длины 6 для входов / £ Х(а?в), а для доказательства NP-полноты последней будет использована та же эталонная NP-полная проблема. Единственное отличие от схемы из [16], которое мы должны обеспечить при построении входа I £ Т{х%) по заданному входу эталонной проблемы, состоит в том, чтобы каждая работа имела не более двух операций. То, как реализуется данное требование, будет видно из доказательства следующей леммы.
Лемма 1.5 Проблема распознавания существования расписания длины
6 для задачи open shop со входом из Х(х%) является NP-полной.
Доказательство. Пусть задан вход задачи Monotone-Not-All-Equ-L-3Sat. Последнее означает, что на множестве логических переменных
7 = {ад,...,Тц} задано семейство дизъюнкций С = {ci,... ,с„}, где саждая дизъюнкция щ £ С состоит не более чем из трех литералов. Зез ограничения общности можем считать, что каждая дизъюнкция а юстоит в точности из трех литералов: q = 1ц V ^2 V 1ц. (В противном