Оглавление
Введение 4
1 Полиномиальные алгоритмы решения задачи 1 | г| Ьтлх 12
1.1 Постановка задачи..................................................... 13
1.2 Обозначения и определения основных понятий............................ 15
1.3 Абсолютная погрешность приближенного решения.......................... 17
1.4 Схема нахождения приближенного решения................................ 22
1.4.1 Вариант схемы на основе случая Лазарева....................... 25
1.4.2 Вариант схемы на основе случая Хогевена....................... 32
1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи 11 | Ьтах.................................................... 36
1.5.1 Способ генерации примеров..................................... 37
1.5.2 Оценка практического значения абсолютной погрешности 40
1.5.3 Эффективность применения полиномиальных
алгоритмов для общего случая задачи............................ 42
2 Алгоритмы оптимального решения задачи 1 | г| Ьт(их 46
2.1 Существующие методы решения задачи 1 | г$ | £тах............................................... 48
2.1.1 Алгоритм Карлье............................................... 48
2.1.2 Метод программирования в ограничениях......................... 53
2.2 Алгоритмы решения задачи 1 (| Лтах ................................... 59
2.3 Экспериментальное сравнение алгоритмов
решения задачи 11 г, | Лтах.......................................... 65
2
2.4 Модифицированный алгоритм Карлье................................... 71
3 Алгоритм ветвей и отсечений для решения задачи 11 г, | 80
3.1 “Гибридная” схема решения одного класса задач целочисленного линейного программирования................................................... 81
3.2 Постановка задачи.................................................. 89
3.3 Формулировка задачи 1 | ту-1 как задачи ЧЦЛП................. 91
3.4 Дополнительные ограничения......................................... 94
3.5 Генерация отсечений................................................ 98
3.6 “Гибридный” алгоритм ветвей и отсечений........................... 109
3.7 Экспериментальная оценка эффективности............................ 111
Заключение 119
Список литературы 121
3
Введение
Общее направление исследований
В наше время люди все чаще и чаще сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Например, мы обычно планируем наши действия в порядке возрастания крайних сроков их исполнения. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно.
Однако, когда дело касается большого производства, целесообразным является использование настолько хороших расписаний, насколько это возможно. Улучшение расписания даже на несколько процентов может дать существенную экономию. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом все более и более трудные задачи составления расписаний.
Данное направление в науке, получившее название “теория расписаний” t берет свое начато в 50-е годы 20-го века. Одними из первых работ по теории расписаний считаются труды Джонсона (Johnson [53]), Джексона (Jackson [50]) и Смита (Smith [79]).
Изначально одними из главных вопросов нового направления были классификация задач и установление их сложности. Считающаяся стандартной и по нынешний день классификация задач теории расписаний была предло-
4
жена Грэхэмом и др. (Graham at al. [45]). Относительно быстро была установлена сложность большого числа задач. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона (Garey, Johnson [1]), Ленстры и др. (Lenstra et al. [62]), Лоулера и др. (Lawler et al. [59]), Танаева и др. [17, 18], Брукера (Brücker [36]).
Отметим, что подавляющее большинство задач теории расписаний являются АР-трудными. Несмотря на это, практика требует решение таких задач. Для этого существует несколько подходов.
Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближенными [6, 16]. Существуют приближенные алгоритмы, гарантирующие как относительную погрешность [2, 76], так и абсолютную погрешность [14]. Некоторые iVP-трудные задачи допускают существование так называемой аппроксимационной схемы. В рамках данной схемы можно найти решение с относительной погрешностью не более любого заданного значения е > 0 за время, полиномиально зависящее от 1/е. Для задач теории расписаний такие схемы разработали, например, Ковалев [3], Алон и др. (Alon et al. [23]), Мастролилли (Mastrolilli [64]), Севастьянов и Вёгин-гер (Sevastianov,Woeginger [77]. Для задач, не имеющих аппроксимационной схемы, большое значение имеет установление предельного значения с, для которого возможно нахождения ^-приближенного алгоритма за полиномиальное время.
В настоящий момент широкое распространение имеют метаэвристиче-ские алгоритмы (еще их называют алгоритмами “локального поиска”), которые находят решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. То есть неизвестно, насколько решение отличается от
5
оптимального в наихудшем случае.
Точным методам решения Т/Р-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение получили методы сокращения перебора, также называемые методами ветвей и границ [4,15,35,37,54]. Для сокращения перебора здесь вычисляются нижние оценки целевой функции (в случае ее минимизации), а также используются комбинаторные свойства задач, например, свойства оптимальных расписаний.
Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [21, 22, 70, 80].
В последнее время широкое распространение получил метод программирования в ограничениях. Одной из областей его успешного применения является теория расписаний [29].
Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — “гибридные алгоритмы” [5. 51]. На данный момент данное направление является одним из перспективных.
Общая характеристика работы
Диссертационная работа посвящена исследованию А^Р-трудных задач теории расписаний для одного прибора с неодновременным поступлением требований с критериями минимизации максимального временного смещения (1 | Гу | Ртах) и минимизации взвешенного числа запаздывающих требований (1 | ту | Для первой задачи предложена схема нахождения
приближенного решения с гарантированной абсолютной погрешностью. В диссертации рассмотрены два варианта данной схемы, основанные на двух
б
полиномиально разрешимых классов примеров задачи. Для данной задачи также предложены два точных алгоритма решения общего случая. Алгоритмы хорошо показали себя в численных экспериментах при их сравнении с лучшими существующими в литературе алгоритмами решения задачи 1 | г1 | £тах- Для решения второй задачи предложен точный алгоритм, работающей по схеме метода ветвей и отсечений. Последний является расширением метода ветвей и границ для решения задач целочисленного линейного программирования (ЦЛП). В алгоритме задача формулируется как задача ЦЛП. Из последней исключаются некоторые ограничения, то есть мы получаем релаксацию изначальной задачи. Затем ‘Усеченная” задача ЦЛП решается методом ветвей и границ. При этом в процессе решения недопустимые решения для исходной задачи исключаются с помощью добавления в формулировку дополнительных ограничений — отсечений. При проведении сравнительного экспериментального исследования предложенный алгоритм показал хорошие результаты.
Структура и обзор результатов диссертации
Диссертационная работа состоит из введения, трех глав, заключения и списка литературы.
Первые две главы посвящены задаче 1 | ту- | Ьтих. В начале первой главы доказывается следующая теорема об абсолютной погрешности. Пусть задано множество требований N = {1,2,... ,п}. Определим гА, рА и (1А как время поступления, длительность обслуживания и директивный срок требования j е N для примера А, соответственно. Обозначим также ЬЛ(7Г) как максимальное временное смещение расписания тг для примера А.
Пусть длительности обслуживания требований одинаковы для двух заданных примеров задачи А и С. Пусть также тгА и тгс — оптимальные
7
расписания для этих примеров. Теорема доказывает, что в этом случае
0<Ьа(71С)-Ьа(тга) </>(А,С),
где р(Л, С) = шах;-едг{^ - с£?} + таXjGл/{^ - с^} -I- тах?€дг{г^ - г?} + тах^у{г^ - гА}. То есть оптимальное расписание для примера С имеет абсолютную погрешность р(А, С) для примера А.
Затем предлагается схема приближенного решения задачи 1 | г^ | Атах, основанная на сведении заданного примера А к примеру С из некоторого полиномиально разрешимого класса задачи, причем пример С наследует у примера А длительности обслуживания. Оптимальное расписание 7гс для примера С может быть найдено за полиномиальное время. Из теоремы следует, что абсолютная погрешность расписания я*с для примера А не превышает р(А.С). Для двух известных полиномиально разрешимых классов примеров задачи найдены эффективные алгоритмы нахождения примера С, наследующего длительности обслуживания, принадлежащего к заданному классу и наименее удаленного от заданного примера А в псев-дохметрике р. Расстояние р(А, С) от примера А до такого примера С может пониматься как расстояние от примера А до рассматриваемого класса примеров задачи или метрика данного класса примеров.
В конце первой главы представлены результаты экспериментального исследования применения некоторых полиномиальных алгоритмов для решения общего случая задачи. Алгоритмы используются как непосредственно, так и в составе предложенной схемы приближенного решения задачи. Для использования в экспериментах предлагается процедура генерации примеров по равномерному распределению из ограниченного множества содержащего всевозможные примеры задачи. В экспериментах исследуется соотношение между практическим значением абсолютной погрешности полученного с помощью предложенной схемы решения и теоретическим значением р(АуС). Также устанавливается процент оптимально решенных примеров
задачи выбранными полиномиальными алгоритмами.
Вторая глава посвящена исследованию точных алгоритмов решения общего случая задачи 1 | rj \ Ьтйх. В начале главы представлен несколько измененный нами алгоритма Карлье, считающийся наиболее эффективным для данной задачи. Далее рассматриваются основы метода программирования в ограничениях (ПвО, в английской литературе — Constraint Programming) и показывается, как с помощью данного метода можно сформулировать и решить задачи теории расписаний с запрещением прерываний при обслуживании требований.
Далее во второй главе предлагаются два алгоритма ветвей и границ решения задачи 1 | гj | Lmax, основанные на идеях, заложенных в алгоритме Карлье и в методе ПвО. Представленные результаты экспериментов показывают преимущество предложенных алгоритмов над существующими на множестве тестовых примеров.
В заключительном разделе второй главы рассматривается вариант задачи 1 | Tj | Lmax. Назовем множество требований К допустимым по отношению к константе Ь\ если существует допустимое расписание тг множества требований К (с максимальным временным смещением не большим, чем V). В варианте задачи требуется определить допустимо ли заданное множество требований N по отношению к заданной константе IJ. Если N допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти недопустимое по отношению JJ подмножество требований из N наименьшей мощности. Для данного варианта задачи предлагается алгоритм, который гарантировано находит допустимое расписание в случае допустимости заданного множества требований N. Алгоритм является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований в случае недопустимости N. Нахождение минимального недопустимого подмножества не гарантируется.
9
Предложенный алгоритм используется в третьей главе диссертации.
В третьей главе диссертации предлагается точный алгоритм решения задачи 1 | г^ | Данная задача может быть сформулирована как
задача целочисленного линейного программирования (ЦЛП) и решена по “гибридному5 методу, описанному в первом разделе третьей главы. Для решения задачи предлагается следующий алгоритм ветвей и отсечений. Из формулировке задачи ЦЛП удаляется часть ограничений, замедляющих ее решение. Затем “урезанная” формулировка решается методом ветвей и границ (метод Лэнд и Дойг). Каждое полученное целочисленное решение формулировки проверяется на допустимость с помощью специально разработанных комбинаторных алгоритмов. В случае недопустимости решения генерируются дополнительное ограничение, добавляемое в формулировку задачи. Данное ограничение, называемое отсечением, должно выполняться всеми допустимыми решениями задачи и нарушаться полученным целочисленным решением формулировки. В третьей главе работы предлагаются алгоритмы проверки решения на допустимость и алгоритмы генерации отсечений. Алгоритмы первой группы основаны на результатах, полученных во второй главе диссертации.
В заключение третьей главы представляются результаты численных экспериментов, проведенных с предложенным алгоритмом ветвей и отсечений. Алгоритм был протестирован на множестве общедоступных тестовых примеров. Экспериментальное исследование показало преимущество алгоритма ветвей и отсечений над лучшим но информации, имеющейся у автора, алгоритмом, существующим в литературе.
Публикации и аппробация результатов исследований
Основные результаты диссертации опубликованы в следующих 9 работах: [8], [9], [10], [13], [12], [61], [71], [72], [73].
10
В совместных работах Садыкову P.P. принадлежит: в [73] — экспериментальное исследование абсолютной погрешности для задачи 1 | гj | Lmax; в [8, 9] - экспериментально исследование полиномиальных алгоритмов решения специального случая задачи 1 | г j [ Lrnax; в [10, 61, 12] — обобщение результата о максимальной абсолютной погрешности приближенного решения задачи 1 | гj \ LmüX на случай с использованием времен поступлений, вариант схемы приближенного решения задачи, основанный на случае Хогевена; в [72] — модификация алгоритма Карлье для решения задачи 1 I Tj | .Z/max) проведенная с использованием алгоритмов программирования в ограничениях, реализация экспериментального сравнения алгоритмов ветвей и границ.
Результаты диссертации докладывались и обсуждались на VII Международном семинаре ‘‘Дискретная математика и ее приложения” (Москва, 2001 г.), XL Международной научной студенческой конференции “Студент и научно-технический прогресс” (Москва, 2002 г.), Российской конференции “Дискретный анализ и исследование операций” (Новосибирск, 2002 г.), Международной конференции по оптимизации FGI-2000 (Монтпелье, Франция, 2000 г.), I Международной конференции по интеграции методов исследования операций и искусственного интеллекта в программировании в ограничениях для решения комбинаторных задач CP-AI-OR’04 (Ницца, Франция, 2004 г.), VII Международном семинаре по методам и алгоритм мам для задач календарного планирования и теории расписаний MAPSP’05 (Сиена, Италия, 2005 г.).
11
- Київ+380960830922