Содержание к диссертации
Введение
1 Полиномиальные алгоритмы решения задачи 12
1.1 Постановка задачи 13
1.2 Обозначения и определения основных понятий 15
1.3 Абсолютная погрешность приближенного решения 17
1.4 Схема нахождения приближенного решения 22
1.4.1 Вариант схемы на основе случая Лазарева 25
1.4.2 Вариант схемы на основе случая Хогевена 32
1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи 36
1.5.1 Способ генерации примеров 37
1.5.2 Оценка практического значения абсолютной погрешности 40
1.5.3 Эффективность применения полиномиальных алгоритмов для общего случая задачи 42
2 Алгоритмы оптимального решения задачи 46
2.1 Существующие методы решения задачи 48
2.1.1 Алгоритм Карлье 48
2.1.2 Метод программирования в ограничениях 53
2.2 Алгоритмы решения задачи 59
2.3 Экспериментальное сравнение алгоритмов решения задачи 65
2.4 Модифицированный алгоритм Карлье 71
3 Алгоритм ветвей и отсечений для решения задачи 80
3.1 "Гибридная" схема решения одного класса задач целочисленного линейного программирования 81
3.2 Постановка задачи 89
3.3 Формулировка задачи как задачи 91
3.4 Дополнительные ограничения 94
3.5 Генерация отсечений 98
3.6 "Гибридный" алгоритм ветвей и отсечений 109
3.7 Экспериментальная оценка эффективности 111
Заключение 119
Список литературы 121
- Обозначения и определения основных понятий
- Экспериментальное исследование полиномиальных алгоритмов решения задачи
- Метод программирования в ограничениях
- Формулировка задачи как задачи
Введение к работе
Общее направление исследований
В наше время люди все чаще и чаще сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Например, мы обычно планируем наши действия в порядке возрастания крайних сроков их исполнения. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно.
Однако, когда дело касается большого производства, целесообразным является использование настолько хороших расписаний, насколько это возможно. Улучшение расписания даже на несколько процентов может дать существенную экономию. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом все более и более трудные задачи составления расписаний.
Данное направление в науке, получившее название "теория расписаний", берет свое начало в 50-е годы 20-го века. Одними из первых работ по теории расписаний считаются труды Джонсона (Johnson [53]), Джексона (Jackson [50]) и Смита (Smith [79]).
Изначально одними из главных вопросов нового направления были классификация задач и установление их сложности. Считающаяся стандартной и по нынешний день классификация задач теории расписаний была предло жена Грэхэмом и др. (Graham at al. [45]). Относительно быстро была установлена сложность большого числа задач. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона (Garey, Johnson [1]), Ленстры и др. (Lenstra et al. [62]), Лоулера и др. (Lawler et al. [59]), Танаева и др. [17, 18], Брукера (Brucker [36]).
Отметим, что подавляющее большинство задач теории расписаний являются ЛФ-трудными. Несмотря на это, практика требует решение таких задач. Для этого существует несколько подходов.
Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближенными [6, 16]. Существуют приближенные алгоритмы, гарантирующие как относительную погрешность [2, 76], так и абсолютную погрешность [14]. Некоторые iVP-трудные задачи допускают существование так называемой аппроксимационной схемы. В рамках данной схемы можно найти решение с относительной погрешностью не более любого заданного значения є 0 за время, полиномиально зависящее от І/є. Для задач теории расписаний такие схемы разработали, например, Ковалев [3], Алон и др. (Alon et al. [23]), Мастролилли (Mastrolilli [64]), Севастьянов и Вёгин-гер (Sevastianov,Woeginger [77]. Для задач, не имеющих аппроксимационной схемы, большое значение имеет установление предельного значения є, для которого возможно нахождения -приближенного алгоритма за полиномиальное время.
В настоящий момент широкое распространение имеют метаэвристиче-ские алгоритмы (еще их называют алгоритмами "локального поиска"), которые находят решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. То есть неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Точным методам решения iVP-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение получили методы сокращения перебора, также называемые методами ветвей и границ [4,15, 35, 37, 54]. Для сокращения перебора здесь вычисляются нижние оценки целевой функции (в случае ее минимизации), а также используются комбинаторные свойства задач, например, свойства оптимальных расписаний.
Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [21, 22, 70, 80].
В последнее время широкое распространение получил метод программирования в ограничениях. Одной из областей его успешного применения является теория расписаний [29].
Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — "гибридные алгоритмы" [5, 51]. На данный момент данное направление является одним из перспективных.
Общая характеристика работы
Диссертационная работа посвящена исследованию iVP-трудных задач теории расписаний для одного прибора с неодновременным поступлением требований с критериями минимизации максимального временного смещения (1 rj Lmax) и минимизации взвешенного числа запаздывающих требований (1 Tj J2WJUJ). Для первой задачи предложена схема нахождения приближенного решения с гарантированной абсолютной погрешностью. В диссертации рассмотрены два варианта данной схемы, основанные на двух
полиномиально разрешимых классов примеров задачи. Для данной задачи также предложены два точных алгоритма решения общего случая. Алгоритмы хорошо показали себя в численных экспериментах при их сравнении с лучшими существующими в литературе алгоритмами решения задачи 1 I fj I -kmax- Для решения второй задачи предложен точный алгоритм, работающей по схеме метода ветвей и отсечений. Последний является расширением метода ветвей и границ для решения задач целочисленного линейного программирования (ЦЛП). В алгоритме задача формулируется как задача ЦЛП. Из последней исключаются некоторые ограничения, то есть мы получаем релаксацию изначальной задачи. Затем "усеченная" задача ЦЛП решается методом ветвей и границ. При этом в процессе решения недопустимые решения для исходной задачи исключаются с помощью добавления в формулировку дополнительных ограничений — отсечений. При проведении сравнительного экспериментального исследования предложенный алгоритм показал хорошие результаты.
Структура и обзор результатов диссертации
Диссертационная работа состоит из введения, трех глав, заключения и списка литературы.
Первые две главы посвящены задаче 1 гj \ Lmax. В начале первой главы доказывается следующая теорема об абсолютной погрешности. Пусть задано множество требований N = {1,2,..., п}. Определим rf,pfvi. df как время поступления, длительность обслуживания и директивный срок требования j Є N для примера А, соответственно. Обозначим также ЬА{тт) как максимальное временное смещение расписания 7г для примера А.
Пусть длительности обслуживания требований одинаковы для двух заданных примеров задачи А ж С. Пусть также іхА и ттс — оптимальные расписания для этих примеров. Теорема доказывает, что в этом случае 0 ЬА(ігс)-ЬА(тгА) р{А,С), где р(А, С) = max.jeN{df - d } + maxj]v{ f — df] + maxj./v{r/ - rf} + max?ejv{ f — rf }• To есть оптимальное расписание для примера С имеет абсолютную погрешность р(Л, С) для примера А.
Затем предлагается схема приближенного решения задачи 1 Tj \ Lmax, основанная на сведении заданного примера А к примеру С из некоторого полиномиально разрешимого класса задачи, причем пример С наследует у примера А длительности обслуживания. Оптимальное расписание ттс для примера С может быть найдено за полиномиальное время. Из теоремы следует, что абсолютная погрешность расписания ттс для примера А не превышает р(А,С). Для двух известных полиномиально разрешимых классов примеров задачи найдены эффективные алгоритмы нахождения примера С, наследующего длительности обслуживания, принадлежащего к заданному классу и наименее удаленного от заданного примера А в псевдометрике р. Расстояние р(А.С) от примера А до такого примера С может пониматься как расстояние от примера А до рассматриваемого класса примеров задачи или метрика данного класса примеров.
В конце первой главы представлены результаты экспериментального исследования применения некоторых полиномиальных алгоритмов для решения общего случая задачи. Алгоритмы используются как непосредственно, так и в составе предложенной схемы приближенного решения задачи. Для использования в экспериментах предлагается процедура генерации примеров по равномерному распределению из ограниченного множества содержащего всевозможные примеры задачи. В экспериментах исследуется соотношение между практическим значением абсолютной погрешности полученного с помощью предложенной схемы решения и теоретическим значением р(Д С). Также устанавливается процент оптимально решенных примеров задачи выбранными полиномиальными алгоритмами.
Вторая глава посвящена исследованию точных алгоритмов решения общего случая задачи 1 гj Lmax. В начале главы представлен несколько измененный нами алгоритма Карлье, считающийся наиболее эффективным для данной задачи. Далее рассматриваются основы метода программирования в ограничениях (ПвО, в английской литературе — Constraint Programming) и показывается, как с помощью данного метода можно сформулировать и решить задачи теории расписаний с запрещением прерываний при обслуживании требований.
Далее во второй главе предлагаются два алгоритма ветвей и границ решения задачи 1 rj \ Ьтах, основанные на идеях, заложенных в алгоритме Карлье и в методе ПвО. Представленные результаты экспериментов показывают преимущество предложенных алгоритмов над существующими на множестве тестовых примеров.
В заключительном разделе второй главы рассматривается вариант задачи 1 r\j Lmax. Назовем множество требований К допустимым по отношению к константе I/, если существует допустимое расписание 7г множества требований К (с максимальным временным смещением не большим, чем U). В варианте задачи требуется определить допустимо ли заданное множество требований N по отношению к заданной константе U. Если N допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти недопустимое по отношению I/ подмножество требований из N наименьшей мощности. Для данного варианта задачи предлагается алгоритм, который гарантировано находит допустимое расписание в случае допустимости заданного множества требований N. Алгоритм является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований в случае недопустимости N. Нахождение минимального недопустимого подмножества не гарантируется.
Предложенный алгоритм используется в третьей главе диссертации.
В третьей главе диссертации предлагается точный алгоритм решения задачи 1 r?- Y wjUj- Данная задача может быть сформулирована как задача целочисленного линейного программирования (ЦЛП) и решена по "гибридному" методу, описанному в первом разделе третьей главы. Для решения задачи предлагается следующий алгоритм ветвей и отсечений. Из формулировке задачи ЦЛП удаляется часть ограничений, замедляющих ее решение. Затем "урезанная" формулировка решается методом ветвей и границ (метод Лэнд и Дойг). Каждое полученное целочисленное решение формулировки проверяется на допустимость с помощью специально разработанных комбинаторных алгоритмов. В случае недопустимости решения генерируются дополнительное ограничение, добавляемое в формулировку задачи. Данное ограничение, называемое отсечением, должно выполняться всеми допустимыми решениями задачи и нарушаться полученным целочисленным решением формулировки. В третьей главе работы предлагаются алгоритмы проверки решения на допустимость и алгоритмы генерации отсечений. Алгоритмы первой группы основаны на результатах, полученных во второй главе диссертации.
В заключение третьей главы представляются результаты численных экспериментов, проведенных с предложенным алгоритмом ветвей и отсечений. Алгоритм был протестирован на множестве общедоступных тестовых примеров. Экспериментальное исследование показало преимущество алгоритма ветвей и отсечений над лучшим по информации, имеющейся у автора, алгоритмом, существующим в литературе.
Публикации и аппробация результатов исследований
Основные результаты диссертации опубликованы в следующих 9 работах: [8], [9], [10], [13], [12], [61], [71], [72], [73].
В совместных работах Садыкову P.P. принадлежит: в [73] — экспериментальное исследование абсолютной погрешности для задачи 1 гj Lmax; в [8, 9] - экспериментально исследование полиномиальных алгоритмов решения специального случая задачи 1 r-j Ьтах; в [10, 61, 12] — обобщение результата о максимальной абсолютной погрешности приближенного решения задачи 1 Tj Ь1ШХ на случай с использованием времен поступлений, вариант схемы приближенного решения задачи, основанный на случае Хогевена; в [72] — модификация алгоритма Карлье для решения задачи 1 rj І-яіах, проведенная с использованием алгоритмов программирования в ограничениях, реализация экспериментального сравнения алгоритмов ветвей и границ.
Результаты диссертации докладывались и обсуждались на VII Международном семинаре "Дискретная математика и ее приложения" (Москва, 2001 г.), XL Международной научной студенческой конференции "Студент и научно-технический прогресс" (Москва, 2002 г.), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002 г.), Международной конференции по оптимизации FGI-2000 (Монтпелье, Франция, 2000 г.), I Международной конференции по интеграции методов исследования операций и искусственного интеллекта в программировании в ограничениях для решения комбинаторных задач CP-AI-OR 04 (Ницца, Франция, 2004 г.), VII Международном семинаре по методам и алгоритмам для задач календарного планирования и теории расписаний MAPSP 05 (Сиена, Италия, 2005 г.).
Обозначения и определения основных понятий
Будем рассматривать следующую задачу теории расписаний. На одном приборе необходимо обслужить требования множества N = {1,2,... ,п}. Каждое требование мы будем обозначать его номером, то есть запись "требование f эквивалентна записи "требование с номером Запрещается одновременное обслуживание и прерывания при обслуживании требований. Для требования j Є N имеем: Tj — минимально возможный момент начала обслуживания, pj 0 — продолжительность обслуживания, dj — директивный срок завершения обслуживания.
Расписание задается совокупностью тг = {SJ \ j Є N} моментов начала обслуживания требований. Множество всевозможных расписаний обслуживания требований множества N обозначим как II(JV). Расписание тг называется допустимым, если Sj(ir) Tj, Vj Є N. Обозначим момент завершения обслуживания требования j Є N в расписании тг как Cj(ir). Тогда Lj(ir) — Cj(тг) — dj, j Є N, обозначает временное смещение требования j в расписании тг, и Ь(тг) = тах дг Lj(тг) — максимальное временное смещение расписания тг. Максимальное временное смещение требований из множества N при расписании тг определяется как
Обозначим момент завершения обслуживания всех требований множества N в расписании тг через
Задача состоит в нахождении оптимального расписания тг с наименьшим значением максимального временного смещения: Для произвольного множества требований Z будем также обозначать:
В стандартной нотации Грэхэма и др. (Graham at al. [45]) данная задача обозначается как 1 гj Lmax. Интенсивные работы над решением этой задачи продолжаются с начала 50-х годов 20-го века. Ленстра и др. (Lenstra et al. [62]) показали, что общий случай задачи 1 Tj \ Lmax является NP-трудным в сильном смысле.
Поттс (Potts [69]) представил итерационную версию расширенного правила Джексона (IJ) и доказал, что Lmax (7Г/j)/I4ax . Холл и Шмойс (Hall, Shmoys [47]) модифицировали итерационную версию и создали алгоритм (MIJ), который гарантирует оценку Ьтах(тгми)/- тах Также они представили две аппроксимационные схемы, гарантирующие нахождение є-приближенного решения за 0(nlogn + n(l/e) /e )) и 0{{п/е)0 ) операций. Недавно Мастролилли (Mastrolilli [64]) представил улучшенную аппроксимационную схему, выполняющуюся за время 0(п + (1/є) ).
Был выделен ряд полиномиально разрешимых случаев задачи, начиная с раннего результата Джексона (Jackson [50]) для случая Tj — 0, j Є N, когда решением является расписание, в котором требования упорядочены по неубыванию директивных сроков (по правилу EDD). Такое расписание также будет оптимальным для случая, когда времена поступления и директивные сроки согласованы (гІ fj 4Ф d{ dj, Vi, j Є N).
Специальные случаи 1 prec\Tj Cmax, 1 preqpj = p;rj Lmax и 1 prec; rj;pmtn Lmax с ограничениями предшествования для требований были рассмотрены в работах Лоулера (Lawler [56]), Симонса (Simons [78]), Бейкера и др. (Baker et al. [25]). Хогевен (Hoogeveen [48]) предложил полиномиальный алгоритм для специального случая, когда параметры требований удовлетворяют ограничениям dj — pj — А Tj dj — A, Vi, для константы А. Псевдополиномиальный алгоритм для NP-сложного случая, когда времена поступления и директивные сроки расположены в обратном порядке (d\ ... dn и г\ ... rn), был разработан Лазаревым и Шульгиной [11].
В данном разделе мы приведем основные обозначения и определения, которые будут нами использоваться в дальнейшем.
Определение 1.1 Для примера А каждая перестановка г требований множества N однозначно определяет раннее расписание 7г . В раннем расписании каждое требование j Є N начинает обслуживаться сразу после окончания обслуживания предыдущего требования в соответствующей перестановке. Если время окончания обслуживания предыдущего требования меньше времени поступления текущего требования, то начало обслуживания откладывается до момента поступления.
Экспериментальное исследование полиномиальных алгоритмов решения задачи
Теперь покажем, что построенный пример С удовлетворяют свойству Хогевена. Возьмем константу \3 = df —ту —pj — df —r_j —pj . Рассмотрим произвольное требование j Є N.
Если df - Tj df, - Tj - pj , то из (1.40), df = df и df - Tj /3. Имеем также df — fj — Pj (3 по определению j и (3. Если же df — Tj df —fj —pj , то из (1.40), df—rj = (3. Очевидно, что тогда df—rf—pf (3. Следовательно, пример С удовлетворяют свойству Хогевена.
Доказательство трудоемкости алгоритма сведения примера А к примеру С следует из того, что для данного преобразования мы должны применить формулу (1.40) п раз. На основе Теоремы 1.3 получаем очевидный Алгоритм 1.2, который сводит пример А к примеру С, для которого (1.37) выполняется как равенство. Для примера А из Таблицы 1.1 оценка абсолютной погрешности решения, полученного с помощью варианта схемы на основе случая Хогевена, составляет рн{А) — 1. Алгоритм 1.2 Алгоритм построения примера, удовлетворяющего случаю Хогевена, минимизирующий р(А,С)
В данном разделе мы экспериментально оценим эффективность использования полиномиальных алгоритмов Лазарева и Хогевена для решения общего случая задачи. Также будет исследована фактическая абслютная погрешность расписаний, полученных с помощью вариантов схемы приближенного решения задачи, представленных в Разделе 1.4.
При проведении экспериментальных исследований одним из первостепенных вопросов является способ генерации тестовых примеров. Мы покажем, что множество Фп всех примеров задачи размерности п может быть преобразовано в ограниченное множество Фп, где каждый элемент представляет собой бесконечное число эквивалентных примеров задачи. В подразделе 1.5.1 мы представим свою процедуру генерации и покажем, что она генерирует примеры по равномерному распределению на множестве Фп.
Используя данную процедуру, в подразделе 1.5.2 мы оценим насколько теоретическое оценка абсолютной погрешности р(А,С) превышает среднее практическое значение абсолютной погрешности приближенного решения, полученного по схеме, представленной в Разделе 1.4. Сравнение теоретической и практической абсолютной погрешности будет произведено для вариантов схемы на основе случаев Лазарева и Хогевена.
Согласно Теореме 1.4 каждая точка, соответствующая примеру с параметрами требований может быть спроецирована на единичную сферу в Зп-мерном пространстве без изменения множества оптимальных расписаний. Следовательно, в качестве множества всех примеров задачи размерности п мы можем взять множество Фп, которое является частью единичной сферы в Зп-мерном пространстве, где Pj 0, j Є N. Таким образом, для каждого примера из множества Фп существует эквивалентный пример из множества Фп.
В экспериментальном исследовании одним из оцениваемых параметров будет относительная погрешность найденного расписания. Поэтому, оптимальное значение целевой функции не должно равняться нулю. В противном случае значение относительной погрешности может равняться бесконечности. Во избежание подобного результата параметры требований тестовых примеров мы будем модифицировать таким образом, чтобы выполнялось гj 0 и dj О, j Є N. Тогда временное смещение каждого требования, и, соответственно, максимального, будет больше нуля.
Рассмотрим пример А с параметрами требований {rf,pf,df}, j Є iV, и пример В с параметрами требований {г? = rf + a,pf = pf, df = dj + /3}, j Є N, где а и p — некоторые константы. Согласно Теореме 1.1, р(А, В) = О, из чего следует, что примеры А я В эквивалентны.
Преобразуем множество Фп примеров задачи во множество Фп. Для этого каждый пример А из Фп преобразуем в эквивалентный ему пример В из Фп следующим образом: rf = rf-minrf, pf=pf, df = dj-maxd?, Vj Є N.
Таким образом, множества примеров Фп и Фп эквивалентны, и для рассмотрения множества всех примеров размерности п можно ограничится примерами из множества Фп, оптимальное значение целевой функции для которых строго положительно.
Следующий Алгоритм 1.3 равномерно генерирует примеры из множества Фп для заданного п, а затем преобразует их в примеры из множества Фп. Так как Фп представляет собой часть единичной Зп-мерной сферы, для получения равномерной генерации примеров из Фп, параметры требований (координаты) генерируются по нормальному распределению.
Метод программирования в ограничениях
В данном подразделе мы рассмотрим метод программирования в ограничениях (ПвО) и его использование для решения задач теории расписаний.
Программирование в ограничениях (Constraint Programming) - это метод, созданный для решения комбинаторных задач, которые могут быть смоделированы как одна или несколько задач выполнимости системы ограничений (ЗВСО) (Constraint Satisfaction Problem). Пример ЗВСО задается множеством переменных, множеством возможных значений для каждой переменной, называемым доменом (domain), а также множеством ограничений, заданных на множестве переменных. ЗВСО является задачей распознавания, где требуется узнать, существуют ли такие возможные значения переменных, при которых выполняются все заданные ограничения. Множество таких значений переменных, если задача выполнима, называется решением ЗВСО. В ПвО ограничения используются не только для тестирования допустимости решения, но также и в активном режиме для удаления значений из доменов переменных, определения вытекающих новых ограничений, установления несовместимости. Процесс использования ограничений для получения этих заключений называется пропагациеи ограничений (constraint propagation). Алгоритмы, которые осуществляют пропагацию ограничений, называются алгоритмами фильтрации (filtering algorithms).
Рассмотрим следующий пример активного использования ограничений. Пусть нам дана система из трех ограничений: где х и у - целые числа (х, у Є Z). Рассматривая первые два ограничения, можно заключить, что у 4, домен переменной у при этом уменьшится до у Є (—со, 3], у Є Z. Затем, используя третье ограничение можно зафиксировать противоречие (домен переменной у становится пустым), означающее несовместимость системы ограничений (2.4).
Так как в общем случае ЗВСО является ЛГР-сложной [1], обычно про-пагация ограничений не дает ответа на вопрос о существовании решения задачи. То есть не все следствия из системы ограничений могут быть выведены. В частности, одной пропагацией ограничений не всегда можно установить несовместимость системы. Поэтому для решения задачи необходимо дополнительно производить частичный перебор решений. Обычно это осуществляется с помощью алгоритма, использующего дерево поиска. В итоге метод ПвО является в некоторой степени аналогом метода ветвей и границ. Отличие заключается в том, что в методе ветвей и границ для сокращения перебора используется правило оценивания, а в ПвО - пропагация ограничений.
Важный принцип ПвО, так называемый "принцип локальности", заключается в том, что пропагация каждого ограничения должна осуществляться как можно более независимо от других ограничений задачи. В соответствии с данным принципом алгоритмы фильтрации разрабатываются для каждого ограничения или группы ограничений отдельно, что позволяет не создавать специальные алгоритмы для каждой вновь возникающей задачи, а использовать уже существующие алгоритмы как "кирпичики" для решения сложных практических задач.
Детальное представление метода программирования в ограничениях можно найти в книгах [24, 63].
Задачи теории расписаний для одного прибора с запрещением прерываний могут быть смоделированы как ЗВСО следующим образом. Для каждого требования j Є N вводится переменная start(j), которая обозначает время фактического начала обслуживания требования j. Также для каждого требования в качестве исходных данных задачи задаются время поступления требования г7-, жесткий директивный срок dj, а также время обслуживания pj. Заметим, что все исходные данные задачи должны быть целыми числами. Любое требование j Є N может обслуживаться только в отрезке [г,,-, dj]. Поэтому начальным доменом переменной start(j) является множество целых чисел из отрезка [rj,dj — Pj] (Рисунок 2.1). В процессе решения задачи домен переменной start(j) может уменьшаться, но для удобства мы будем использовать rj и dj также для обозначения текущего наименьшего времени начала обслуживания (текущего времени поступления) и текущего наибольшего времени окончания обслуживания (текущего предельного срока) требования j, соответственно.
Формулировка задачи как задачи
Итак, пусть рассматриваемая задача может быть сформулирована как следующая задача частично целочисленного линейного программирования {ЧЦЛІТ):
Задача (ОР) имеет как целочисленные (булевы), так и действительные переменные, причем только часть булевых переменных имеет ненулевые коэффициенты в целевой функции. Множество ограничений разделено на два подмножества. Ограничения (3.2) отображают некоторые аспекты задачи, которые могут быть эффективно смоделированы линейными ограничениями. Напротив, ограничения (3.3) вносят сложность в решение задачи ЧЦЛП стандартными методами, например, ввиду большой размерности. Важным моментом, влияющим на эффективность рассматриваемой схемы, является то, что отсутствие ограничений (3.3) по возможности не должно сильно влиять на оптимальное значение линейной релаксации задачи (ОР).
Здесь ограничения (3.8) и (3.10) - это переформулированные ограничения (3.3). Ограничения (3.8) могут быть любыми, они не обязательно должны быть линейными. Множество возможных значений В переменных х, у, V также может быть задано произвольным способом. Однако, между переменными х и х должно быть взаимно-однозначное соответствие (3.7).
Основой схемы решения задачи (GP) является задача ЧЦЛП, включающая только часть исходных ограничений и решаемая стандартным методом, а также задача выполнимости, которая решается наиболее подходящими для нее методами, это может быть программирование в ограничениях или специализированные комбинаторные алгоритмы. Решая задачу ЧЦЛП, мы находим решение, удовлетворяющее ограничениям (3.6) и (3.9), оптимизируя при этом целевую функцию (3.5). Решение х данной задачи преобразуется в частичное решение х задачи выполнимости. Затем задача выполнимости проверяет существуют ли такие значения у и v для переменных рв, что решение {x,y,v) является допустимым для ограничений (3.8) и (3.10). Если расширение возможно, то значение целевой функции такого полного решения такое же, как и частичного решения х.
Опишем детально рассматриваемую схему решения задачи (GP). На итераций к алгоритма решается следующая задача ЧЦЛП: Задача (МІР) может быть решена стандартным методом ветвей и границ (метод Лэнд и Дойг [55]). Ограничения (3.13) находятся на предыдущих итерациях, они будут рассмотрены далее по тексту. Если задача (МІР) не имеет решения, то и исходная задача (GP) также не имеет решения, т.к. область допустимых решений (МІР) больше чем (GP). Если найдено решение хк задачи (МІР), то оно трансформируется ъ хк о, помощью соотношений (3.7) и решается следующая задача выполнимости:
В некоторых случаях задача (FP) разбивается на независимые подзадачи, каждая из которых решается по отдельности, что уменьшает время решения. Поэтому, когда это возможно, следует разбивать ограничения задачи на подмножества (3.2) и (3.3) таким образом, чтобы задача (FP) разбивалась на подзадачи.
Если решение (#, у, v) задачи (FP) найдено, то оно будет оптимальным для исходной задачи (GP), так как это решение имеет такое же значение целевой функции, как и решение хк задачи (МІР). Если же решение не найдено, то хк исключается из пространства допустимых решений задачи (МІР). Для этого генерируется следующее отсечение: где Тк = {і \ х\ = 1}, Fk = {г хк = 0}, Вк = Тк . Отсечения в форме (3.18) являются универсальными для рассматриваемого класса задач и отсекают только одно решение, так как любое другое решение х %к удовлетворяет ограничению (3.18). Поэтому, когда это возможно, следует использовать специфические для конкретной задачи более сильные отсечения Qkx qk, которые отсекают несколько однотипных решений из области допустимых значений задачи (МІР). Отсечения являются связующим звеном между задачами (МІР) и (FP), и от того, какой тип отсечений используется, напрямую зависит эффективность всего алгоритма, разработанного в рамках рассматриваемой схемы.
Похожие диссертации на Алгоритмы решения задач теории расписаний для одного прибора с критериями Lmax и EwjUj
