О сложности задач теории расписаний с длительностями, зависящими от времени

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

Оглавление
Введение
Глава 1. Задачи теории расписаний на одной машине с длительностями работ, пропорциональными произвольной функции
1.1. Основные обозначения и определения
1.2. Линейные функции .
1.3. Выпуклые и вогнутые функции
1.4. Ступенчатые функции
Глава 2. Задачи теории расписаний на одной машине с длительностями, линейно или кусочно-линейно зависящими от времени
2.1. Задача минимизации максимального запаздывания с линейными функциями длительностей
2.2. Задача минимизации длины расписания с кусочно-линейными функциями длительностей
2.3. Полиномиальные и псевдополиномиальные алгоритмы для задач с общим директивным сроком
2.4. Сложность задач с общим директивным сроком
Глава 3. Задачи теории расписаний на параллельных ма-
шинах и в многооперационных системах с линейно растущими длительностями
3.1. Основные обозначения и определения
3.2. Вспомогательный результат
3.3. Параллельные машины. ЛГР-трудность
3.4. Многооперационные системы
3.5. Полиномиально-разрешимые случаи
Заключение
Список литературы

Введение
В теории расписаний исследуются вопросы оптимального распределения и упорядочения конечного множества требований, обслуживаемых системами с одним или несколькими ресурсами. Под ресурсами могут пониматься машины, станки, учебные помещения, приборы и т. п.. под требованиями — выполняемые работы, программы, школьные занятия, грузоперевозки и многое другое. Для определенности, в дальнейшем ресурсы будем называть машинами, а требования — работами. Если просмотреть многочисленные статьи, обзоры и монографии, посвященные задачам теории расписаний, то можно обнаружить огромное количество различных задач, рассматриваемых в рамках этой теории. Поэтому необходимо описать, какие именно задачи будут рассматриваться в диссертации и какие ограничения при этом предполагаются.
Первое условие связано с доступностью информации о параметрах задачи. Далее речь пойдет только о детерминированных задачах теории расписаний. В них предполагается, что вся исходная информация об индивидуальной задаче определена и известна заранее.
Остальные ограничения связаны с самими машинами и работами. Обычно каждой работе сопоставляется множество машин, каждая из которых может или должна выполнить эту работу. Такое множество машин называется обслуживающей системой. Если каждая работа мо-

Доказательство проведем для случая Ь).
Рассмотрим два расписания л1 = (яь /,, /;, яг) и 7г2 = (яг, Т;, яг),
отличающиеся друг от друга только положением двух работ 7/ и
Предположим, что
а; — + Я) > а,- — м/((аТ1 + Я). (1-26)
Тогда для работ 7) и 7; выполняется, что оц > а; и и>((аг-1 + Я) < + Я). Сначала, докажем первое неравенство. Предположим обратное, пусть щ < а,-. Тогда из (1.25) + Я) < шДа1 + Я) и,
вычитая последнее неравенство из предыдущего получаем противоречие.
Неравенство + Я) < ш,>(а,_ + Я) в случае а; > а,- следует из
(1.25), а в случае а; = а*- следует из (1.26).
Обозначим через I время завершения работ из перестановки тч. Тогда
7/, 7,) = f(nl) + Wli+wa(i) + Wit + WialT(t) + WiaiT(i+al'T()), /(щ, 7), 7;) = /(я1)+к)7 + »;аД(4) + +гиг*+и№-Т(4) + ГО(а|Т(£+а;Т(?)). Далее имеем
/(Щ, 71; Л) - /(эт1, 7,-, 7;) = шгагТ(£) + ш;а;Т(1) + ю,-аг-Т(£ + а;Т(£))
- гс;а,Т(£) - адаЩг) - «да|Т(£ + а;Т(£)). (1-27)
Рассмотрим линейную функцию 7?(£) = а£ + 5, определенную в предыдущей теореме. Подставив (1.17) в (1.27), получаем
/(гг, 7г, Т,-) - /(»1, 7;, 7/) = ацщЩТ) +и1{СцН(Щ + №;а;Д(£ + а;Д(£))
—к;,-а;Д(£) - ицсчЩ?) - ге/а|Т(£ + а,-Т(£)).