Содержание к диссертации
Введение 7
1 Оценка абсолютной погрешности задач минимизации
максимального временного смещения 42
Постановка задачи 1 | гj | Lmax 42
Обозначения и определения основных понятий 44
Абсолютная погрешность приближённого решения 47
Схема нахождения приближённого решения 52
1.4.1 Вариант схемы на основе случая
1 | di < dj,di - Гі -pi > dj - rj -pj | Lmax 55
1.4.2 Вариант схемы на основе случая Хогевена 63
1.5 Экспериментальное исследование полиномиальных алгоритмов решения
задачи 1 | r;- | Lmax 67
Способ генерации примеров 68
Оценка экспериментального значения
абсолютной погрешности 70
1.5.3 Эффективность применения полиномиальных
алгоритмов для общего случая задачи 71
Свойства оптимальных расписаний общего случая задачи l|rj|Lmai ... 76
Свойства оптимальных расписаний
частных случаев задачи l\rj\Lmax 94
1.8 Оценки абсолютной погрешности 99
1.8.1 Задачи для нескольких приборов 100
1.8.2 Оценка абсолютной погрешности 104
1.8.3 Схема приближённого решения задачи Р | prec, г,-( Lmax 110
Нормированное пространство примеров 112
Схемы нахождения приближённого решения 116
1.10.1 Схема Сведения Задач О. | р | -i/max —^ СК J /О | Стах И
а | Р, г, | ^тах ->a\{3,rj = 0\ тах 116
1.10.2 Схема сведения задач а \ /3,pj | Lmax -> а | (3,Pj — р | Lmax и
а | /3,pj | Lmax -> а | APj = l I ^max 117
Схема сведения задач {К, Q} \ /3 \ Lmax —> Р | /3 | Lmax . . 118
Схема сведения задачи R \ /3 | Lmax -> Q | /3 | Lraax 119
Схема сведения задачи а|^|ітах->а|^,ріє{ріІ...>р*}|Стах 120
2 Полиномиально и псевдополиномиально разрешимые случаи задачи
1 I г,- | тах 122
2.1 Задача 1 | d, < dj, d{ ~ г,- - р* > rfj - г,- - pj | Lmax 122
Свойства задачи 122
Задача на быстродействие при ограничении на
максимальное временное смещение 131
2.1.3 Алгоритм построения множества Парето-расписаний
ПО Критериям Сщах И Шах 134
"Двойственная" задача 139
"Обратная" задача 143
3 Алгоритмы оптимального решения задачи 1 | r3-,\ Lmax 147
3.1 Существующие методы решения задачи 1 | Vj \ Lm&x .... 149
Алгоритм Карлье 149
Метод программирования в ограничениях 153
Алгоритмы решения задачи 1 | г,- | Lmax 160
Экспериментальное сравнение алгоритмов
решения задачи 11 г,- | Lmax 166
Модифицированный алгоритм Карлье 172
Эффективные алгоритмы решения задачи минимизации максимального временного смещения 181
3.5.1 Процедура построения приближённого решения задачи
l|rt- < Tj,di > dj\Lmax. Оценка абсолютной погрешности 181
3.5.2 Процедура построения допустимого расписания
для задачи 1\п < r^&i > dj\Lmax 192
Алгоритм решения задачи 1|гг- < r^d,- > dj\Lmax 202
Полиномиальные алгоритмы решения частных случаев
задачи l|r; < r,-,dj > dj\Lmax 204
3.6 Приближённый алгоритм решения общего
случая задачи. Оценка абсолютной погрешности 206
4 Алгоритм ветвей и отсечений для решения задачи 1 | г,- | YlwjUj 211
4.1 "Гибридная" схема решения одного класса задач
целочисленного линейного программирования 212
Постановка задачи 220
Формулировка задачи 1 | rj \ YlwjUj как задачи ЧЦЛП 222
4.3.1 Дополнительные ограничения 225
Генерация отсечений 229
"Гибридный" алгоритм ветвей и отсечений 240
Экспериментальная оценка эффективности 241
5 Исследование свойств задачи 1 11 J^ Tj 250
Постановка задачи суммарного запаздывания для одного прибора .... 251
Алгоритмы построения оптимальных расписаний, основанные
на "декомпозиционных" свойствах задачи 259
Построение оптимальных расписаний в случае фиксированного количества запаздывающих требований 269
Канонические примеры задачи 1||]Г]7) 276
5.4.1 Задача ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ (ЧНР) 276
Канонические DL-примеры задачи 1||7} 277
Канонические LG-примеры задачи 1||7} 279
Свойства канонических LG примеров задачи 111 ) 7} 280
5.5 Трудоёмкость алгоритмов 297
Канонические DL-примеры задачи l||Tj 298
Трудоёмкость алгоритмов для канонических DL-примеров .... 307
Трудоёмкость алгоритмов решения задач случая BF 308
5.6 Оценки SPT расписаний 312
Первая оценка 313
Вторая оценка 315
Задача построения набора требований с заданным оптимальным значением целевой функции 318
5.7 Результаты экспериментальных исследований 319
6 Полиномиально и псевдополиномиально разрешимые случаи задачи
111 2} 327
Свойства оптимальных расписаний 329
Подход к решению задачи 332
Алгоритмы решения задачи 1 || 7) 335
Алгоритм ВЛ 335
Алгоритм В-к 340
Алгоритм СЛ 344
Алгоритм В-п 350
7 Исследование свойств и приложения алгоритма ВЛ 355
Свойство В-1 356
Алгоритм решения задачи РАЗБИЕНИЕ 359
Постановка и полиномиальная сводимость задач разбиения .... 359
Алгоритм В-1-канонический 363
7.3 Алгоритм ВЛ-модифицированный 366
8 Графический подход к решению задач комбинаторной оптимизации 375
8.1 Графический алгоритм для задачи РАЗБИЕНИЕ 376
8.1.1 Идея графического алгоритма 376
Сокращение рассматриваемых интервалов 378
Пример задачи РАЗБИЕНИЕ 378
Трудоёмкость алгоритма 382
Экспериментальная оценка трудоёмкости алгоритма 384
8.2 Графический подход для задачи одномерный РАНЕЦ (0 — 1 knapsack) . 386
Алгоритм динамического программирования для задачи РАНЕЦ 386
Графический подход 387
Эффективность графического алгоритма 392
Заключение 394
Список литературы
Введение к работе
Общее направление исследований
Люди на протяжении всей жизни сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение. Так как лучше получить на экзаменах три четвёрки, чем две пятерки и одну тройку,— стипендии не будет... Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом всё более и более трудные задачи разработки алгоритмов составления расписаний.
Теория расписаний является одним из разделов исследования операций. Термин "теория расписаний" предложил Р. Беллман в 1956 году [84]. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации.
Диссертационная работа посвящена исследованию iVP-трудных задач теории расписаний для одного и нескольких приборов, а также задач РАЗ-
БИЕНИЕ и РАНЕЦ. Важным является разработка новых математических методов и эффективных алгоритмов решения этих задач.
Данное направление в науке, получившее название "теория расписаний", берёт свое начало с известной работы в данной области Генри Гантта 1903 г. (Gantt H.L. [117]), предложившего то, что сегодня называют диаграммами Гантта, которые встречаются во многих работах по теории расписаний, в том числе и в данной работе. С 50-х годов 20-го века началось активное теоретическое исследование задач теории расписаний, следует отметить работы Джонсона (Johnson [131]), Джексона (Jackson [129]) и Смита (Smith [197]), а также монографии [12, 61].
Одним из главных вопросов нового направления была классификация задач и установление их сложности. В настоящее время наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. (Graham at al. [121]). Относительно быстро была установлена сложность большого числа задач. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэ-ри и Джонсона (Garey, Johnson [7]), Ленстры и др. (Lenstra et al. [162]), Лоулера и др. (Lawler et al. [142]), Танаева и др. [61, 62, 63], Брукера и ДР. [95, 96].
Рассмотрим постановку задачи теории расписаний. Множество требований N = {1,2,...,п} должно быть обслужено без прерываний на одном или нескольких приборах M{,i = 1,...,m, которые могут обслуживать не более одного требования в каждый момент времени. Время обслуживания требования j Є N на приборе М{ обозначается как Pji,Pji > 0. Момент, когда требование j становится доступным для обслуживания, задаётся временем поступления Ту Требование j может иметь директивный срок dj (время, до которого желательно завершить обслуживание требования), а также вес Wj (значимость, важность требования). Между требования-
ми могут быть заданы отношения предшествования в виде ациклического ориентированного графа G. В подавляющем большинстве задач теории расписаний целью является построение оптимального расписания по определённому критерию или совокупности критериев. Для представления различных критериев нам необходимы следующие определения. Момент окончания обслуживания требования j при расписании тт будем обозначать через Cj(7r). Определим Lj(7r) — Cj(7r) — dj как временное смещение требования j при расписании 7г, a Tj(ir) = max{0, Lj(ir)} ~ как его запаздывание. Uj(it) обозначает запаздывает ли требование j при расписании 7г или нет: Uj(ir) = 1, если j запаздывает (Cj(ir) > dj), иначе Uj{ii) = О (требование j обслуживается вовремя). Классическими критериями в задачах теории расписаний являются: Стах — минимизация максимального времени окончания обслуживания (задача на быстродействие); Lmax — минимизация максимального временного смещения; ^Tj — минимизация суммарного запаздывания; YlwjUj ~ минимизация взвешенного числа запаздывающих требований. Заметим, что данные критерии являются регулярными, т.е. данные функции являются неубывающими по отношений к моментам окончания обслуживания требований. При наличии регулярного критерия мы можем ограничиться рассмотрением только ранних расписаний, без искусственных простоев приборов.
Через щ будем обозначать перестановку (расписание) из элементов множества N, обслуживаемых на приборе М;, і ~ 1,..., т, множество требований в расписании щ обозначим {щ} С N, а через -к = 1J х щ, {7га} П!71^} = 0, если а ф (3, расписание для всего множества требований N = {тг}. Рассматриваются только допустимые расписания, удовлетворяющие отношениям предшествования. Для любого ациклического графа G множество допустимых расписаний не пусто. Момент окончания обслуживания требо-
вания j на приборе М,- при расписании 7Г определяется как Cj(ir) =ma.x{rj,mdLxCk(n), max С*(7г*)}+р«,
где iVj — множество требований предшествующих требованию j, согласно графу (7, и (& —> j%. требования, согласно расписанию 7гг- на приборе Mj, предшествующих обслуживанию требования j Є {щ}. Предполагается, что для пустого расписания (7(0) = г^ + ] для всех требований к, для которых нет предшествующих требований, при обслуживании на приборе М{. Множество расписаний обслуживания требований множества N, допустимых относительно графа предшествования (7, будем обозначать через U(N).
Если обслуживание требования і предшествует обслуживанию требования j, i,j Є АГ, при расписании 7Г, то это будем обозначать через (г -» j)n или г-> j, чтобы "не перегружать" нижний индекс.
Для представления задач построения оптимальных расписаний обслуживания требований множества N, рассмотренных в данной работе, мы будем использовать обозначение а\/3\у [121]. Первое поле а описывает обслуживающую систему: Р - параллельные идентичные приборы; Q - параллельные приборы разной производительности; R - параллельные различные приборы; F - flow—shop - каждое требование должно быть обслужено каждым из приборов множества М = {1,..., т} в порядке 1,..., т. Во втором поле Р описываются характеристики требований и отношения предшествования между ними: г/ - заданы моменты поступления требований на обслуживание; pj = р - все требования имеют одинаковые продолжительности обслуживания; ргес - между требованиями заданы отношения предшествования. Третье поле 7 описывает критерий задачи, который состоит в отыскании допустимого (относительно графа предшествования) расписания, минимизирующего целевой функционал.
Отметим, что подавляющее большинство исследованных задач теории расписаний являются ІУР-трудньїми. Несмотря на это, практика требует решение таких задач. Для этого существует несколько подходов.
Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближёнными [15, 56]. Существуют приближённые алгоритмы, гарантирующие как относительную погрешность [9, 191], так и абсолютную погрешность [59]. Некоторые iVP-трудные задачи допускают существование так называемой аппроксимационной схемы. В рамках данной схемы можно найти приближённое решение с относительной погрешностью не более любого заданного значения є > 0 за время, полиномиально зависящее от І/є и от размера входной информации задачи,— вполне полиномиальная аппроксимационная схема (FPTAS). Для задач теории расписаний такие схемы разработали, например, Ковалёв [11], Алон и др. (Alon et al. [72]), Мастролилли (MastroliUi [166]), Севастьянов и Вёгингер (Sevastia-nov, Woeginger [192]. Для задач, не имеющих аппроксимационной схемы, большое значение имеет установление предельного значения є, для которого возможно нахождения ^-приближённого решения за полиномиальное время,— полиномиальная аппроксимационная схема (PTAS).
В настоящий момент широкое распространение имеют метаэвристиче-ские алгоритмы (еще их называют алгоритмами "локального поиска"), которые находят "хорошее" решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. Неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Точным методам решения JVP-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение
получили методы сокращённого перебора, также называемые методами ветвей и границ [13, 60, 90, 98, 137]. Для сокращения перебора вычисляются нижние оценки целевой функции (в случае её минимизации) и используются комбинаторные свойства задач. Также для решения задач теории расписаний широко применяется метод динамического программирования [1, 7, 56, 57, 95,133].
Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [69, 70, 182, 198].
В последнее время широкое распространение получил метод программирования в ограничениях (ПвО, в англоязычной литературе - Constraint Programming). Одной из областей его успешного применения является теория расписаний [81].
Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — "гибридные алгоритмы" [14, 130]. На данный момент данное направление, на наш взгляд, является одним из перспективных.
Цель работы
Целью работы является разработка новых алгоритмов, как приближённых, так и точных алгоритмов сокращённого перебора, для решения NP-трудных задач теории расписаний как для одного, так и для нескольких приборов: 1 | г, | Lmax,Cmax; 1 | г, | ^- 1 || 7}; {P,R,Q,F} I prec,rj I {Lmax, Cmax}, а также алгоритмов решения классических задач РАЗБИЕНИЕ и РАНЕЦ. Кроме того, важным является введение метрики для задач теории расписаний минимизации максимального временного смещения.
Методы исследования
В диссертационной работе для нахождения эффективных нижних оценок и приближённых решений исследуемых задач используется метод изменения параметров требований и приборов, а также целевой функции. Достоверность результатов диссертации подтверждается приведёнными доказательствами всех утверждений, сформулированных в работе.
Научная новизна
Для задач теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения впервые введена метрика р. Доказана теорема об абсолютной погрешности.
Предложена новая схема нахождения приближённого решения задач теории расписаний, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится такое изменение исходных параметров примера A (rf, р$, df\j Є N,i Є М), чтобы полученный пример В с параметрами требований (rf,pf{,df\j Є N,i Є М) принадлежал заданному полиномиально/псевдополиномиалыю разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния р(А, В) между примерами. Данный подход позволяет находить эффективные нижние оценки целевой функции, которые можно использовать в методах сокращённого перебора для оптимального решения задачи.
Поставлена и решена задача, в некотором смысле "двойственная" к за-
даче 1 I гj I /max при произвольных неубывающих функциях штрафа, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной ІУР-трудной задачи 1 | т$ | /тах и может быть использована в алгоритмах сокращённого перебора.
Для iVP-трудной задачи 1 || 5^2), когда параметры требований удовлетворяют ограничениям р\ > р2 > > Рп, d\ < d-i < ... < dn, построен псевдополиномиальный алгоритм трудоёмкости 0(n2J2Pj) операций.
Предложена графическая реализация метода динамического программирования, на основе которой построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.
Теоретическая и практическая значимость
Предложенные подходы могут быть использованы для разработки алгоритмов решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть полезны специалистам занимающимися проблемами дискретной оптимизации.
Структура и обзор результатов диссертации
В разделе 1.1 первой главы рассматриваются постановки задач минимизации максимального временного смещения (Lmax), дан краткий исторический обзор задач, приведены основные результаты, существующие в литературе. В разделе 1.2 вводятся обозначения и определения, которые
используются далее в работе. В разделе 1.3 формулируется и доказывается теорема об абсолютной погрешности [28].
Теорема 0.1 Пустъ A = {G, (rf,pf, df)\j eN}uB = {G, (rf.pf, df)\j G
iV} (с идентичным графом предшествования G) - два примера NP-трудной задачи Р \ prec, rj | Lmax, тогда
Li^B)-Ltx{
где 7Ґ4,7Г8 - оптимальные расписания примеров А и В,
p{A,B) = pr{A,B)+pd(A,B) + pp(A,B),
рг(А, В) = maxjeiV{r/ - rf} - mmjeN{rf - rf}, pd(A, В) = maxjeN{df - df} - mmjeN{df - df},
рр(АВ) = Еієм\рі-р!\-
Мы можем использовать оптимальное расписание примера В для решения исходного примера А. Если пример В принадлежит некоторому полино-миально/псевдополиномиально разрешимому подмножеству примеров, то необходимо найти такой пример из этого подмножества, до которого расстояние р(А, В) было бы минимальным. Искомое оптимальное значение будет принадлежать интервалу ^ах(тгл) G [^ах(тгв) - р(А, В), L^Jp8)].
Рассмотрим полиномиалыю/псевдополиномиалыю разрешимый случай исходной задачи, когда параметры требований удовлетворяют к линейно независимым неравенствам
XR + YP + ZD
где R = (п,..., гп)Т, Р = (ph... ,рп)т, D = (dh..., dn)T, и X,Y, Z - матрицы размерности к X п, а Н = (hi,..., hk)T - fc-мерный вектор (верхний индекс т обозначает операцию транспонирования). Затем в этом
классе примеров находим пример В с минимальным расстоянием р(А, В) до исходного примера А, решая следующую задачу
' (xd -yd + xr~ f) + J2jeN tf —* min yd
Vr
-x] < pf-pf
Рассмотрим совокупность примеров задачи Р\ргес, Г{\Ьтах с количеством требований п, количеством приборов т и ориентированным графом предшествования G. Данная совокупность примеров образует Зп-мерное линейное пространство (Зп параметров: rj,pj,dj,j = 1,п). Два примера А = {G, (rf,pf,df)\j Є N} и В = {G, (rf,pB,df)\j Є iV} будем называть эквивалентными, если существуют константы d и г, что df = dB + d, rf = rB+r,pf = pf, V? Є N. Полученное семейство классов эквивалентности является (Зп — 2)-мерным линейным пространством, которое обозначим через Сп. Будем говорить, что пример А принадлежит классу Сп, если выполняется условие г\ = d\ = 0. Несложно показать, что у эквивалентных примеров совпадают множества оптимальных расписаний. На пространстве классов эквивалентности примеров рассмотрим следующий функционал
У А Є Сп, <р(А) = max rf - min rf + max df - min df + ^\pf\> 0.
' jeN 2 JEN J jeN J jeN 3 ^' Jl~
Данный функционал удовлетворяет трём свойствам нормы: <р(А) = 0 <=> А = 0; <р(аА) = aip{A); <р(А + В) < <р{А) + <р(В).
Таким образом, Сп является (Зп — 2)-мерным линейным нормированным пространством с нормой ||Л|| = <р(А).
Теорема 0.2 [28] Функция р(А,В) = \\А — В\\ удовлетворяет свойствам нормированной метрики в (Зп — 2)-мерном линейном пространстве параметров требований {(fj,Pj,dj)\j Є N}.
В случае, когда для исходной задачи нет полиномиально и псевдополиноми-ально разрешимых выделенных подслучаев задачи (в скобках заметим, что тривиальные подслучаи задачи обычно не позволяют найти качественно новые оценки абсолютной погрешности), либо "расстояние" р(А, С) до любого полиномиалыю/псевдополиномиально разрешимого примера С "слишком велико", тогда можно использовать следующую теорему.
Теорема 0.3 Пусть A = {G, (rf,pf,df)\j N}uB = {G, (rf,pf,df)\j Є
N} (с идентичным графом предшествования G) два примера, тогда для любого приближённого расписания 7f верно
0 < Li„(Tf) - LtAA < sBW + Р(АВ), где 6*(ж) = LBmaM - LaI(nB).
Предлагается общая схема приближённого решения задач минимизации -^тах- Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение, с минимальным расстоянием до исходного примера в введённой метрике.
Во второй главе представлены новые полиномиально и псевдополипо-миально разрешимые случаи іУР-трудной в сильном смысле задачи l|rj|Lmaa;
В разделе 2.1 рассмотрен случай [23, 27, 47], когда параметры требований удовлетворяют следующим ограничениям:
f di<...
[ di-ri-pi>...>dn-rn-pn.
Данным ограничениям соответствует случай, когда dj = rj -f pj + z, j — 1,..., n, где z - константа, т.е. когда все требования имеют одинаковый запас времени до своего директивного срока. Алгоритмом [27] за 0(n3 log п) операций может быть найдено Парето-оптималыюе множество (по критериям Lmax и Стах), состоящее не более чем из п расписаний, решение общей двукритериальной задачи l\rj\Lmax,Cmax-
Теорема 0.4 [46, 4^1 Для любого примера А задачи 1 | г$ | Ьтдх, не принадлежащего исследуемому классу, и для любого примера С, наследующего длительности обслуоісивания примера А и принадлежащего данному классу, справедлива оценка расстояния между А и С:
р(А, С) > р\А) = maxmin^/ - df, (df - rf - pf) - (df - rf - pf)}.
Оценка достигается на некотором примере С, который может быть найден за время O(nlogn).
Кроме того, был рассмотрен полиномиально разрешимый случай Хоге-вена [126]: тах&едг{<4 —r^ — pk} < dj — rj, V? Є N. Оптимальное расписание находится за 0(n2\ogn) операций.
Теорема 0.5 Для любого примера А задачи l\rj\Lmax, не принадлежащего классу Хогевена, и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего классу Хогевена, справедлива оценка расстояния меоюду А и С:
р(А, С) > рн(А) = max{df - rf - pf - df + rf}.
Оценка достигается на некотором примере С, который может быть найден за время 0{п).
Для более сложного iVP-трудного подслучая задачи l\rj\Lmax, когда параметры требований удовлетворяют ограничениям:
d\ < d2 < ... < dn; П>г2> ... > rn;
предлагается псевдополиномиальный алгоритм решения [52, 55] Трудоёмкого
сти 0(п2Р+пртахР) операций, где Р = max{rmax, t} + pj -max{rmin, і}, fmax = maxn, rmin = minr,-, pmax = maxpj, a t- момент времени, с которого
jN jeN jeN
прибор готов начать обслуживать требования множества N.
Для получения нижних оценок целевой функции был также использован следующий подход. Рассмотрим общую постановку JVP-трудной задачи
fmax-
ireU{N) k=l,n
где fjk(Cjk(ir))- произвольные неубывающие функции штрафа. Решим задачу нахождения величины и*:
г/* = тах min fjk{Cik(nj).
k=l,n 7reII(iV)
Теорема 0.6 [18, 23] Для NP-трудной задачи l|rj|/max с произвольными неубывающими функциями штрафа fj(t),Vj Є N, верно и* < /і* и величина v* может быть найдена за 0(п2) операций.
Третья глава диссертации посвящена алгоритмам оптимального решения задачи 1 | r;- | Lmax. В разделе 3.1 рассмотрены существующие подходы
к решению задачи, такие как алгоритм Карлье [98] и метод программирования в ограничениях [81] (ПвО). Данный метод близок к методу ветвей и границ. Отличие заключается в том, что для сокращения перебора в ПвО используется пропагация ограничений, которая удаляет несовместимые значения из множеств допустимых значений переменных.
В разделе 3.2 предлагаются два алгоритма оптимального решения задачи 1 | Tj | i/max- Первый алгоритм построен по методу ПвО. На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенное нами правило ветвления, основанное на следующей теореме.
Теорема 0.7 Пусть построено расписание Шраге [185] ка и требования пронумерованы в том порядке, в котором они упорядочены в к'. Пусть Ь Є N - наименьший номер, для которого Ьъ(ка) = -^шах^); и а Є N -наибольший такой номер, что а <Ь и
Са{*) - Ра - ШІП Tj < Lb{ita) - UB, a
где UB < Lmax(ira), UB - верхняя оценка оптимального решения. Примем S = {а,... ,Ь}, тогда:
если не существует такого требования с Є S, что dc > dt, то не существует расписания с Lmax меньшим, чем UB;
если с Є S - последнее требование с директивным сроком dc > dj,, то в любом расписании ж', что Ьтах(тт') < UB, выполняется либо (с -> 3)жі, либо (J —» с)жі, где J = {с + 1,..., Ь].
Второй алгоритм построен по методу ветвей и границ. В алгоритме также используется правило ветвления, основанное на теореме 0.7. Отличительной особенностью алгоритма является использование алгоритмов ПвО на каждом узле дерева поиска.
В разделе 3.3 приводятся результаты экспериментального сравнения точных алгоритмов решения задачи 1 | rj | Lmax, предложенных в работе, и подходов, существующих в литературе.
В разделе 3.4 рассматривается вариант распознавания задачи 1 | г/ | Lmax- Назовем расписание 7Г допустимым по отношению к константе Z/, если ^тах(тг) < L'. Множество требований S допустимо по отношению к константе I/, если существует допустимое расписание 7Г П(5), и недопустимо, если не существует такого расписания. В рассматриваемом варианте задачи требуется определить допустимо ли множество требований N по отношению к заданной константе V. Если N допустимо, то необходимо найти допустимое расписание. Если же iV недопустимо, то требуется найти как можно меньшее недопустимое подмножество требований из множества N. Для данного варианта задачи предлагается алгоритм, который является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований S С iV, не обязательно минимальное, когда множество требование N недопустимо. В тоже время, алгоритм точно определяет, допустимо ли множество требование N. Правило ветвления алгоритма основано на следующей теореме.
Теорема 0.8 Пусть Ьтах{ка) > L' и требования пронумерованы в том порядке, в котором они упорядочены в іга, Ь Є N — наименьший номер, для которого Ьь(ка) > L', и а Є N - наибольший номер, что а <Ь и
Са{ъа) -ра- minr,- < Ьъ(т?) - L',
где S = {a,..., b}. Тогда:
если не существует такого требования с Є S, что dc > db, то множество требований S недопустимо по отношению к V;
если с Є S - последнее требование с директивным сроком dc > db, и
существует допустимое расписание я7, то выполняется либо (с -» J)ni, либо (J -> с)жі, где J = {с + 1,..., 6}.
Отличительной чертой модифицированного алгоритма Карлье является способ построения недопустимого подмножества требований в случае, если алгоритм не нашёл допустимого расписания. На каждом узле дерева поиска, где не происходит ветвления, согласно теореме 0.8, мы располагаем подмножеством S, недопустимым для задачи с текущими параметрами требований. Данное подмножество "передаётся родительскому" узлу дерева поиска. Способ построения недопустимого подмножества для узла, имеющего "дочерние" узлы, обоснован в теореме.
Теорема 0.9 Пусть при любом допустимом расписании п' Є n(iV) требование сЄ N обслуживается до или после всех требований множества J С N, S' С N - недопустимое множество требований, когда (с —> J)n> a S" С N - недопустимое подмножество, когда (J —> с)^. Тогда:
если с . S' (с S"), то мнооїсество S' (S") недопустимо;
если с Є S' и с Є S", то множество S = J U S' U S" недопустимо.
В четвёртой главе диссертации предлагается точный алгоритм решения задачи 1 | гj | J2wjUj- Алгоритм построен по "гибридному" методу [14], который представлен в разделе 4.1.
В последующих разделах задача 1 | rj \ Y^wjUj формулируется как задача целочисленного линейного программирования (ЦЛП) и решается методом отсечения и ветвления. Пусть булева переменная Xj принимает значение 1, если требование j Є N обслуживается вовремя и 0 - если тре-
бование j Є N запаздывает.
Y^j Wj(l — Xj) —> min
disjunctive^), ^{0, l}n.
Ограничение disjunctive (я) выполняется тогда и только тогда, когда множество требований J — {j : Xj — 1} может быть обслужено на одном приборе без прерываний и с соблюдением времён поступления и директивных сроков, 1^в{х) ~ релаксация ограничения disjunctive. В разделе 4.4 рассматриваются различные варианты релаксации.
Лемма 0.1 Пусть для двух требований i,j Є N выполняется г і < dj. Если вектор х удовлетворяет ограничению disjunctive, тогда х также удовлетворяет ограничению1
]Tmin[dy - п, (pi - ma,x{au,l3ji})+]xi < dj - г*, leN
где an - (г,- - r/)+ и ft/ = (d/ - dj)+.
Похожие диссертации на Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации
