Общее направление исследований.
Люди на протяжении всей жизни сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение. Так как лучше получить на экзаменах три четвёрки, чем две пятерки и одну тройку, — стипендии не будет. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом всё более и более трудные задачи разработки алгоритмов составления расписаний.
Теория расписаний является одним из разделов исследования операций. Термин «теория расписаний» предложил Р. Беллман в 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,., п} должно быть обслужено без прерываний на одном или нескольких приборах Mi, i = 1 ,., m, которые могут обслуживать не более одного требования в каждый момент времени. Время обслуживания требования j Е N на приборе Mi обозначается как Pji, Pji > 0. Момент, когда требование j становится доступным для обслуживания, задаётся временем поступления rj. Требование j может иметь директивный срок dj (время, до которого желательно завершить обслуживание требования), а также вес Wj (значимость, важность требования). Между требованиями могут быть заданы отношения предшествования в виде ациклического ориентированного графа G. В подавляющем большинстве задач теории расписаний целью является построение оптимального расписания по определённому критерию или совокупности критериев. Для представления различных критериев нам необходимы следующие определения. Момент окончания обслуживания требования j при расписании тг будем обозначать через Cj (тг). Определим L^k) = Cj (тг) — dj как временное смещение требования j при расписании тг, a Tj{тг) = шах{0, Lj (tt)} ~ как его запаздывание. Uj (ir) обозначает запаздывает ли требование j при расписании тг или нет: Uj (тг) = 1, если j запаздывает (Cj (тг) > dj), иначе Uj (тг) = О (требование j обслуживается вовремя). Классическими критериями в задачах теории расписаний являются: Стах — минимизация максимального времени окончания обслуживания (задача на быстродействие) — Lm3X — минимизация максимального временного смещения- ^ Tj — минимизация суммарного запаздыванияJ^WjUj — минимизация взвешенного числа запаздывающих требований. Заметим, что данные критерии являются регулярными, т. е. данные функции являются неубывающими по отношений к моментам окончания обслуживания требований. При наличии регулярного критерия мы можем ограничиться рассмотрением только ранних расписаний, без искусственных простоев приборов.
Через TTj будем обозначать перестановку (расписание) из элементов множества N, обслуживаемых на приборе Mi, i ~ 1,., m, множество требований в расписании щ обозначим {щ} С JV, а через 7 г = jj™ х тг,-, {тга} П!71″ /?} = 0, если, а Ф (3, расписание для всего множества требований N = {тг}. Рассматриваются только допустимые расписания, удовлетворяющие отношениям предшествования. Для любого ациклического графа G множество допустимых расписаний не пусто. Момент окончания обслуживания требования j на приборе М (при расписании 7 Г определяется как.
Cj (7г) = max{r—, max С* (7г), max Ck (щ)} + ри, keNj {k->j)ni где Nj — множество требований предшествующих требованию j, согласно графу G, и (к —> j) n. требования, согласно расписанию щ на приборе Mi, предшествующих обслуживанию требования j Е {^i}- Предполагается, что для пустого расписания С&-(0) = г^ +ры для всех требований к, для которых нет предшествующих требований, при обслуживании на приборе Mi. Множество расписаний обслуживания требований множества N, допустимых относительно графа предшествования G, будем обозначать через П (N).
Если обслуживание требования i предшествует обслуживанию требования j, i, j G N, при расписании тг, то это будем обозначать через (г j) n или г Aj, чтобы «не перегружать» нижний индекс.
Для представления задач построения оптимальных расписаний обслуживания требований множества N, рассмотренных в данной работе, мы будем использовать обозначение а/3у [121]. Первое поле, а описывает обслуживающую систему: Р — параллельные идентичные приборыQ — параллельные приборы разной производительностиR — параллельные различные приборыF — flow—shop — каждое требование должно быть обслужено каждым из приборов множества М = {1,., т} в порядке 1,., т. Во втором поле (3 описываются характеристики требований и отношения предшествования между ними: — заданы моменты поступления требований на обслуживаниеpj = р — все требования имеют одинаковые продолжительности обслуживанияргес — между требованиями заданы отношения предшествования. Третье поле 7 описывает критерий задачи, который состоит в отыскании допустимого (относительно графа предшествования) расписания, минимизирующего целевой функционал.
Отметим, что подавляющее большинство исследованных задач теории расписаний являются iVP-трудными. Несмотря на это, практика требует решение таких задач. Для этого существует несколько подходов.
Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближёнными [15, 56]. Существуют приближённые алгоритмы, гарантирующие как относительную погрешность [9, 191], так и абсолютную погрешность [59]. Некоторые iVP-трудные задачи допускают существование так называемой аппроксимациопной схемы. В рамках данной схемы можно найти приближённое решение с относительной погрешностью не более любого заданного значения е > 0 за время, полиномиально зависящее от 1/е и от размера входной информации задачи, — вполне полиномиальная аппроксимационная схема (FPTAS). Для задач теории расписаний такие схемы разработали, например, Ковалёв [И], Алон и др. (Alon et al. [72]), Мастролилли (Mastrolilli [166]), Севастьянов и Вёгингер (Sevastia-nov, Woeginger [192]. Для задач, не имеющих аппроксимациопной схемы, большое значение имеет установление предельного значения е, для которого возможно нахождения-приближённого решения за полиномиальное время, — полиномиальная аппроксимационная схема (PTAS).
В настоящий момент широкое распространение имеют метаэвристиче-ские алгоритмы (еще их называют алгоритмами «локального поиска»), которые находят «хорошее» решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. Неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Точным методам решения iVP-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение получили методы сокращённого перебора, также называемые методами ветвей и границ [13, 60, 90, 98, 137]. Для сокращения перебора вычисляются нижние оценки целевой функции (в случае её минимизации) и используются комбинаторные свойства задач. Также для решения задач теории расписаний широко применяется метод динамического программирования [1, 7, 56, 57, 95,133].
Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [69, 70, 182, 198].
В последнее время широкое распространение получил метод программирования в ограничениях (ПвО, в англоязычной литературе — Constraint Programming). Одной из областей его успешного применения является теория расписаний [81].
Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — «гибридные алгоритмы» [14, 130]. На данный момент данное направление, на наш взгляд, является одним из перспективных.
Цель работы.
Целыо работы является разработка новых алгоритмов, как приближённых, так и точных алгоритмов сокращённого перебора, для решения NP-трудных задач теории расписаний как для одного, так и для нескольких приборов: 1 | rj | Lmax, Cmax- 1 | rj | 1 II E^'i {P, R, Q, F} I prec, rj | {-^max, Cmax}, а также алгоритмов решения классических задач РАЗБИЕНИЕ и РАНЕЦ. Кроме того, важным является введение метрики для задач теории расписаний минимизации максимального временного смещения.
Методы исследования.
В диссертационной работе для нахождения эффективных нижних оценок и приближённых решений исследуемых задач используется метод изменения параметров требований и приборов, а также целевой функции. Достоверность результатов диссертации подтверждается приведёнными доказательствами всех утверждений, сформулированных в работе.
Научная новизна.
Для задач теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения впервые введена метрика р. Доказана теорема об абсолютной погрешности.
Предложена новая схема нахождения приближённого решения задач теории расписаний, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится такое изменение исходных параметров примера A (rf, pfi, dfj G N, i G М), чтобы полученный пример В с параметрами требований (rf, pfi, dfj G N, i G М) принадлежал заданному полиномиально/псевдополиномиалыю разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера, А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния р (А, В) между примерами. Данный подход позволяет находить эффективные нижние оценки целевой функции, которые можно использовать в методах сокращённого перебора для оптимального решения задачи.
Поставлена и решена задача, в некотором смысле «двойственная» к задаче 1 | Tj | /max при произвольных неубывающих функциях штрафа, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной ./VP-трудной задачи 1 | rj | /тах и может быть использована в алгоритмах сокращённого перебора.
Для ./VP-трудной задачи 1 ||Tj, когда параметры требований удовлетворяют ограничениям р > р2 >. > рп, d < d, 2 <. < dn, построен псевдополиномиальный алгоритм трудоёмкости 0(n2YlPj) операций.
Предложена графическая реализация метода динамического программирования, на основе которой построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.
Теоретическая и практическая значимость.
Предложенные подходы могут быть использованы для разработки алгоритмов решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть полезны специалистам занимающимися проблемами дискретной оптимизации.
Структура и обзор результатов диссертации.
В разделе 1.1 первой главы рассматриваются постановки задач минимизации максимального временного смещения (Lmax), дан краткий исторический обзор задач, приведены основные результаты, существующие в литературе. В разделе 1.2 вводятся обозначения и определения, которые используются далее в работе. В разделе 1.3 формулируется и доказывается теорема об абсолютной погрешности [28].
Теорема 0.1 Пусть А= {G,(rf, pf, df) j eN}uB = {G, (rf, pf, df) j €.
N} (с идентичным графом предшествования G) — два примера NP-трудной задачи Р prec, rj | Ьтгх, тогда.
LAmax (*B)-L^A).
Рг (А, В) = ma xjeN{rf — rf} - minjeN{rf — rf}, Pd{A, В) = maxjeN{df — df} - minjeN{df — df}, pP (AB) = j: jeNpf-pf.
Мы можем использовать оптимальное расписание примера В для решения исходного примера А. Если пример В принадлежит некоторому полино-миально/псевдополиномиально разрешимому подмножеству примеров, то необходимо найти такой пример из этого подмножества, до которого расстояние р (А, В) было бы минимальным. Искомое оптимальное значение будет принадлежать интервалу ах (тгл)? [L^J8) ~ р (Л, В), LiJjtB)].
Рассмотрим полиномиалыю/псевдополиномиальпо разрешимый случай исходной задачи, когда параметры требований удовлетворяют к линейно независимым неравенствам.
XR + YP + ZD <Н, где R = (rh., rn) T, Р = (.ph., pn) T, D = (dh., dn) T, и X, Y, Z — матрицы размерности к х п, a, Н = (h,., hk) T — fc-мерный вектор (верхний индекс Т обозначает операцию транспонирования). Затем в этом классе примеров находим пример В с минимальным расстоянием р (А, В) до исходного примера А, решая следующую задачу xd — yd + xr — yr) + Y^jeN xPj —> min yd < dfdf < xd, j = l,., n, Уг < rf — rf < rf, j = l,., n,.
XRB + YPB + ZDB < H. Задача линейного программирования с Sn + 4 + п переменными {rf, pf, df, j = l,., n, u xd, yd, xr, уг, и rf, j = 1,., n) и 7 n + k неравенствами иногда может быть решена за полиномиальное (от п) операций, учитывая специфику ограничений задачи. Для всех известных полиномиаль-но/псевдополиномиально разрешимых случаев задачи Р | prec^rj | Lmax количество ограничений к = 0(п).
Рассмотрим совокупность примеров задачи Рргес, Г{Ьтах с количеством требований п, количеством приборов т и ориентированным графом предшествования G. Данная совокупность примеров образует Зп-мерное линейное пространство (3п параметров: Tj, pj, dj, j = 1, п). Два примера, А = {G, (rf, pf, df) j? N} и В = {G, (:rf, pf, df) j G N] будем называть эквивалентными, если существуют константы с? и г, что df = df + d, rf — rf+r, pf = pf, VE N. Полученное семейство классов эквивалентности является (3п — 2)-мерным линейным пространством, которое обозначим через Сп. Будем говорить, что пример, А принадлежит классу Сп, если выполняется условие r = d = 0. Несложно показать, что у эквивалентных примеров совпадают множества оптимальных расписаний. На пространстве классов эквивалеитности примеров рассмотрим следующий функционал.
VA е Сп, <�р (А) = maxrf — minrf + max df — min df + V pf > °< v ' jeN 3 jeN 3 jeN J jeN 3 ^ 3 jGiv.
Данный функционал удовлетворяет трём свойствам нормы: р (А) = 0 Л = 0] <�р (аА) = a.
< <�р (А) + <�р (В).
Таким образом, Сп является (3п — 2)-мерным линейным нормированным пространством с нормой ЦАЦ = <�р (А).
Теорема 0.2 [28] Функция р (А, В) = \А — ВЦ удовлетворяет свойствам нормированной метрики в (3п — 2)-мерном линейном пространстве параметров требований {{fj, Pj, dj) j Е N}.
В случае, когда для исходной задачи нет полиномиально и псевдополиноми-ально разрешимых выделенных подслучаев задачи (в скобках заметим, что тривиальные подслучаи задачи обычно не позволяют найти качественно новые оценки абсолютной погрешности), либо «расстояние» р (А, С) до любого полиномиально/псевдополиномиально разрешимого примера С «слишком велико», тогда можно использовать следующую теорему.
Теорема 0.3 Пусть, А = {G, (rf, pf, df) j tN}uB = {G, {rf, pf, df) j 6 N} (с идентичным графом предшествования G) два примера, тогда для любого приближённого расписания 7f верно.
0 < LiJW) — liaI (nA) < 5B (W) + р (А, В), где 5 В (ж) = LBaI (lf) — !&,(**).
Предлагается общая схема приближённого решения задач минимизации Lmax. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение, с минимальным расстоянием до исходного примера в введённой метрике.
Во второй главе представлены новые полиномиально и псевдополино-миально разрешимые случаи iVF-трудной в сильном смысле задачи lrjLmax.
В разделе 2.1 рассмотрен случай [23, 27, 47], когда параметры требований удовлетворяют следующим ограничениям: di<.. > dn — rn — pn.
Данным ограничениям соответствует случай, когда dj = rj + pj + z, j = 1, —, n, где z — константа, т. е. когда все требования имеют одинаковый запас времени до своего директивного срока. Алгоритмом [27] за 0{пъ log п) операций может быть найдено Парето-оптимальное множество (по критериям Lmax и Стах), состоящее не более чем из п расписаний, решение общей двукритериальной задачи l|r,-|L maxi Стпах ¦
Теорема 0.4 [46, 4^} Для любого примера, А задачи 1 | rj | Lmax, не принадлежащего исследуемому классу, и для любого примера С, наследующего длительности обслуоюивания примера, А и принадлежащего данному классу, справедлива оценка расстояния между, А и С: р (А, С) > pL (A) = maxmin{df — df, (df — rf — pf) — (df — rf — pf)}. i, j? N J j j j.
Оценка достигается на некотором примере С, который может быть найден за время O (nlogn).
Кроме того, был рассмотрен полиномиально разрешимый случай Хоге-вена [126]: maXk? N{dk~rk—Pk} < dj — rj, Vj € N. Оптимальное расписание находится за 0(п2 log п) операций.
Теорема 0.5 Для любого примера, А задачи 1|rjLmax, не принадлежащего классу Хогевена, и для любого примера С, наследующего длительности обслуживания примера, А и принадлежащего классу Хогевена, справедлива оценка расстояния между, А и С: р (А, С) > рн (А) = max{j/ - rf — pf — df + rf}. ijGiv.
Оценка достигается на некотором примере С, который может быть найден за время 0(п).
Для более сложного iVP-трудного подслучая задачи lrjLmax, когда параметры требований удовлетворяют ограничениям: d < с?2 < • ¦ • < dnri>r2>.>rn].
Tj, pj, dj е 6 N, предлагается псевдополиномиальный алгоритм решения [52, 55] трудоёмкоп сти 0(п2Р+пртахР) операций, где Р = max{rmax, + Е Pj-max{rmin, t}, j=l rmax = maxr,-, rmin = minr,-, pm3X = maxpj, a tмомент времени, с которого jeN jeN jeN прибор готов начать обслуживать требования множества N.
Для получения нижних оценок целевой функции был также использован следующий подход. Рассмотрим общую постановку А^Р-трудной задачи.
Д* = min тах4(С^(тг)), ттеп (лг) k=, п где fjk (Cjk (7г)) — произвольные неубывающие функции штрафа. Решим задачу нахождения величины v* v* = max min /, v (C7-.(тг)). k=T-H тгепсN) JJkK JkK.
Теорема 0.6 [18, 23] Для NP-трудной задачи 1|г—|/тах с произвольными неубывающими функциями штрафа fj{t), Vj? N, верно v* < ц* и величина и* может быть найдена за 0(п?) операций.
Третья глава диссертации посвящена алгоритмам оптимального решения задачи 1 | | Ьтгх. В разделе 3.1 рассмотрены существующие подходы к решению задачи, такие как алгоритм Карлье [98] и метод программирования в ограничениях [81] (ПвО). Данный метод близок к методу ветвей и границ. Отличие заключается в том, что для сокращения перебора в ПвО используется пропагация ограничений, которая удаляет несовместимые значения из множеств допустимых значений переменных.
В разделе 3.2 предлагаются два алгоритма оптимального решения задачи 1 | rj | Lmax. Первый алгоритм построен по методу ПвО. На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенное нами правило ветвления, основанное на следующей теореме.
Теорема 0.7 Пусть построено расписание Шраге [185] па и требования пронумерованы в том порядке, в котором они упорядочены в ка. Пусть Ь? N — наименьший номер, для которого Ьь (па) = Lmax (i:(T), и, а € Nнаибольший такой номер, что, а <Ь и.
СаЮРа — min rj < Lb{7Ta) — UB, a< Ьтах (тга), UB — верхняя оценка оптимального решения. Примем S = {а,., Ь}, тогда:
• если не существует такого требования с? S, что dc > db, то не существует расписания с Lmax меньшим, чем UB;
• если с? S — последнее требование с директивным сроком dc > db, то в любом расписании к', что Lmax (it') < UB, выполняется либо (с -" J) n', либо (J —"¦ где J = {с + 1,., Ь}.
Второй алгоритм построен по методу ветвей и границ. В алгоритме также используется правило ветвления, основанное на теореме 0.7. Отличительной особенностью алгоритма является использование алгоритмов ПвО на каждом узле дерева поиска.
В разделе 3.3 приводятся результаты экспериментального сравнения точных алгоритмов решения задачи 1 | rj j Lmax, предложенных в работе, и подходов, существующих в литературе.
В разделе 3.4 рассматривается вариант распознавания задачи 1 | ry | Lmax. Назовем расписание 7 г допустимым по отношению к константе I/, если Lmax (n) < L'. Множество требований S допустимо по отношению к константе L', если существует допустимое расписание 7 Г G П (5), и недопустимо, если не существует такого расписания. В рассматриваемом варианте задачи требуется определить допустимо ли множество требований N по отношению к заданной константе V. Если N допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти как можно меньшее недопустимое подмножество требований из множества N. Для данного варианта задачи предлагается алгоритм, который является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований S С N, не обязательно минимальное, когда множество требование N недопустимо. В тоже время, алгоритм точно определяет, допустимо ли множество требование N. Правило ветвления алгоритма основано на следующей теореме.
Теорема 0.8 Пусть Ьтах (ка) > L' и требования пронумерованы в том порядке, в котором они упорядочены в 7га, Ь G N — наименьший номер, для которого Ьь (ла) > 11, и, а G N — наибольший номер, что, а <Ь и.
Са (па) — Раmin Tj < Lbtf) — L', jes где S = {а,., b}. Тогда:
• если не существует такого требования с Е S, что dc > db, то множество требований S недопустимо по отношению к L';
• если с G S — последнее требование с директивным сроком dc > db, и существует допустимое расписание тг', то выполняется либо (с —> J) ni, либо (J -> c) ni, где J = {с + 1,., Ь].
Отличительной чертой модифицированного алгоритма Карлье является способ построения недопустимого подмножества требований в случае, если алгоритм не нашёл допустимого расписания. На каждом узле дерева поиска, где не происходит ветвления, согласно теореме 0.8, мы располагаем подмножеством S, недопустимым для задачи с текущими параметрами требований. Данное подмножество «передаётся родительскому» узлу дерева поиска. Способ построения недопустимого подмножества для узла, имеющего «дочерние» узлы, обоснован в теореме.
Теорема 0.9 Пусть при любом допустимом расписании тг'? n (iV) требование с? N обслуживается до или после всех требований множества J С N, S' С N — недопустимое множество требований, когда (с —> J a S" С N — недопустимое подмножество, когда (J —> с) ж/. Тогда:
• если с? S' (с? S"), то мноэюество S' (S") недопустимо;
• если с € 5' и с G S", то множество S = J U S' U S" недопустимо.
В четвёртой главе диссертации предлагается точный алгоритм решения задачи 1 | rj | Алгоритм построен по «гибридному» методу [14], который представлен в разделе 4.1.
В последующих разделах задача 1 rj формулируется как задача целочисленного линейного программирования (ЦЛП) и решается методом отсечения и ветвления. Пусть булева переменная Xj принимает значение 1, если требование j? N обслуживается вовремя и 0 — если требование j? N запаздывает.
Wj (1 — Xj) —> min jeN.
J Hd{x), disjunctive^), ze{o, i}n.
Ограничение disjunctive^) выполняется тогда и только тогда, когда множество требований J = {j: Xj — 1} может быть обслужено на одном приборе без прерываний и с соблюдением времён поступления и директивных сроков, — релаксация ограничения disjunctive. В разделе 4.4 рассматриваются различные варианты релаксации.
Лемма 0.1 Пусть для двух требований i, j? N выполняется гг- < dj. Если вектор х удовлетворяет ограничению disjunctive, тогда х также удовлетворяет ограничению1.
Pmm[dj — п, (pi — т&х{ац, (3ji})+]xt < dj — rf, leN где an = (rf — п)+ и fyi = (d[ - dj)+.
Раздел 4.5 посвящён вопросу проверки на допустимость решения х задачи ЦЛП, а также вопросу построения отсечений в случае недопустимости х. Алгоритм выполняется для множества требований J = {j: Xj = 1}, и в случае его недопустимости находится недопустимое подмножество S С J, для которого строится ограничение.
5> <1*1−1jeS.
Следующее утверждение представляет отсечения второго вида.
1 (*)+ = {Zlol- (*) — = {- W = (*)+ + (*).
Лемма 0.2 Пусть заданы такие множество требований О, С N и требование к? N что к может быть обслужено только с момента времени rf, rf > rk, если все требования из Q выполняются вовремя. Положим такэюе afk = (г? — п)+. Тогда вектор х, удовлетворяющий ограничению disjunctive, удовлетворяет неравенству.
Е min [dj ~ (Pi ~ max{a$, M)+] xl+ ieNn{k} pk — Pjk)+xk < dj — rf + (rf — rk){ xo), oen для каждого требования j G NQ, dj > rf.
В работе предлагается алгоритм сложности 0(п3) операций, который проверяет существование отсечения найденного вида. В разделе 4.6 рассматриваются различные варианты предложенного алгоритма отсечения и ветвления. В заключительном разделе 4.7 представлены результаты экспериментального исследования предложенного алгоритма на множестве общедоступных тестовых примеров. Показанно, что разработанный алгоритм для задачи 1 | rj является более эффективным, чем лучший алгоритм для данной задачи, существующий в литературе [173].
В пятой главе рассматриваются комбинаторные свойства NP-трудной в обычном смысле [110] задачи минимизации суммарного запаздывания для одного прибора 1 11Tj. Получены свойства оптимальных расписаний, на основе которых построены алгоритмы решения задачи. Построены оценки оптимального значения целевой функции. В разделе 5.1 приводится постановка рассматриваемой задачи, вводятся необходимые понятия и определения.
В разделе 5.2 приводятся алгоритмы решения рассматриваемой задачи, основанные на «декомпозиционных» свойствах задачи. Одно из первых «декомпозиционных» свойств задачи было получено Лоулером, который предложил алгоритм решения задачи трудоёмкости 0(n4J2Pj) операций [145].
Перенумеруем требования множества N в порядке неубывания директивных сроков d <. < dn (при этом, если dj = dj+i, то pj < pj+i, j = 1,2,., n — 1). Пусть j* будет требованием с максимальной продолжительностью (если таких требований несколько, то выберем требование с наибольшим номером), т. е. j* = max{j G N: pj = maxpf}. Пусть ieN.
Sk = to + к = 1,2,., n, и S = Sn.
Через L (I) обозначим множество индексов к > j*, для которых выполнены неравенства dj +pj < Sk {j = j* + 1,., к) и Sk < dk+i, доопределив dn+1 := +oo. Множество L (I) будем называть миоэюеством подходящих позиций для требования j*.
Теорема 0.10 [25] Для любого примера I множество подходящих позиций L (I) для требования j* не пусто и существует оптимальное расписание 7г* G П*(/), при котором требование j* обслуживается на месте к G L (I). При этом для подходящего места к выполняется.
U Лдля j G {1,2, .,&} {j*} и (j* для j? {к + 1,., п}.
Идея алгоритма решения произвольного примера задачи с помощью «декомпозиционных» свойств (алгоритм А) основана на обходе дерева подпри-меров «в глубину» с использованием рекурсивного вызова процедуры декомпозиции примеров на подпримеры. Если в двух различных вершинах дерева подпримеров будет находиться один и тот же подпример (одинаковы множества требований и моменты начала обслуживания), то алгоритм, А построит оптимальное расписание для данного подпримера дважды. Чтобы избежать этого недостатка, предлагается использовать алгоритм SB А, процесс выполнения которого разбивается на два этапа. На первом этапе осуществляется «разбиение» исходного примера вплоть до получения под-примеров из одного требования. Список подпримеров организован как хэш-таблица. Значение хэш-функции, соответствующее подпримеру, вычисляется с использованием момента начала обслуживания требований данного примера. На втором этапе осуществляется «сборка» оптимального расписания на основе построенного списка подпримеров. В заключение раздела приводятся результаты экспериментального сравнения работы алгоритмов, А и SB А.
В разделе 5.3 рассматриваются свойства оптимальных расписаний и предлагается алгоритм решения примеров I в случае, когда при любом расписании тг Е П (/) запаздывает одно и тоже количество требований т (О < т < п). При этом запаздывающие требования упорядочены в конце расписания 7 г (т.е. расписание тг можно представить в виде тг — (щ,^), где подрасписание тг2 содержит все m запаздывающих требований). Через D (7r) обозначим множество запаздывающих требований при расписании 7 г. В рассматриваемом случае верны следующие утверждения.
Лемма 0.3 При любом оптимальном расписании тг* требования множества D (i{*) обслуживаются в SPT порядке2.
Далее, перенумеруем требования примера I в порядке невозрастания продолжительиостей обслуживания pi > P2 >. > рп, при этом, если Pj = Pj+i (j = 1,., п-1), то dj> dj+i.
Лемма 0.4 Существует оптимальное расписание 7г* такое, что если для некоторого к? N выполняется к Е D[it*), то (j —> к) п* для всех требований j € {к + 1,., п}.
2SPT — Shortest Processing Time. Расписание 7 Г называется SPT-расписанием, если требования упорядочены при расписании 7 Г в порядке неубывания продолжительиостей обслуживания.
Найденные свойства позволяют построить алгоритм нахождения оптимального расписания за 0(п3) операций (алгоритм FA). Построение оптимального расписания алгоритмом FA сводится к обходу дерева, каждая ветка которого соответствует некоторому порядку обслуживания запаздывающих требований.
В разделе 5.4 приводятся две оценки оптимального значения суммарного запаздывания, основанные на свойствах SPT-расписаний. Полученные оценки позволяют найти абсолютную погрешность значения суммарного запаздывания при SPT-расписании3.
Перенумеруем требования множества N в порядке неубывания продол-жителыюстей обслуживания, т. е. pi < <. < рп. SPT-расписание (1,2,., гг) будем обозначать через 7rspt. Рассмотрим пример задачи / = ({pj, dj}jeN, to) с оптимальным значением целевой функции F*(I). Пусть dmin — minjGj/v dj и dmax = тах—едг dj. Выберем величины С и 5 такими, что dmin <с < dmax и 5 = max{dmax — С, С — dm-m}. Рассмотрим пример V — ({pj, d’j = Cjj’eiVj ^о).
Теорема 0.11 (первая оценка). Для выбранных значений С и 5 верно неравенство.
FI)~FI').
Для формулировки второй оценки рассмотрим функцию п j j=1 i=1.
Значение этой функции в точке t равно оптимальному значению суммарного запаздывания для параметрического примера I (t) = ({pj, to), при.
3 Относительная погрешность значения суммарного запаздывания при EDD-расписаиии (расписании, требования при котором упорядочены в порядке невозрастания значений директивных сроков) установлена Лоулером в 1977 г. котором директивные сроки всех требований равны t. Функция / является кусочно-линейной, невозрастающей, непрерывной и неотрицательной функцией, принимающей значения 0 для всех t > to + YljeNPj.
Теорема 0.12 (вторая оценка) Для любого примера I справедливы неравенства f (dmax) < F*(I) < /(4iin).
Раздел 5.5 посвящён результатам экспериментальных исследований задачи.
В диссертационной работе применяется новая методика проведения экспериментов. В б—окрестности произвольно выбранной начальной точки (примера) xi находим точку с большей трудоёмкостью (количеством ветвлений в дереве поиска) х^. Затем в окрестности точки Х2 ищем «более сложную» точку и т. д. Процесс останавливается, когда не удаётся найти «более сложную» точку. Замечен интересный факт: для всех построенных алгоритмов «предельные сложные» точки взаимноортогональны.
В шестой главе диссертации рассматривается частный iVP-трудный случай [6] задачи минимизации суммарного запаздывания.
Р1>Р2>—->Рп, d < d2 <. < dn.
Предлагается подход решения задачи в этом случае, при котором исходное множество требований N разбивается на к таких непересекающихся подмножеств Ml, М2, • • •, Mt, ЧТО iV = Ml U М2 и • • • U «Мк И тах^етИа |d{-dj| < minj? MaPji аг = 1,., к, а затем на основе этого разбиения строится оптимальное расписание.
В разделе 6.1 формулируется и доказываются две леммы, отражающие свойства оптимальных расписаний для исследуемого случая.
Лемма 0.5 Существует оптимальное расписание к*, при котором выполняется либо (к —> i)^*, либо (j —"• к) п* для любой тройки требований i, j, k Е N, что d{ — dj < min{pi, pj}, к < mm{i, j} и (i -)•.
Лемма 0.6 Существует оптимальное расписание 7Г*- при котором выполняется либо (к —" j) t*, либо ((к + 1) к) п* для любой пары требований к, j? N, к < j.
На первом этапе решения задачи производится разбиение множества требований N па непересекающиеся подмножества М, М.2, • • • ,-Мк, такие, что разность между максимальным и минимальным директивными сроками требований каждого подмножества не превышает величины минимальной продолжительности требований из этого подмножества4.
Определим параметрический пример Ik (t) = {{pj, dj (t)}je^k, 0), где = {k, k+l,., n} и dj (t) = dj—dn-{-t—tQ. Ik (t) — это пример исследуемой задачи обслуживания требований множества с моментом начала обслуживания равным нулю и директивными сроками dj (t), линейно зависящими от параметра t.
Идея предлагаемого подхода заключается в построении оптимальных расписаний 7для примеров Ih{t), к = тг, п — 1,., 1, для всех целочисленных точек t Е [to] й? п]. Расписания !(?) строятся на основе построенных на предыдущих шагах расписаний I > k, t' Е tQd^[.
Согласно леммам, при построении оптимального расписания для исходного примера I можно исключить из рассмотрения все расписания 7 Г, при которых: a) (г Чк -> к < min{i, j}, i, j Е Ма, к Е Мр,(3 < аb) (jк (к + 1)), к < j.
4 Такое разбиение множества требований может быть выполнено за 0(тг) операций.
В разделе 6.3 рассматривается случай к = 1, когда параметры требований удовлетворяют условиям:
Р > Р2 > • • • > Рп di < d-2 <. < dn] k dn-di< pn.
В этом случае при построении оптимального расписания тгl (t) с помощью описанного выше подхода для каждой точки t требуется просмотреть только две позиции для требования к: до всех требований множества Nk+1 и после всех требований этого множества. При обслуживании требования к до всех требований множества Nk+1 получаем расписание (k, irl+1(t — рк)), после всех требований — расписание к). Расписание с наименьшим значением суммарного запаздывания среди двух полученных расписаний будет оптимальным расписанием для примера h{t) — Алгоритм, реализующий данный подход к построению расписания в этом случае, мы назвали алгоритмом В-1.
Теорема 0.13 Алгоритм В-1 находит оптимальное расписание для данного NP-трудного случая за 0(nJ2Pj) операций.
В разделе 6.4 рассматривается случай для произвольного значения к. Приводится описание алгоритма В-к нахождения оптимального расписания в случае (6.1), трудоёмкость алгоритма 0(knJ2Pj) операций.
В разделе 6.5 рассматриваются примеры, параметры требований которых удовлетворяют условиям: d< dn — di < 1;
Алгоритм C-l находит оптимальное расписание для данного случая за 0(п2) операций. Отметим, что алгоритм можно использовать для решения примеров в случае, когда в условиях второе неравенство заменено на dn — d < НОД (pi,. ., рп).
В разделе 6.6 рассматриваются примеры, параметры требований которых удовлетворяют условиям dj ~ dj-1 > Pj, j = 2,3,., п.
Поскольку pj > 0, /j? N, то выполняется d <. < dn. Отметим, что этот случай является «предельным» подслучаем, когда количество подмножеств к = п, т. е. каждое подмножество Ма, а = 1,., к, состоит ровно из одного требования.
Показано, что для данного случая задачи существует оптимальное расписание 7г*? П*(/), при котором требование j* обслуживается на первой позиции из множества L (I). Данное свойство позволяет построить алгоритм В-п решения задачи трудоёмкости 0(п2) операций.
В разделе 6.7 построен алгоритм трудоёмкости 0(п3) операций для случая:
Pi < Р2 < - ¦ ¦ < Рп, k Pi + d < Р2 + d2 <. • • < Р2 +.
В седьмой главе диссертации исследуются свойства алгоритма В-1, показано, что данный алгоритм может быть использован для нахождения решения следующих iVP-полных задач разбиения: РАЗБИЕНИЕ, ЧЕТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ (ЧНР), ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ (ОЧНР).
Расписание тг назовем расписанием, обладающим свойством В-1, если для всех требований к? {1,2,., п — 1} при расписании тг выполняется либо (к -4- j) n, либо (j к) ж для всех j? {к + 1,., п}.
Множество всех расписаний, обладающих свойством В-1 для примера 7, будем обозначать через Ub-i (I) — Пусть = р| П*(/).
Теорема 0.14 Алгоритм В-1 находит оптимальное расписание примера I задачи 1 ||Tj тогда и только тогда, когда П^.^/) ф 0.
Раздел 7.2 посвящён классической iVP-полной задаче РАЗБИЕНИЕ, рассматривается схема полиномиального сведения примеров этой задачи к примерам задачи теории расписаний 1 11 ^Ту.
В классической задаче РАЗБИЕНИЕ требуется определить, существует ли такое разбиение множества п целых положительных чисел на два подмножества, что суммы чисел в обоих подмножествах равны. Задача ЧНР представляет собой модификацию задачи РАЗБИЕНИЕ, когда на разбиение множества накладывается ограничение, что соседние числа (первое и второе, третье и четвертое и т. д.) должны оказаться в разных подмножествах. Задача ОЧНР представляет собой задачу ЧНР с дополнительными ограничениями на значения чисел исходного множества.
Показано, что любое (в том числе, и оптимальное) расписание канонического вида обладает свойством В-1. Таким образом, мы можем использовать алгоритм В-1 для нахождения решения канонических примеров задачи 1 11? Tj и, соответственно, задач РАЗБИЕНИЕ, ЧНР, ОЧНР. С учётом особенностей канонических примеров предложен алгоритм В-1 -канонический, трудоёмкость которого не хуже известного алгоритма из книги Гэри и Джонсона [7] для задачи РАЗБИЕНИЕ.
В разделе 7.3 приводится модификация алгоритма В-1, которая позволяет снизить трудоёмкость решения примеров задачи 1 11Tj. Идея алгоритма В-1-модифицированный заключается в том, что процесс построения оптимального расписания сведён к процессу построения кусочно-линейной функции специального вида. Рассматриваются три операции над функциями: «сдвиг» функции, сложение двух функций и нахождение функции минимума двух функций. Полученные свойства рассматриваемых функций были использованы для построения алгоритма В-1-модифицированный. Преимущество этого алгоритма заключается в том, что при построении решения нет необходимости рассматривать все целочисленные точки интервала t 6 [^0) driТрудоёмкость решения полиномиально зависит от максимального количества точек изменения наклона функций, рассматриваемых в ходе решения. Преимуществом Алгоритма В-1-модифицированный является то, что при масштабировании всех параметров примера, трудоёмкость алгоритма решения не меняется. Также данный алгоритм может быть использован для решения задач 1 11 РАЗБИЕНИЕ, ЧНР и 04-НР с нецелочисленными параметрами.
В восьмой главе рассматривается графическая реализация метода динамического программирования на примерах решения задач РАЗБИЕНИЕ и РАНЕЦ. Проведён сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач.
Задача РАЗБИЕНИЕ. Задано упорядоченное множество из п положительных целых чисел В = {&i, &2> • • • > К}, > h > ¦ •. > Ьп. Требуется разбить множество В, на два подмножества В и В2, В\}В2 = В, В[В2 = 0, так, чтобы минимизировать значение:
I ]Сbi ~ S Ь{ —> min' bjG-Bi he В2.
Задача об одномерном РАНЦЕ. f (x) = E" =l °iXi -> тах.
Ег=1 aiXi — k Xi € {0,1}, г = 1,., n.
Когда С{ = a, i = bi, i = 1,2, ., п, и, А = Т0 данные задачи являются эквивалентными.
В разделе 8.1 представлен графический алгоритм для решения задачи РАЗБИЕНИЕ. В алгоритме последовательно на шаге, а = 1,2, ., п рассматриваются следующие функции:
2(*) = l Е *}- Е МbjeB^t-ba) bjeB2{t-ba) т= е Е чbjeB^t+ba) bjeB2(t+ba) На каждом шаге, а алгоритма B (t) JB2(t) = {b, 62, — - -, ba-i}> Последовательно «добавляется» очередное число Ьа, где, а = 1,2,., п, в множество B{t) или ^(ОВ каждой точке t «добавление» числа Ьа выбирается таким образом, чтобы минимизировать значение функции | Yb^B^t) + t ~ Еь^вд bjIHa очередном шаге, а из функции Fai (t) = | Еь^ВД bj ~ Ylbj< F2{t), то B^t) = B^t — ba){J{ba}, иначе B2(t) = ^(i + 6a) (J{6a). Кусочно-линейную функцию Fa (t) можно представить (и хранить) в табличном виде по точкам «излома»: ^i", • • •- tma. На промежутке [U —, ^ + fi+12~fi), г = 1,2,., та — 1, кусочно-линейная функция Fa (t) задаётся уравнением Fa (t) = — U, т. е. график функции пересекает ось t в точке t (. Каждому временному интервалу + '+12 ') соответствует некоторое фиксированное разбиение (BiВ2), т. е. Bift1) = ?i (t2) = Вь Vt1,*2 Е [U — + (аналогично и для Пусть на предыдущем шаге, а — 1 получена функция.
Fa-i (t), заданная таблично. На шаге, а мы рассматриваем две функции Fai (i — ba) и Fa-i (t + ba), заданные двумя таблицами в точках «излома»: к — ba, ii — ba,. — U — ba, ., ?max — ba иo + h + ba, ¦ • ¦, U + ba, .,.
В разделе 8.2 показано сокращение рассматриваемых интервалов. Учитывая, что на шаге п нам требуется вычислить значение целевой функции и найти разбиение лишь в точке t — 0, то на шаге п — 1 нам достаточно рассчитать значения в точках t е [—Ьп, Ьп]. Аналогично на шаге п — 2 достаточно рассмотреть интервал [—bn — 6ni, bn + 6ni] и т. д.
Следовательно, на каждом шаге, а достаточно рассматривать интервал [- Л]=а+1 bh Ej=a+1 У > вместо интервала [- bj, EJ= 14.
При построении функции Fa (t) рассматриваются только точки t е [-Е? =a+ibj]- Чтобы интервал сокращался максимально быстро необходимо упорядочить bj по невозрастанию. Учитывая, что функция Fa (t), a = 1,2, ., 7 г, является чётной, поэтому достаточно хранить «половину» таблицы. Кроме того, следует отметить, что при «масштабировании с небольшим изменением параметров» примера, т. е. когда b’j = Kbj + ?j, где |?j| <С К, К— некоторая достаточно большая положительная константа, j = 1,2, ., п, трудоёмкость алгоритма, построенном на методе динамического программирования [1], составит 0(Kn^2bj) операций, в то время как у графического алгоритма трудоёмкость не изменится. Для алгоритма Balsub [133] с трудоёмкостью 0(nbmax) операций такое «масштабирование» примера также приведёт к увеличению трудоёмкости в К раз. Таким образом, графический алгоритм находит решение за одно и тоже количество операций для всех точек некоторого конуса в п—мерном пространстве, если представить параметры примера как точку (61,62,., 6П) в п—мерном пространстве. Причём параметры примера могут быть как отрицательными, так и нецелочисленными.
Существуют классы примеров, для которых трудоёмкость графического алгоритма растёт экспоненциально быстро (от п):
1. В = {6Ь62,. X} = {М, М-1, М-2,., 1,1,., 1}. Мдостаточно большое число, сумма единиц в примере равна М (М + 1)/2, т. е. п = М + М (М + 1)/2;
2. класс нецелочисленных примеров В = {Ь, 62,., Ьп}, если не существует такого набора чисел Aj = ±-1,г = 1 что выполняется ХА + Л262 +. + А пЬп = 0.
В разделе 8.3 представлена графическая реализация метода динамического программирования решения задачи РАНЕЦ. Также как и для задачи РАЗБИЕНИЕ в ранец последовательно «добавляются предметы». На шаге (а+1) строится график g2(t) из графика ga (t) смещением «наверх» на са+1 и «вправо» на аа+. График gl (t) полиостью повторяет график ga{t). Следовательно, чтобы построить да+(t) = max{gl (t), g2(t)} необходимо рассмотреть не более 2та интервалов, образованных точками из множества ftb h, • - • 1 tma, t0 + аа+1, ti + аа+1, ., tma + аа+1}, которые принадлежат интервалу [0, А]. Количество точек не превосходит, А для aЕ Z+, г = 1,., п. Параметры задачи могут быть и отрицательными.
В заключении диссертации перечислены основные результаты работы и намечены пути дальнейших исследований.
Основными результатами диссертации являются следующие:
1. Для iVP-трудных задач {Р, R, Q, F}prec, rj{Lmax, Cmax} найдены оценки абсолютной погрешности целевой функции. Для этих классов задач введена метрика. Предложена новая схема нахождения приближённого решения данных задач, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится изменение исходных параметров примера A {rf, pfi, dfj € N, i € М), что полученный пример В с параметрами требований € N, i € М) принадлежал известному полиномиально/псевдополиномиально разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера, А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния В) между примерами;
2. Для iVP-трудной задачи 1 | rj | Lmax предложен новый точный алгоритм решения на основе методов ветвей и границ и программирования в ограничениях. Найдены новые эффективные нижние оценки оптимального значения целевой функции. Экспериментальное исследования на множестве тестовых примеров показало преимущество (время работы алгоритма и количество ветвлений в дереве поиска существенно меньше) предложенного алгоритма над существующими алгоритмами;
3. Для iVP-трудной задачи 1 | rj | ^ WjUj предложен точный алгоритм отсечения и ветвления. Преимущество (время работы алгоритма и количество ветвлений в дереве поиска) предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами;
4. Поставлена и решена задача, в некотором смысле «двойственная» к задаче 1 | rj | /тах, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной NP-трудной задачи 1 j rj | /тах и может быть использована в алгоритмах сокращённого перебора;
5. Для ТУР-трудной задачи 1 || доказаны новые свойства оптимальных расписаний NP-трудного частного случая, когда параметры требований удовлетворяют ограничениям р > Р2 >. > Pni di < <. < dn, и предложен алгоритм решения этого случая задачи за 0(n2^pj) операций. Выделен один псевдополииомиалыю разрешимый {0(nY^Pj) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая. Получены необходимое и достаточное условия того, что построенный пседополиномиальный алгоритм находит оптимальное решение.
Показано, что любой алгоритм решения задачи 1 || основанный на «декомпозиционных» правилах [201], при решении канонических примеров будет иметь трудоёмкость не менее 0(п22−1) операций;
6. Построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.
Публикации и аппробация результатов исследований.
Основные результаты диссертации опубликованы в следующих 56 работах: [2], [3], [6], [16]—[55], [116], [148]—[161], [183], [184], в том числе, 8 в центральной печати (из списка ВАКа), четырёх книгах, а также в материалах и тезисах международных, всесоюзных и всероссийских конференций.
В совместных работах автору принадлежат в: [2] - разработка приближённого алгоритма решения задачи Pprec, rjCmax- [3] - доказательство полиномиальной разрешимости задачи 1|р- < pj, pi + di < pj + dj^2Tf, [6], [155] - построение канонического примера задачи 1||Tj и полиномиальное сведение к задаче ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ- [31], [32], [46], [50] - компоновка и редактирование текстов- [33]-[42], [116], [156]-[158] - разработка алгоритмов решения задачи 1|[ E^j и методика проведения экспериментов- [43]-[45], [183]-[184] - доказательство утверждений и разработка алгоритмов решения задачи 1г^Ьтах и методика проведения экспериментов- [47], [159] - доказательство теоремы об абсолютной погрешности и разработка схемы приближённого решения задачи 1|rjLmax- [48], [49] -получение нижних оценок решения задачи PrjCmax- [51] - оценка абсолютной погрешности целевой функции задачи 1|г—|?тах при модификации директивных сроков требований- [52]-[55], [160] - разработка алгоритмов решения задачи l|rj|Lmax и выделение полиномиально/псевдополиномиально разрешимых случаев задачи- [115] - графический подход решения задач комбинаторной оптимизации- [161] - получение нижних оценок решения задачи l|rj|.
Результаты диссертации докладывались и обсуждались на: 4-ом международном конгрессе по промышленной и прикладной математике (Эдинбург, Шотландия, 1999 г.) — международных конференциях по оптимизации (Намур, Бельгия, 1998 г., Монтпелье, Франция, 2000 г.) — международных семинарах «Дискретная математика и её приложения» (Москва, МГУ, 2001, 2004, 2007 гг.) — Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004 гг.) — международных семинарах по методам и алгоритмам для задач календарного планирования и теории расписаний MAPSP (Сиена, Италия, 2003, 2005 гг., Стамбул, Турция, 2007 г.) — 3-ей международной конференции «Математические методы и компьютеры в экономике» (Пенза, 1998 г.) — международной школе-семинаре «Методы оптимизации и их применение» (Байкал 1998 г.) — научно-исследовательской конференции «Практика использования мини и микро ЭВМ в ГАП механической обработки» (Казань, 1988 г.) — симпозиуме «Программное обеспечение решения задач оптимального планирования» (Нарва, Эстония, 1988 г.) — конференции «Проблемы теоретической кибернетики» (Иркутск, 1985 г., Казань 2002 г.) — международной конференции по исследованию операций (Карлсруэ, Германия, 2006 г.) — международной конференции по комбинаторной оптимизации ЕССО XVIII (Минск, Беларусь, 2005 г.) — международной конференции ENC'04 (Колима, Мексика, 2004 г.) — IFAC симпозиуме по проблемам контроля в производстве INCOM'2006 (Сент-Этьен, Франция, 2006 г.) — международном семинаре по сложности многомерных задач (Гои-Конг, Китай, 1999 г.) — VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ, 2004 г.) — 9-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1999 г.) — международной конференции по теории расписаний MISTA'07 (Париж, Франция, 2007 г.) — семинарах кафедр прикладной математики и экономической кибернетики Казанского университета (1980;2002 гг.) — семинарах математического департамента CICESE (Энсенада, Мексика, 2004 г.) — семинарах профессора П. Брукера (Осна-брюкский университет, Германия, 2002, 2003 гг.) — семинарах профессора Ф. Баптиста (Эколь Политекник, Полиазье, Франция, 2007 г.) — семинаре отдела «Математических проблем распознавания и методов комбинаторного анализа» Вычислительного центра им. А. А. Дородницына Российской академии наук (Москва, 2007 г.).
Благодарности.
Считаю своим долгом выразить благодарность: B.C. Танаеву, Е. Г. Лазаревой, Ю. И. Журавлёву, В. К. Леонтьеву, И. Х. Сигалу, Ю. А. Флёрову, Л. С. Иртышёвой, К. В. Рудакову, В. Н. Буркову, Д. А. Новикову, С. В. Севастьянову, М. Я. Ковалёву, Я. М. Шафранскому, Ю. Н. Сотскову, Н. Н. Кузюрину, В. В. Шкурбе, А. А. Сапоженко, М. Н. Вялому, С. П. Тарасову, P.P. Садыко-ву, А. Г. Кварацхелия, P.P. Сираеву, Е. Р. Гафарову, С. А. Скиндереву, А. Н. Черных, Я. И. Заботину, О. Н. Шульгиной, А. Ф. Кадомцевой, Р.Ф. Хабибул-лину, А. А. Корбуту, П. Брукеру (Германия), Ф. Баптисте (Франция), В.
РОССИЙСКАЯ. 41.
ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА/.
Шварцу (США) за помощь в работе и обсуждение полученных результатов.
Работа выполнена в рамках научной школы академика Ю. И. Журавлёва (грант НШ-5833.2006.1) при частичной финансовой поддержке фондов: РФФИ (Россия), DAAD (Германия), CNRS (Франция), NSC (США).
Заключение
.
В заключении мы остановимся на основных результатах представленных в данной работе, а также рассмотрим возможные направления для продолжения исследований.
Основными результатами диссертации являются следующие:
1. Для NP-трудных задач {Р, R, Qjjprec, rj{Lmax, Cmax} найдены оценки абсолютной погрешности целевой функции. Для этих классов задач введена метрика. Предложена новая схема нахождения приближённого решения данных задач, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится изменение исходных параметров примера A {rf, pj-, dfj? N, i G M), что полученный пример В с параметрами требований {rf, pfi, dfj e N, ie м) принадлежал известному полиномиально/псевдополиномиально разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера, А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния р (А, В) между примерами;
2. Для iVP-трудной задачи 1 | гj | Lmax предложен новый точный алгоритм решения на основе методов ветвей и границ и программирования в ограничениях. Найдены новые эффективные нижние оценки оптимального значения целевой функции. Экспериментальное исследования на множестве тестовых примеров показало преимущество (время работы алгоритма и количество ветвлений в дереве поиска существенно меньше) предложенного алгоритма над существующими алгоритмами;
3. Для NP-трудной задачи 1 | rj | WjUj предложен точный алгоритм отсечения и ветвления. Преимущество (время работы алгоритма и количество ветвлений в дереве поиска) предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами;
4. Поставлена и решена задача, в некотором смысле «двойственная» к задаче 1 | гj | /тах, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной NP-трудной задачи 1 | rj | /тах и может быть использована в алгоритмах сокращённого перебора;
5. Для jVP-трудной задачи 1 || доказаны новые свойства оптимальных расписаний iVP-трудного частного случая, когда параметры требований удовлетворяют ограничениям р > р2 >. > рп, d < d2 <. < dn, и предложен алгоритм решения этого случая задачи за 0(n2Y, Pj) операций. Выделен один псевдополиномиальпо разрешимый (0(nYPj) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая. Получены необходимое и достаточное условия того, что построенный пседополиномиальный алгоритм находит оптимальное решение.
Показано, что любой алгоритм решения задачи 1 || основанный на «декомпозиционных» правилах, при решении канонических примеров будет иметь трудоёмкость не менее 0(п2?" 1) операций;
6. Построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.
Задача 1 | гj | Ьтах является одной из важных комбинаторных задач теории расписаний. Во-первых, она тесно связана с часто встречающейся задачей теории расписаний состоящей в проверке возможности обслуживания заданного множества требований на одном приборе без прерываний и нарушений времен поступления и директивных сроков требований. Можно вспомнить, например, главу 4 данной работы, где последняя задача играла важную роль.
Во-вторых, как уже было упомянуто, решение задачи 1 | гj | Lmax помогает получить неплохие нижние оценки для многих многоприборных как теоретических так и практических задач.
Смеем надеяться, что данный труд внесет свою лепту в изучение этой важной задачи и предложит новые пути ее исследования. Остановимся теперь на основных результатах.
С помощью теоремы об абсолютной погрешности нами были установлены новые свойства оптимальных расписаний примеров задачи. Было показано, что расписание, оптимальное для одного примера, может быть использовано при приближённом решении с гарантированной погрешностью другого примера задачи. Данное свойство позволило нам предложить целое семейство алгоритмов решения задачи. Следует заметить, что до этого только алгоритм Шраге [185] позволял получить за полиномиальное время решение с гарантированной абсолютной погрешностью (которая равняется максимальному времени обслуживания требования [98]).
Отличительной чертой нашего подхода является то, что в основе каждого приближённого алгоритма лежит алгоритм решения некоторого полиномиально разрешимого частного случая задачи. Здесь необходимо повториться, что, насколько нам известно, подход такого типа для приближённого решения комбинаторной задачи применяется впервые.
Не менее значимым теоретическим результатом можно считать введение метрики в пространстве примеров задачи, что также является новшеством в теории расписаний. В настоящее время продолжается работа над получением метрики для задач теории расписаний с «суммарными» критериями.
Мы надеемся, что полученные теоретические результаты могут быть обобщены, а также перенесены на другие комбинаторные задачи.
Наряду с теоретическими, нами также были получены важные результаты с практической точки зрения. Долгое время считалось, что алгоритм Карлье [98] позволяет справляться со всеми примерами проблемы 1 | rj | Lmax встречающимися на практике. Однако, наше исследование показало, что это не так. Предложенная нами модификация алгоритма Карлье намного более эффективна. Данная модификация заключается в использовании алгоритмов «Edge-Finding «известных в программировании в ограничениях. В отличие от оригинального алгоритма, с помощью его модификации были решены все тестовые примеры.
Несмотря на хорошие результаты, предложенный алгоритм точного решения задачи не всегда работает достаточно быстро (особенно на примерах большой размерности). Обычно задача 1 | т* | Ьтах используется в качестве подзадачи, и поэтому ее требуется решить много раз в течение одного алгоритма. Поэтому, даже если каждый пример решается за считанные секунды, это может быть недостаточно эффективно.
Задача 1 | г j YjwjUj интересна как в теоретическом так и в практическом плане. Минимизация запаздывающих требований — один из классических критериев в теории расписаний. Этот факт обусловлен большим количеством задач с данной целевой функцией, встречающихся на практике. Наибольший интерес представляют многоприборные задачи. Однако, вариант с одним прибором, рассмотренные в работе, так же важен, так как идеи и подходы для его решения зачастую могут быть обобщены на задачи с несколькими как идентичными так и неоднородными приборами.
Задача 1 j rj | Y, WjUj может быть переформулирована как нахождение допустимого множества требований максимального суммарного веса. Здесь допустимость множества определяется возможностью обслуживания его требований на одном приборе без прерываний и нарушений времен поступления и директивных сроков. Для оптимального решения данной задачи нами был предложен алгоритм ветвей и отсечений основанный на декомпозиции Бендерса формулировки целочисленного линейного программирования. Декомпозиция разбивает задачу на две подзадачи — выбор множества требований и проверку его допустимости. Первая подзадача решается методами целочисленного линейного программирования, для второй используются специализированные комбинаторные алгоритмы и методы программирования в ограничениях. Связь между двумя подзадачами осуществляется при помощи отсечений, генерируемых второй подзадачей и используемых в первой.
Идея такой декомпозиции задачи теории расписаний не нова, см. например [87,130]. Наш вклад в данный подход состоит в следующем. Во-первых, мы предложили дополнить формулировку первой подзадачи ограничениями, которые существенно сокращают число выбранных недопустимых множеств требований. Это позволило также сократить число генерируемых отсечений и, соответственно, время работы алгоритма. Во-вторых, нами были разработаны новые алгоритмы для генерации отсечений. Стандартный метод состоит в генерации так называемых «no-good» отсечений, которые гарантируют, что все требования недопустимого множества требований не могут быть выбраны одновременно. Наш первый алгоритм основан на идее о том, что, когда некоторое множество требований недопустимо, обычно можно найти недопустимое подмножество требований из данного множества. Отсечение «no-good» для подмножества требований «работает» более эффективно. Одно такое отсечение может заменить много стандартных отсечений «no-good», тем самым значительно уменьшая время работы алгоритма. Наш второй алгоритм для генерации отсечений использует новую технику «Edge-Finding», уже упомянутую выше. Данная техника позволяет находить пары (Q, k), где Q — множество требований, и к — некоторое требование. Если требование из множества Q U {к} обслуживается на одном приборе в допустимом расписании, к может обслуживаться только в определенном интервале, меньшим, чем интервал [гк, с1к]. Использую пары (Q, к), дополнительные ограничения могут быть добавлены в формулировку первой подзадачи. Так как число таких ограничений экспоненциально, они используются как отсечения.
С помощью предложенного алгоритма ветвей и отсечений были решены все тестовые примеры содержащие до 100 требований. По нашим сведениям, это наилучший результат среди всех алгоритмов существующих в литературе.
При анализе предложенного алгоритма возникает важный вопрос касающийся отсечений «no-good». Возможно ли построить достаточно эффективный на практике алгоритм, который, при заданном недопустимом множестве требований, находил минимально недопустимое подмножество. Такое подмножество требований позволило бы нам сгенерировать наиболее эффективное отсечение «no-good» (т.е. ограничение которое наряду с заданным решением «отсекает» наибольшее число недопустимых решений задачи).
В алгоритме ветвей и отсечений не были использованы правила доминирования задачи. Интересно было бы оценить эффект данных правил на работу алгоритма. Особенно полезными могли бы быть правила, которые могут быть выражены переменными х, например «если требование j обслуживается вовремя, то и требование г тоже должно обслуживаться вовремя» .
Еще одним направлением для исследования может быть поиск других семейств отсечений и ограничений, которые могут быть использованы при решении первой подзадачи. Однако, наиболее важным нам представляется изучение возможности применения использованной схемы декомпозиции для решения практических задач.
Важным, на наш взгляд, является то, что для NP-трудного случая задачи 1 11Tj, когда параметры требований удовлетворяют ограничениям:
Pi > Р2 > • • • > Vn d < d>2 <. < dn, построен псевдополиномиальный алгоритм трудоёмкости 0(n2^2pj) операций. На основе идеи (названный нами В — 1 подход) и метода динамического программирования был построен графический алгоритм решения задач РАЗБИЕНИЕ и РАНЕЦ, позволяющий решать эти задачи не хуже, чем существующие алгоритмы их решения. Одним из преимуществ предложенного алгоритма является то, что параметры задач могут быть как нецелочисленными, так и отрицательными. Мы планируем применить предложенный подход и для других задач комбинаторной оптимизации.