Алгоритмы с оценками качества для задач календарного планирования, упаковки и выбора подмножества векторов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Рыков, Иван Александрович

• Рыков, Иван Александрович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Рыков, Иван Александрович

Введение

Глава 1 Задача календарного планирования в условиях ограниченных ресурсов

1.1 Постановка задачи.

1.1.1 Классическая постановка.

1.1.2 Известные обобщения.

1.1.3 Возобновимые, складируемые и невозобновимые ресурсы

1.1.4 Задачи упаковки как частные случаи задачи календарного планирования

1.2 Связь задачи календарного планирования с задачей упаковки в полосу.

1.2.1 Оценка сверху на отношение оптимальных значений

1.2.2 Пример с отношением 5/4.

1.2.3 Минимальность примера

1.3 Приближенный алгоритм для мультипроектной задачи календарного планирования

1.3.1 Приближенный полиномиальный алгоритм для задачи упаковки в полосу

1.3.2 Мультипроектная постановка.

1.4 Опыт применения алгоритмов для задачи планирования в прикладных проектах.

1.4.1 Коммерческая библиотека решения задач планирования LSE.

1.4.2 Система планирования собраний Freetime.

1.4.3 Вероятностная модель планирования ВСНГК.

Глава 2 Задача выбора подмножества векторов

2.1 Постановка задачи.

2.2 Алгоритм решения задачи с целочисленными координатами векторов.

2.2.1 Алгоритм решения задачи гп-ПВ с целочисленными координатами векторов.

2.2.2 Алгоритм решения задачи ПВО с целочисленными координатами векторов.

2.3 Полиномиальный при фиксированном к алгоритм.

2.4 Приближенный рандомизированный алгоритм и условия его асимптотической точности.

Введение диссертации (часть автореферата) на тему «Алгоритмы с оценками качества для задач календарного планирования, упаковки и выбора подмножества векторов»

В двадцатом веке, в связи с радикальным усложнением возникающих задач оптимизации, возникла потребность в развитии математического аппарата, поддерживающего принятие решений. Возникла новая область математики, названная исследованием операций. Деятельность исследователя операций при поддержке принятия наилучших решений состоит из следующих этапов: анализ реальной проблемы и составление математической модели; разработка алгоритмов нахождения оптимального решения в полученной модели; корректировка модели в случае, если полученное решение оказывается практически неприемлемым.

Математическую модель реальной задачи принятия решения в общем случае можно представить в виде f{x) min, (*) xGsi где множество Q определяет область доступных для выбора вариантов (допустимых решений), функция / : Cl —> R, называемая целевой функцией, определяет критерий, позволяющий сравнивать различные решения.

Если множество О, в задаче (*) конечно, ее называют задачей дискретной оптимизации. Любую такую задачу можно решить, рассмотрев все элементы множества ГI. Однако мощность множества Q может оказаться слишком большим для осуществления полного перебора в обозримое время. В частности, его размер может экспоненциально возрастать с ростом длины входа. Этот факт, в своё время, был назван проклятием размерности [21]. Фрагменты таблиц из монографии [13] показывают, что практически полезными являются только алгоритмы, время работы которых ограничено некоторой степенной функцией от размера задачи, причем такая ситуация не изменится со временем:

Таблица 0.1. Рост времени работы полиномиального и экспоненциального алгоритмов при росте размера задачи размер задачи функция 30 временной сложности 10 60 п* 0,0001 сек 0,0009 сек 0,0036 сек

2П 0,001 сек 17,9 мин 36600 лет размер задачи, решаемой за час совр. ЭВМ в 100 раз быстрее в 1000 раз быстрее п2 10 * iVi 31,6* iVi

2 п n2 n2 + 6.64 n2 + 9.97

Приведем формальное определение временной сложности алгоритма. Мы полагаем, что алгоритм Л решает некоторую массовую задачу Л4 — совокупность индивидуальных задач вида (*) (примеров) I Е Л4. Предполагая, что все входные данные записываются «разумным» способом (так, что длина записи каждого входного числа равна логарифму этого числа), обозначим через [/| длину записи примера I. Через Тд(/) обозначим число операций, выполняемых алгоритмом Л при решении примера I. Тогда под временной сложностью алгоритма понимается функция

Тл(п) = sup Тл{1)

1-.\1\—п

Алгоритм называется полиномиальным, если функция Тд(7г) растет как 0(р(п)), где р(п) — полиномиальная функция.

В силу изложенных соображений, при решении математической модели внимание исследователей операций главным образом сосредоточено на получении полиномиальных алгоритмов решения задачи.

По мере накопления опыта разработки полиномиальных алгоритмов было замечено, что для некоторых комбинаторных задач не удается построить полиномиальные алгоритмы точного решения, в то время как для других (часто похожих по формулировке задач) такие алгоритмы находятся без труда.

Классическим примером служат задача коммивояжера и задача о минимальном остовном дереве (см., например, [17]). Обе формулируются как задачи о нахождении в графе подмножества ребер минимального суммарного веса. В первом случае рассматриваются подмножества ребер, образующие гамильтоновы циклы, а во втором — остовные деревья. И несмотря на то, что для второй задачи множество допустимых решений имеет много большую мощность, существует простой полиномиальный алгоритм ее точного решения. Что же касается задачи коммивояжера, то полиномиальный алгоритм для нее до сих пор не построен, и большинство специалистов по исследованию операций склоняются к тому, что его вовсе не существует.

Для изучения степени сходства комбинаторных задач была предложена концепция полиномиальной сводимости. Задача Л4\ считается полиномиально сводимой к задаче М.^, если по любому примеру I £ Л41 можно за полиномиальное время построить пример I' G Л4.2, а по оптимальному решению у* примера V за полиномиальное время строится оптимальное решение х* примера I. В этом случае, если для решения задачи М.2 найдется полиномиальный алгоритм, это будет означать и полиномиальную разрешимость задачи

Концепция полиномиальной сводимости иллюстрирует применение одного из важнейших методов научного познания. Этим методом является сравнение объекта исследования с другими объектами, выделение их общих свойств и различий, что составляет основу систематизации. Изучение общности структуры дискретных экстремальных задач, построение сведений, выделение общих алгоритмических идей играют большую роль в развитии методов оптимизации.

Так, одним из важнейших открытий в исследовании операций стало нахождение Куком [25] подкласса задач распознавания, названного классом NP-полных задач, к которым полиномиально сводится любая задача из класса NP (неформально говоря, это класс задач, для которых существует полиномиальный алгоритм проверки правильности предъявленного решения для всех примеров с ответом «да»). Нахождение полиномиального алгоритма для некоторой NP-полной задачи означало бы полиномиальную разрешимость любой задачи класса NP, то есть означало бы равенство Р = NP. В настоящее время исследователи считают маловероятным положительный ответ на вопрос о совпадении классов Р и NP. Это делает проблематичным построение полиномиальных алгоритмов точного решения для NP-трудных задач (задач, к которым полиномиально сводятся NP-полные задачи распознавания). К сожалению, NP-трудными являются уже такие простые в своей постановке классические оптимизационные задачи, как задача коммивояжера, задача упаковки в контейнеры и даже задача о разбиении. Поэтому неудивительно, что при моделировании реальной задачи оптимизации исследователь операций, как правило, сталкивается с

NP-трудной задачей и едва ли может рассчитывать на построение точного полиномиального алгоритма.

В такой ситуации существует два принципиальных подхода, определяющих направления дальнейшего исследования задачи: выделение подзадач исходной массовой задачи, допускающих построение точного полиномиального алгоритма, и построение приближенных алгоритмов решения исходной задачи.

Подход с выделением полиномиально разрешимой подзадачи часто оказывается весьма привлекательным, поскольку массовая задача построенной математической модели может обладать чрезмерной общностью, в то время, как данные из задачи реального мира соответствуют более узкому подмножеству индивидуальных примеров, образующих более простую задачу. Следует заметить, однако, что не всегда частный случай трудной задачи оказывается существенно легче общего случая. Выделение полиномиально разрешимых подзадач представляет собой весьма нетривиальную проблему.

Алгоритмы приближенного решения в качестве своего результата выдают не оптимальное решение задачи, а некоторое допустимое решение, отличное от оптимального. Возникает естественный вопрос о степени близости получаемого решения к оптимальному. Если можно априорно установить эту степень, то говорят об алгоритмах с гарантированными оценками точности.

Обозначим через /д(/) значение целевой функции на решении, которое алгоритм Л находит для примера 7, а через f*(I) — значение целевой функции на оптимальном решении этого примера. Величину

Ш) - Г(1)

Л = SUp Тем оо называют величиной относительной погрешности алгоритма А ([31]).

Очевидно, качество приближенного алгоритма определяется близостью величины относительной погрешности к нулю. В лучшем случае NP-трудная задача допускает построение TVTAS или VTAS ((fully) polynomial time approximation scheme, [13]) — такого семейства полиномиальных алгоритмов, что для любого заданного е > 0 найдется алгоритм из этого семейства, что его относительная погрешность не превышает е. FVTAS обладает тем преимуществом, что указанный алгоритм полиномиально зависит не только от размера задачи п, но и от величины

Асимптотической относительной погрешностью называется величина '^K^fepl'6 м'171 -п)

Если е^д = 0, алгоритм называется асимптотически точным. Пользуясь этим определением, можно определить асимптотические схемы VTAS или J-VTAS аналогичным изложенному выше способом.

Не все задачи допускают построение приближенных алгоритмов со сколь угодно малой погрешностью. Существуют результаты, показывающие, в предположении Р ф NP, несуществование полиномиальных алгоритмов с относительной погрешностью меньшей, чем некоторая константа. Таким образом, наиболее точным результатом при анализе NP-трудной задачи является нахождение наименьшего е, для которого существует полиномиальный е-приближенный алгоритм и построение этого алгоритма.

Наряду с получением гарантированных оценок точности, большой интерес представляет также анализ алгоритма в среднем, поскольку примеры, на которых достигается оценка £д, могут не встречаться в реальных данных. В этом случае на множестве Л4 индивидуальных примеров задается вероятностная мера V, отражающая распределение реальных входных данных. Характеристики, подобные величине относительной погрешности £д(/) = (/а{1) — /*(-0)//*(-0> исследуются как случайные величины.

Одним из подходов к вероятностному анализу является нахождение классов вероятностных распределений, при которых алгоритм является асимптотически точным, т.е. почти всегда находит почти оптимальные решения на примерах большой размерности. Этот подход был впервые предложен в [12], и с тех пор получил широкое распространение (см., например,

Разобьем массовую задачу Л4 = U^:1Л4п на классы в соответствии с размерностью примеров (например, количеством вершин в задаче коммивояжера, количеством предметов в задаче упаковки и т.д.). Говорят, что алгоритм Л имеет оценки еп, 5п относительно вероятности V, если при любом п. Алгоритм Л называется асимптотически точным относительно вероятности V, если еп, 5п —» 0 при п —оо.

Наконец, нередкой является ситуация, когда для приближенного алгоритма решения NP-трудной комбинаторной задачи не удается обосновать гарантированные оценки точности. В этом случае говорят об эвристических алгоритмах. Решение, получаемое в результате работы этих алгоритмов,

43, 5, 6, 11, 8, 9]). может сколь угодно сильно отличаться от оптимального по значению целевой функции. Оценки качества таких алгоритмов могут быть получены посредством анализа результатов численных экспериментов.

В силу того, что в основе большинства реальных проблем лежат NP-трудные задачи, в последнее время разработке эвристических алгоритмов посвящены усилия большинства специалистов в области исследования операций. Интенсивно разрабатываются метаэвристики — общие алгоритмические идеи, такие, как генетический алгоритм, имитация отжига, поиск с запретами ([30]). Каждую из них можно «настроить» под конкретную задачу, опираясь на структурные свойства этой задачи, и превратить тем самым в эвристику.

Подобный подход хорошо зарекомендовал себя на практике — для задач, считающихся «крепкими орешками» в исследовании операций, для которых не удается построить алгоритмы с приемлемыми гарантированными оценками качества, эвристические алгоритмы порой находят решения, весьма близкие к оптимальным. Построение эвристических алгоритмов носит более прикладной характер — основной задачей при построении такого алгоритма является получение приемлемых результатов на базе тестовых примеров соответствующих прикладных задач.

Обобщая сказанное выше, приведем общую схему методологии исследования дискретной задачи оптимизации:

1. Установление сложностного статуса задачи (нахождение полиномиального алгоритма или доказательство NP-трудности).

2. Исследование структуры задачи, связи ее с другими известными комбинаторными задачами, в частности, в терминах полиномиального сведения.

3. Выделение наиболее общих полиномиально разрешимых подзадач.

4. Построение полиномиальных приближенных алгоритмов с гарантированными оценками точности. В идеале — нахождение нижней границы множества чисел допускающих построение ^-приближенного алгоритма.

5. Построение и анализ приближенных полиномиальных алгоритмов с оценками качества для решения задачи на случайных входных данных и, по возможности, обоснование условий асимптотической точности этих алгоритмов для различных вероятностных распределений на множестве примеров.

6. Построение полиномиальных эвристических алгоритмов, дающих малые погрешности на релевантных классах тестовых примеров.

Методы исследования, используемые в данной работе, соответствуют описанной схеме.

Предметом исследования диссертации являются задача календарного планирования с ограниченными ресурсами и задача выбора подмножества векторов с максимальной нормой суммы. Обе задачи имеют важное практическое значение.

Объединяет эти задачи связь с задачами упаковки. Исследованию этой связи посвящен, в частности, второй раздел первой главы. Задачи упаковки естественным образом делятся на два класса: в задачах первого класса, классическим представителем которого является задача упаковки в контейнеры ([23]), требуется разместить все предметы в как можно меньшее число контейнеров. Во втором классе, напротив, задано ограниченное число контейнеров, в котором требуется разместить только часть предметов, максимизировав их количество (или, в общем случае, их суммарную ценность). В этом классе центральным представителем служит задача о рюкзаке (knapsack problem, [26]). Первая из рассматриваемых задач обобщает задачу упаковки в контейнеры, вторая — задачу о рюкзаке.

Первая глава посвящена задаче календарного планирования с ограниченными ресурсами (в зарубежной литературе фигурирует как RCPSP — resource-constrained project scheduling problem). Модель впервые была сформулирована в 1969 году [41] и давно стала классическим представителем труднорешаемых задач комбинаторной оптимизации. Она обладает простой и вместе с тем имеющей достаточную общность постановкой и возникает во многих реальных приложениях, связанных с планированием проектов — совокупностей работ, направленных на достижение некоторой цели и использующих общие ограниченные ресурсы. Помимо проектного управления примерами применения модели RCPSP являются задачи автоматического распределения работ при вычислении на параллельных процессорах и другие прикладные задачи.

RCPSP является NP-трудной в сильном смысле [28]. Более того, в работе [42] показано, что частным случаем RCPSP является задача вершинной раскраски графа, откуда, в частности, следует (при условии Р ф NP) несуществование полиномиального приближенного алгоритма с оценкой погрешности меньшей, чем пЕ для некоторого е > 0. Авторы обзора [39] называют RCPSP одной из самых сложных задач исследования операций.

О высокой сложности этой задачи говорят и факты из области численных экспериментов: к настоящему моменту [37] в самой известной библиотеке тестовых примеров для RCPSP — PSPLIB, содержащей приблизительно по 500 тестов с 30, 60 и 120 работами, оптимальные решения для некоторых тестов с 120 и даже 60 работами до сих пор неизвестны.

В силу высокой сложности RCPSP является отличным объектом для испытания различных эвристических алгоритмов, а также для поиска подзадач, позволяющих получить алгоритмы с оценками.

Так, например, простой частный случай RCPSP — с пустым графом предшествования, одним типом ресурсов и единичными длительностями работ — представляет собой задачу упаковки в контейнеры. Для этой задачи удалось построить асимптотическую TVTAS ([35]).

Задачи упаковки, особенно двумерной и трехмерной ([20, 22, 29]), также являются чрезвычайно востребованными в приложениях, таких как логистика (например, оптимальная загрузка транспорта) и производство (например, при нахождении оптимального раскроя материала).

Первый раздел главы посвящен постановке задачи календарного планирования, а также ее обобщений, которые учитывают задержки, связанные с ограничениями предшествования; времена появления работ в проекте; директивные сроки; ресурсы с переменными выделением и потреблением; мультимодальное исполнение работ; складируемые и невозобновимые ресурсы и другие.

Задачи планирования и упаковки безусловно являются подходящими кандидатами для сравнительного анализа. Обе модели имеют дело с набором объектов, использующих некоторые ограниченные ресурсы (в случае задач упаковки этим ресурсом служит свободное место в контейнерах). В заключительной части раздела приводится обзор известных результатов о сравнении задач планирования и упаковки.

Во втором разделе главы рассматривается частный случай RCPSP — задача с одним типом ресурсов и без ограничений предшествования. Данная задача оказывается естественным образом связанной с задачей упаковки в полосу ([20]). Действительно, между входными данными примеров этих задач имеется взаимнооднозначное соответствие, а требование ресурсного ограничения естественным образом отвечает требованию непересечения прямоугольников в полосе. Тем не менее, задачи не являются эквивалентными. Более точно, указанный частный случай задачи RCPSP является релаксацией задачи упаковки в полосу. В развитие работ [4, 18] исследуется вопрос о максимальном различии оптимальных значений этих задач на всем множестве примеров, а также асимптотическое различие на множестве «больших» примеров.

Основными результатами раздела является установление верхних оценок этих величин, а также построение примера с шириной полосы, равной восьми, для которого оптимумы задач равны, соответственно, четырем и пяти. Показано, что данный пример является самой компактной иллюстрацией нижней оценки величины максимального различия оптимумов.

В третьем разделе рассматривается применение модификации алгоритма формирования связок Гимади и Залюбовского к мультипроектно-му случаю RCPSP с одним ресурсом со случайными входными данными. Предложена естественная процедура формирования случайных входных данных задачи. Проводится вероятностный анализ предложенного алгоритма, в частности, устанавливаются условия его асимптотической точности.

Четвертый раздел посвящен опыту решения прикладных задач с применением эвристических алгоритмов.

В первой части описывается программная библиотека LSE (Ledas Scheduling Engine) — вычислительное ядро для решения задач календарного планирования, в создании которого автор принимал непосредственное участие. Описываются реализованные в нем алгоритмы, позволяющие решать как классическую задачу, так и обобщения, рассмотренные в первом разделе (для задач с директивными сроками не гарантируется нахождение допустимого решения). Алгоритмы основаны на методе последовательной укладки работ в расписание ([36]).

Также описывается пример внедрения библиотеки в приложение — систему планирования собраний "Freetime". В связи с данным приложением рассматривается задача «натурального перепланирования». Вход данной задачи дополнен множеством = l,.iV}, представляющим некоторое начальное (возможно, недопустимое) расписание. Требуется найти допустимое расписание, имеющее минимальный суммарный сдвиг работ по сравнению с входным расписанием. Предложен эвристический алгоритм решения этой задачи.

В заключительной части раздела рассматривается опыт применения алгоритмов для решения RCPSP в проекте строительства ВосточноСибирского нефтегазового комплекса. Исследуется модель со стохастическим графом предшествования. Предложен линейный алгоритм розыгрыша данной стохастической модели, а также метод статистического прогнозирования сроков окончания проекта.

Вторая глава посвящена задачам выбора подмножества векторов в многомерном евклидовом пространстве.

Основные результаты посвящены следующей задаче га-ПВ («Подмножество из т векторов»): Задано конечное семейство векторов V = {v1: гГ2,., vn} в евклидовом пространстве Rk и натуральное число т < п. Требуется найти подсемейство векторов из V мощности т, обладающее максимальной нормой суммы.

Эта задача возникает при решении прикладной задачи обнаружения квазипериодически повторяющегося фрагмента в зашумленной числовой последовательности при заданном числе повторов. Подобная ситуация типична для таких приложений, как электронная разведка, радиолокация, телекоммуникация, геофизика, обработка речевых сигналов, медицинская и техническая диагностика и др. (см. [10, 15, 14]). Поэтому разработка алгоритмов решения таких задач имеет высокое практическое значение.

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

Действительно, векторы можно представлять себе как предметы, имеющие единичный вес, при вместимости рюкзака, равной т. При этом целевая функция, определяющая ценность подмножества предметов, имеет более сложную — нелинейную (и даже неаддитивную) форму. Каждый предмет обладает набором характеристик, выражаемых компонентами вектора. Наибольшую ценность представляет такое сочетание предметов, при котором максимизируется вклад всех характеристик (в евклидовой метрике).

Задача о рюкзаке, является одной из самых простых NP-трудных задач. Для нее раньше всех других задач была построена TVT AS ([33]). Кроме того, для этой задачи существует псевдополиномиальный (т.е. полиномиально зависящий от значений входных данных) алгоритм точного решения, основанный на методе динамического программирования ([40]).

В первом разделе главы приводится постановка задачи m-ПВ и некоторых ее модификаций, и излагается связь задачи с задачей апостериорного («оффлайн») обнаружения повторяющегося фрагмента в зашум-ленной сети.

Также приводятся известные ранее результаты. Исследования задачи га-ПВ начались относительно недавно. В 2002 году в работе [15] была описана связь этой задачи с прикладными задачами распознавания. В 2007 году в статье [2] установлена NP-трудпость задачи и предложена TVT AS для подзадач с фиксированной размерностью пространства Rk, а также следующий из нее псевдополиномиальный алгоритм.

NP-трудность задачи была доказана для общего случая задачи, с использованием больших размерностей пространства векторов. Ставится вопрос о сложностном статусе задачи при фиксированном к.

Во втором разделе проводится построение точных псевдополиномиальных при фиксированной размерности пространства алгоритмов решения целочисленной задачи m-ПВ и её обобщения ПВО. Алгоритмы, аналогично классическим псевдополиномиальным алгоритмам для задачи о рюказке, основаны на применении динамического программирования. Они больший модуль компонент входных векторов, улучшающую трудоемкость алгоритмов, предложенных в [2].

Решение целочисленного случая имеет высокое прикладное значение, поскольку задачи распознавания обыкновенно связаны с компьютерной обработкой. Ограничения на разрядность вычислительных процессоров позволяют любые задачи с цифровыми входными данными расматривать как целочисленные.

В третьем разделе приводится полиномиальный при фиксированной размерности пространства алгоритм точного решения задачи m-ПВ с временной сложностью, равной 0(к2п2к). Тем самым положительно разрешается вопрос, поставленный в первом разделе главы.

Идея алгоритма основана на сведение ^-мерной задачи к решению конечного набора одномерных задач нахождения т максимальных проекций на некоторые направления. При построении этого конечного набора направлений существенную роль играет лемма из работы [3]. Лемма была использована авторами указанной статьи для построения алгоритма решения задачи ПВ. Задача ПВ имеет аналогичную задаче m-ПВ постановку, но без задания входного параметра т: мощность выбираемого подмножества может быть любым. Любопытным фактом является то, что задача ПВ рассматривалась в работе [3] в связи с совершенно другой прикладной задачей, связанной с экономикой производства.

В четвертом разделе, в развитие алгоритмических идей статьи [2], имеют временную трудоемкость, равную наиприводится простой рандомизированный алгоритм решения задачи, также полиномиальный при фиксированной размерности пространства, однако обладающий значительно меньшей трудоемкостью 0(nk3/2 lnfc п). Доказывается его асимптотическая точность. Целесообразность применения этого алгоритма заключается в простоте его реализации и меньшей временной сложности по сравнению с детерминированными точными алгоритмами.

Таким образом, основным результатом главы является построение псевдополиномиального и полиномиального при фиксированном к алгоритмов точного решения задачи m-ПВ. Псевдополиномиальный алгоритм обладает лучшей по сравнению с полиномиальным трудоемкостью при условии, что 2тЬ < п2.

Основные результаты диссертации докладывались на международных научных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, 2004, 2005, 2006), на Всероссийских конференциях «Методы оптимизации и экономические приложения» (Омск, 2006, 2009), на Международных конференциях по исследованию операций «Optimal Discrete Structures and Algorithms» (Росток, 2006), «Operations Research» (Карлсруэ, 2006; Аугсбург, 2008), «European Conference on Operational Research» (Прага, 2007; Бонн, 2009), «Combinatorial Optimization» (Ковентри, 2008), на научных семинарах Института математики и механики УрО РАН, Института математики им. C.JI. Соболева СО РАН.

1. Задача календарного планирования в условиях ограниченных ресурсов

1.1. Постановка задачи

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Рыков, Иван Александрович

Заключение

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

В работе получены следующие основные результаты.

1. Улучшена верхняя граница для величины, характеризующей максимальное различие оптимумов задачи упаковки в полосу и частного случая задачи календарного планирования с ограниченными ресурсами. Также получена верхняя оценка величины, характеризующей асимптотическое, при росте числа работ в примере, различие оптимумов этих задач.

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

3. Построен полиномиальный приближенный алгоритм решения муль-типроектной задачи календарного планирования с одним типом ресурса. Представлены условия его асимптотической точности на случайных входных данных.

4. Для задачи выбора подмножества векторов заданной мощности с максимальной нормой суммы построен алгоритм с временной сложностью 0(к2п2к), где та — число векторов, из которых производится выбор, к — размерность евклидова пространства. Тем самым, установлена полиномиальная разрешимость задачи при фиксированной размерности пространства.

5. Для целочисленного случая указанной задачи построен точный алгоритм Ad, имеющий трудоемкость О (kmn(2mb)k~l^j, где т — мощность выбираемого подмножества, и все компоненты векторов по модулю не превосходят Ь. Алгоритм является псевдополиномиальным при фиксированном к и обладает лучшей по сравнению с алгоритмом Ар трудоемкостью при условии, что 2mb < та2.

Благодарности

Автор выражает искреннюю признательность своему научному руководителю Эдуарду Хайрутдиновичу Гимади за неоценимую поддержку и постоянное внимание к работе. Также хотелось бы поблагодарить сотрудников отдела теоретической кибернетики ИМ СО РАН за плодотворные встречи и обсуждения: Бабурина А.Е., Глазкова Ю.В., Глебова А.Н., Кель-манова А.В., Пяткина А.В., Севастьянова С.В.

Отдельную благодарность выражаю своим родным — Штатнову Ю. В., Штатновой Т. И., Рыковой Е. Ю. и Рыковой М.А. за любовь и поддержку во всех начинаниях.

Список литературы диссертационного исследования кандидат физико-математических наук Рыков, Иван Александрович, 2009 год

1. Ахо А., Хопкрофт Дою., Ульман Дою. Построение и анализ вычислительных алгоритмов // Мир, Москва, 1979.

2. Бабурин А. Е., Гимади Э. X., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет, анализ и исслед. операций, Серия 2. 2007. Т. 14, N 1. С. 22-32.

3. Бабурин А. Е., Пяткин А. В. О полиномиальных алгоритмах решения одной задачи суммирования векторов // Дискрет, анализ и исслед. операций, Серия 1, 2006, Т. 13, N 2. С. 3-10. 106.

4. Гимади Э. X. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Тр. АН СССР. Сиб. Отд-ние. Ин-т математики, Новосибирск: Наука. 1988. Т. 10. С. 89-115.

5. Гимади Э. X., Глебов Н. И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука. 1975. № 31 С. 35-42.

6. Гимади Э.Х., Глебов Н.И., Сердюков А.И. Алгоритм для приближенного решения задачи коммивояжера и его вероятностный анализ // Сиб. жури, исслед. опер. 1994. Т. 1 № 2. С. 8-17.

7. Гимади Э.Х., Залюбовский В.В., Севастьянов С.В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками. // Дискрет, анализ и исслед. операций, Серия 2. 2000. Т. 7, № 1. С. 9—34

8. Гимади Э. X., Залюбовский В. В. Задача упаковки в контейнеры: асимптотически точный подход // Известия высших учебных заведений. 1997. № 12. С. 23-36.

9. Гимади Э. X., Залюбовский В. В., Шарыгин П. И. Задача упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. 1997. № 12. С. 37-49.

10. Гимади Э. X., Сердюков А. И. Аксиальные трехиндексные задачи о назначении и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия высших учебных заведений. 1999. № 12. С. 19-25.

11. Гимади Э. X., Перепелица В. А. К задаче нахождения минимального га-мильтонова контура на графе со взвешенными дугами // Дискретный анализ: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР. 1969. № 15 С. 57-65.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.

13. Кельманов А. В. Проблема off-line обнаружения квазипериодически повторяющегося фрагмента в числовой последовательности. // Тр. ИММ. 2008. 14(2). С. 81-88.

14. Келъманов А. В., Хамидуллин С. А., Околънишникова JI. В. Апостериорное обнаружение одинаковых подпоследовательностей-фрагментов в квазипериодической последовательности // Сиб. журн. индустриальной математики. 2002. Т. 5, № 2(10). С. 94-108.

15. Кельманов А. В., Пятпкин А.В. Об одном варианте задачи выбора подмножества векторов // Дискрет, анализ и исслед. операций, 2008, Т. 5, № 15. С. 20-34.

16. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность // М: Мир, 1985.

17. Шарыгин П. И. Оценки приближенного решения одной задачи календарного планирования // Дискрет, анализ и исслед. операций. 1995. Т. 2, № 1. С. 57-67.

18. Baker В. S., Brown D. J., Kartseff Н. P. А 5/4 algorithm for two-dimensional packing // J. of Algorithms. 1981. N 2. P. 348-368.

19. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions // SI AM Journal on Computing. 1980. N 9. P. 846.

20. Bellman R. Dynamic programming // Adaptive Control Processes, A Guided Tour, 1961.

21. Chung F. R. K., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM Journal on Algebraic and Discrete Methods. 1982. N 3. P 66.

22. Coffman E. G., Garey M. K., Johnson D. S. Approximation algorithms for bin-packing. — An updated survey // Algorithm Design for Computer System Design. 1984. N 284. P. 49-106.

23. Coffman E. G., Garey M. K., Johnson D. S., Tarjan К. E. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. on Computing. 1980. V. 9, N 4. P. 808-826.

24. Cook S.A. The complexity of theorem-proving procedures // Proceedings of the third annual ACM symposium on Theory of computing. 1971. P. 151-158.

25. Dantzig G.B. Discrete-variable extremum problems j j Operations Research. 1957. P. 266-277.

26. Garey M. R., Graham R. L., Johnson D. S., Yao A. C.-C. Resource constrained scheduling as generalized bin packing // J. Combinatorial Theory. 1976. V. A, N 21. P. 251-298.

27. Garey M.R., Johnson D.S. Complexity results for multiprocessor scheduling under resource constraints // SIAM Journal on Computing. 1975. N 4. P. 397.

28. Gehring H., Menschner K., Meyer M. A computer-based heuristic for packing pooled shipment containers // European Journal of Operational Research. 1990. 44(2) P. 277-288.

29. Gonzalez T.F. Handbook of approximation algorithms and metaheuristics // Chapman & Hall/CRC, 2007.

30. Graham R.L. Bounds on multiprocessing anomalies and related packing algorithms // Proceedings of fall joint computer conference. 1971. P. 205217.

31. Hartmann S. Packing problems and project scheduling models: an integrating perspective. // J. of Operational Research Society. 2000. N 51. P. 1083-1092.

32. Ibarra O.H., Kim C.E. Fast approximation algorithms for the knapsack and subset sum problems // Journal of the ACM. 1975. 22(4) P. 463-468.

33. Johnson D. S., Demers A., Ullman J. D., Garey M. R., Graham R. L. Worst-case performance bounds for simple one-dimensional packing algorithms. // SIAM J. on Computing. 1974. V3 N 4. P. 299-325.

34. Karmarkar N., Karp R.M. An efficient approximation scheme for the one-dimensional bin-packing problem // Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. 1982. P. 312-320.

35. Kelley, J.E. The critical-path method: Resource planning and scheduling. // Industrial Scheduling. 1963.

36. Kolisch R., Hartmann S. Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. // European J. of Operational Research. 2005. N 9. P. 320-333.

37. Kolish R. Serial and Parallel resource-constrained project scheduling methods revisited: Theory and computation // European Journal of Operational Research. 1996. N 90. P. 320-333.

38. Mohring R.H., Schulz A.S., Stork F., Uetz M. Solving project scheduling problems by minimum cut computations // Management Science. 2003. P. 330-350.

39. Papadimitriou C.H. On the complexity of integer programming // Journal of the Assoclauon for Compuung Machinery. 1981. 28(4). P. 765-768.

40. Pritsker A.A., Watters L., Wolfe P. Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach // Management Science. 1969. N 16. P. 93-107.

41. Schaffier M. W. Scheduling with forbidden sets // Discrete Applied Mathematics. 1997. 72(1-2). P. 155-166.

42. Slominski L. Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations // Computing. 1982. 28(3) P. 257-267.

43. Публикации автора по теме диссертации1. Статьи в журналах

44. Гимади Э.Х., Глазков Ю.В., Рыков И.А. О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве // Дискретный анализ и исследование операций. 2008. Т. 15. № 4. С. 30-43.

45. Гимади Э.Х., Пяткин А.В., Рыков И.А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 11-19.

46. Рыков И. А. О сравнении задачи упаковки в полосу с одной задачей календарного планирования // Дискретный анализ и исследование операций. 2008. Т. 15. № 4. С. 57-73.

47. A. Ershov, I. Ivanov, V. Kornienko, S. Preis, A. Rasskazov, I. Rykov A new scheduling engine for PLM // International Journal of Product Life-cycle Management. 2006. V. 1. № 2. C. 164-180.1. Прочие публикации

48. Ершов А., Иванов ИКорниенко В., Прейс С., Рассказов А., Рыков И. LSE: Новое вычислительное ядро системы планирования ledas scheduler 3.0 и перспективы его использования. // Препринт. Новосибирск, ЗАО ЛЕДАС. 2005. 38 с.

49. Ершов А., Корниенко В., Прейс С., Рассказов А., Рыков И., Ушаков Д. Обзор возможностей системы планирования Freetime. // Препринт. Новосибирск, ЗАО ЛЕДАС. 2005. 24 с.

50. Рыков И.А. Промышленные алгоритмы для задачи календарного планирования с ограниченными ресурсами. // Мат. XLIII Международной научной студ. конф. «Студент и научно-технический прогресс»: Математика. НГУ, Новосибирск. 2005. С. 212-213.

51. Рыков И.А. Задача упаковки в полосу как релаксация задачи календарного планирования с ограниченными ресурсами. // Мат. XLIV Международной научной студ. конф. «Студент и научно-технический прогресс»: Математика. НГУ, Новосибирск. 2006. С. 210-211.

52. Рыков И. А. Алгоритмы приближенного решения задачи календарного планирования. // Мат. Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск. 2006. С. 121.

53. Гимади Э.Х., Залюбовский В.В., Пляскина Н.И., Рыков И.А. Вероятностные аспекты планирования нефтегазового комплекса ВСНГК // Мат. Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск. 2009. С. 221

54. Рыков И. А. Приближенный алгоритм решения мультипроектпой задачи календарного планирования с ограниченными ресурсами на случайных входах // Мат. Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск. 2009. С. 161

55. Gimadi E., Glazkov Y., Rykov I. On Subset Vector Problem with Maximal Euclidean Norm of Sum // Abstracts of International Conference on Operation Research, Augsburg. 2008. P. 210-211.

56. Rykov I. Solving RCPSP using relaxation with consumable resources // Abstracts of International Conference on Operations Research, Bremen. 2005. P. 178

57. Rykov I. Polynomial approximation algorithms for solving resource-constrained project scheduling problem // Electronic Notes in Discrete Mathematics, Elsevier. 2006. V. 27. P. 93-94.

58. Rykov I.A. Approaches to solving RCPSP using Relaxed Problem with Consumable resources // Operations Research Proceedings 2006, Springer Berlin Heidelberg. 2007. P. 547-552

59. Rykov I. Asymptotically exact approach for solving RCPSP with single resource // Abstracts of European conference on Operational Research, Prague. 2007. P. 83

60. Rykov I. Asymptotically exact approach to solving RCPSP with one resource type // Abstracts of International Symposium on Combinatorial Optimization, Coventry. 2008. P. 74

61. Rykov I. Polynomial optimal algorithm for solving subset vector problem in the space with fixed dimension. // Abstracts of European conference on Operational Research, Bonn. 2009. P. 225