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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

На правах рукописи

РЫКОВ Иван Александрович

АЛГОРИТМЫ С ОЦЕНКАМИ КАЧЕСТВА ДЛЯ ЗАДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ, УПАКОВКИ И ВЫБОРА ПОДМНОЖЕСТВА ВЕКТОРОВ

(01.01.09 - дискретная математика и математическая кибернетика)

Автореферат ^ ^ О Н1 /[¡{¡д

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2009

003480322

Работа выполнена в Учреждении Российской академии наук Институте математики им. С. Л.Соболева Сибирского отделения РАН.

Научный руководитель: д.ф.-м.н., профессор Э. X. Гимади Официальные оппоненты: д.ф.-м.н., профессор В. К. Попков

к.ф.-м.н. А. Н. Глебов Ведущая организация: Омский Государственный Университет

Защита состоится 11 ноября 2009 г. в 15 часов на заседании диссертационного совета Д.003.015.01 при Учреждении Российской академии наук Институте математики им. С. Л. Соболева СО РАН (пр. Академика Коп-тюга, 4, 630090 Новосибирск).

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института математики СО РАН.

Автореферат разослан

октября 2009 г.

"Ученый секретарь диссертационного совета доктор физ.-мат. наук

Ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ1

Актуальность темы.

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

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

Задача календарного планирования с ограниченными ресурсами возникает во многих реальных приложениях, связанных с планированием проектов — совокупностей работ, направленных на достижение некоторой цели и использующих общие ограниченные ресурсы. Несмотря на достаточно простую постановку задачи, данная модель является одной из самых сложных задач исследования операций [13]. Она МР-трудна в сильном смысле. В связи с высокой прикладной значимостью, для решения этой задачи предложено множество алгоритмов приближенного решения. Однако в своем большинстве они являются эвристическими, и оценки их качества основаны на результатах численных экспериментов.

Задача выбора подмножества векторов с максимальной нормой суммы возникает при поиске повторяющегося фрагмента в зашумленной числовой последовательности. Эта задача играет важную роль в таких приложениях, как электронная разведка, радиолокация, телекоммуникация, геофизика, обработка речевых сигналов, медицинская и техническая диагностика и др. (см. [4, 7, 6]). Задача выбора подмножества векторов также является КР-трудной.

Продуктивным подходом к исследованию №Р-трудных задач является выделение подклассов задачи, допускающих построение полиномиальных точных алгоритмов. Также при решении МР-трудных задачи важное значение приобретают эффективные приближенные алгоритмы с гарантированными оценками качества. Обозначим через /д(/) значение целевой функции на решении, которое алгоритм Л находит для примера I, а через /* (/) — значение целевой функции на оптимальном решении этого примера. Величину ел — ьир{(/А(1) -/*(/))//*(/)€ -М} называют величиной относительной погрешности алгоритма Л. Здесь через М мы обозначаем «массовую задачу» — множество примеров, т.е. задач с конкретными входными данными, к которым применим алгоритм Л.

Работа поддержана грантами РФФИ (проекты 08-01-00516 и 07-07-00022)

Величина £_а характеризует поведение приближенного алгоритма в худшем случае. Большой интерес представляет также вероятностный анализ алгоритма на случайных входных данных. Одним из подходов является рассмотрение такой характеристики качества работы алгоритма, как вероятность его несрабатывания т.е. доля случаев, когда алгоритм не обеспечивает анонсированную оценку относительной погрешности ед. Этот подход был впервые предложен в [5], и с тех пор получил широкое распространение (см., например, [14]). Особый интерес представляет нахождение условий асимптотической точности, т.е. таких условий на распределение входных данных, при котором оценки и 8.д одновременно стремятся к нулю с ростом размера задачи.

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

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

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

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

Разработка программного модуля и оценка качества эвристических алгоритмов осуществлялась с использованием языка программирования С++.

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

Практическая ценность. Разработанная коммерческая библиотека

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

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

Основные результаты.

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

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

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

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

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

при фиксированном к и обладает лучшей по сравнению с алгоритмом Ар трудоемкостью при условии, что 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. Соболева СО РАН.

Публикации. По теме диссертации автором опубликовано 19 работ, из них 4 публикации в научных журналах, 2 препринта и 13 публикаций в трудах и тезисах конференций. Конфликт интересов с соавторами отсутствует.

Структура и объем работы. Диссертация изложена на 115 страницах, содержит введение, две главы, заключение, благодарности и список литературы, содержащий 61 наименование.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

Рассматривается случай (далее обозначаемый как RCSP) с пустым графом предшествования и одним типом ресурса. Математическая модель

для этого случая выглядит следующим образом:

maxf.s,- + L) jeJ J 3

min

s3ez+

£ Щ < W, t = 1,2...

jeA(s,t)

(здесь W — интенсивность выделения ресурса, Wj — интенсивности потребления ресурса работами, lj — длительности работ; A(S, t) = {j \Sj < t < Sj + lj} — множество работ, выполняющихся в интервале времени t).

Построение расписания представляется в виде расположения в полубесконечной полосе ширины W прямоугольников с длиной lj (ориентированной вдоль полосы) и шириной wj. При этом непересечение прямоугольников между собой и с границами полосы означает соблюдение ресурсного ограничения: в каждый момент времени суммарная ширина выполняемых работ (интенсивность потребления ресурса) не превышает ширины полосы (интенсивности выделения ресурса). Таким образом, имеется взаимнооднозначное соответствие между входными данными примеров этой задачи и известной двумерной задачей упаковки в полосу ([10], далее обозначаемой SPP — strip packing problem). Однако, представление работ в виде прямоугольников накладывает дополнительное ограничение на работы. В исходной постановке задачи RCSP работам не предписано использование одних и тех же единиц ресурса в течение времени выполнения, поэтому работа может быть представлена в виде lj прямоугольников единичной длины, уложенных последовательно друг за другом в полосу.

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

Введем следующие обозначения.

SPP'{L)

Р ~ SlP RCSP*(L)'

Pa = sup

{

SPP*(L)

RCSP*(L)

L — такие, что

RCSP*(L)

'max (L)

р0о = lim Р\,

где L — произвольный вход для обеих задач, a /ma)t(L) — наибольшая из длин прямоугольников во входе.

Таким образом, величина р характеризует максимальное отличие оптимальных значений задач на всем множестве входных примеров, а величина рос ~ различие на множестве «больших» примеров, т.е. примеров с большим числом работ.

Доказана следующая теорема.

Теорема 1.1 Для величин р и рс*, имеют место оценки

Верхние оценки в теореме доказаны с использованием анализа приближенных алгоритмов из работ [11] и [9]. Показано, что нижние оценки оптимума SPP* (L) для этих алгоритмов являются также нижними оценками для RCSP*(L).

Нижняя оценка для величины р была доказана ранее в работе [8]. В диссертации для этой оценки построен более компактный пример и доказана его минимальность.

1,25 <р< 2,7;

1 < Рос < 1,25.

8

а

7

6

с

h /

5

4

3

2

9

Ь

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

Теорема 1.2 Оптимальная упаковка для приведенного примера имеет длину, равную пяти.

Теорема 1.3 Для любого примера Ь с вектором (оптимальная длина расписания, ширина полосы), лексикографически меньшим (4, 8), оптимальные значения НСБР^Ь) и ЭРР(Ь) совпадают.

Из теоремы 1.2 следует, что данный пример служит доказательством неравенства | < р, а теорема 1.3 показывает, что этот пример минимален для лексикографического упорядочения примеров по длине оптимального расписания и ширине полосы.

В разделе 1.3 рассматривается мультипроектная постановка задачи календарного планирования с одним ресурсом, когда граф предшествования состоит из нескольких компонент связности.

Предложен следующий алгоритм решения данной задачи:

1. В каждом проекте выбрать нумерацию прямоугольников, согласованную с ограничениями предшествования ((г,у) £ Е => пит(г) < пит{з)). Пусть М/с — число работ в к-ом проекте, Мтах = тах{М*;}.

к<т

2. Для каждого г = 1,... Мтах упаковать все прямоугольники с номером г алгоритмом И/Г-связок Гимади и Залюбовского [3]. Границу полученной упаковки считать основанием для упаковки прямоугольников со следующим номером.

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

• Количество работ п и количество проектов т считаются детерминированными входными данными.

• Каждая из работ распределяется (случайным или детерминированным образом) в один из проектов.

• В каждом из проектов на множестве работ задается орграф без циклов (случайным или детерминированным образом).

• Независимо каждая из работ получает длину 13 € {1... L} и ширину Wj € {1... W} в соответствии с дискретным распределением, заданным матрицей (pwi).

Матрицу А — (awi) назовем Ж-асимметричной если V/ е {1... L}, Vw € {1... [W/2\}, pw,i < P(w-w),i-

Пусть на множестве примеров М задана вероятностная мера V и пусть массовая задача М. = U^Lj-M,, разбита на классы в соответствии с размерностью примеров. Алгоритм называется асимптотически точным относительно вероятности V, если существуют последовательности еп, Sn —> О при п —> ос, такие, что

Доказана следующая теорема.

Теорема 1.4 Пусть имеется т проектов, число работ в каждом из них одинаково. Пусть матрица (pwh) W-асимметрична. Тогда при условиях п = mlnm uWL — о(ln m) алгоритм Aspp асимптотически точен.

В разделе 1.4 излагается опыт участия в прикладных проектах, связанных с решением задач планирования. Описываются эвристические алгоритмы, реализованные в коммерческой библиотеке LSE [19], позволяющие решать как классическую задачу, так и обобщения, рассмотренные в разделе 1.1 (для задач с директивными сроками не гарантируется нахождение допустимого решения, поскольку эта задача NP-трудна). Алгоритмы основаны на методе последовательной укладки работ в расписание [12].

Приводится постановка «задачи натурального перепланирования», возникающая во многих приложениях. Вход данной задачи дополнен множеством {8j\j = 1....JV}, представляющим некоторое начальное (недопустимое) расписание. Требуется найти допустимое расписание, имеющее минимальный суммарный сдвиг работ по сравнению с входным расписанием. Описан эвристический алгоритм решения этой задачи, реализованный в модуле LSE, а также представлена система планирования собраний "Freetime" как пример приложения, где востребовано решение этой задачи.

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

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

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

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

Задача т-ПВ («ПОДМНОЖЕСТВО ВЕКТОРОВ с максимальной нормой суммы»): Задано конечное семейство векторов V = {г>х, у2,..., в евклидовом пространстве Ик и натуральное число т < п. Требуется найти подсемейство векторов из V мощности т, обладающее максимальной нормой суммы.

Под нормой здесь и далее понимается евклидова норма в А>мерном пространстве М*, т. е. ||х|| = + ... +

Задача ПВО («т-ПВ с ОГРАНИЧЕНИЕМ»): Задано конечное семейство векторов V — {#1, щ, •. -,уп} в евклидовом пространстве Як и натуральные числа т и I, удовлетворяющие условию 1т < п. Требуется выделить в V подсемейство векторов X = {г>а1, ьа2,..., ьЛт }, обладающее максимальной нормой суммы, при соблюдении ограничений на номера соседних векторов выделенного подсемейства:

а;+1 — йг>1 для г = 1,2,..., т — 1.

Задача т-ПВ является частным случаем задачи ПВО (с / = 1).

Обсуждается постановка задачи ПВО как задачи обнаружения квазипериодического фрагмента в зашумленной числовой последовательности ([7]), включающей передачу т повторений фрагмента и — (щ,... иь) можно представить как X = (х\,.. . хп+А;-_1), где хг — иг-г,, г =

1,..., п + т — 1, = 0, если г — г^ Ф 0,..., к — 1. Принимающая сторона наблюдает вектор У = X + Е, где Е = (еь... еп+к-1), e¡ е Фо,^ — независимые одинаково распределенные гауссовские случайные величины. Обнаружение по критерию максимального правдоподобия приводит к минимизации функционала

5(А-(»ь ..., гт, и)) = ||У - Х(н,.. . ,гт, [1)\\2. где 11 После минимизации 5 по II получаем задачу

тем

где Yi = (уг,... у1+к-\), что равносильно задаче ПВО (условие аг+1 — аг > I для I = к соответствует непересечению фрагментов).

Приводятся полученные ранее результаты. МР-трудность задачи ПВО показана в работе [4], МР-трудность задачи т-ПВ — в работе [1]. Также в работе [1] построен алгоритм решения задачи т-ПВ с величиной относительной погрешности, равной (к - 1)/(8£2), и временной сложностью о(пк2(2Ь где Ь — параметр алгоритма. Этот алгоритм предо-

ставляет полиномиальную аппроксимационную схему при фиксированной размерности к. Также на основе этого алгоритма получен псевдополиномиальный при фиксированном к алгоритм точного решения целочисленной задачи т-ПВ с трудоемкостью 0(пк2{ктЬ)к~1), где Ь — максимальная по абсолютной величине координата векторов из семейства V.

Ставится вопрос о сложностном статусе задачи при фиксированном к.

В разделе 2.2 предлагается псевдополиномиальный алгоритм решения целочисленной постановки задач т-ПВ и ПВО, имеющий лучшую по сравнению с алгоритмом из [1] оценку временной сложности.

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

Пусть строки матрицы («¡¿) образованы векторами У\,...ьп. Пусть В £ 2+-1 — вектор с компонентами В; = 1'г,ст,(г), 1 < г < /с, где а г — перестановка, упорядочивающая элементы («¿1, • ■• • Уы) ¿-й строки матрицы (и^) по невозрастанию (т.е., В* — сумма т максимальных

значений г'-ой строки). В = {/? € Ь < (3 < В}. Для элементов

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

Теорема 2.1 Пусть х*(/3) и /тп(/3) — соответственно, оптимальное решение и значение оптимума следующей задачи

Е сзхз 3 = 1

тах

£ УцХз = 1 < г < к; -

з=1 (1)

П

£ щ = т;

3 = 1

X, е {0,1}, 1 < э <п.

Пусть /3* — оптимальное решение задачи

X? ^ + ¡1п(Р) - тах (2)

/3 &В.

Тогда х*(6*) — оптимальное решение задачи ПВ с целочисленными координатами векторов.

Для решения одномерной задачи 1 достаточно решить две задачи с тем же набором ограничений и линейными целевыми функциями с^х^ и

12] = \(~сз)хг

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

и

£ c.jXj —> шах ¿=1

V

£ и^Х] = , 1 < г < /с; .7 = 1

I'

Е X] = м;

7 = 1

х, € {0,1}: l<j<v.

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

Лемма 2.1. Для всяких /3 6 В верны следующие рекуррентные соотношения:

[О, если (3 = 0, 1о,ЛР) ~ N для всех V = 1,..., п; (3)

I — ос, иначе,

им =

£ Сг, если

г=1 г=1 для всех ц = 1,..., т; (4)

—ос, иначе,

}цЛР) =шах{с„ + /м_1,„_1(Д-г7„); /„,„-1 (/?)}, (5)

для всех /х = 1,..., т, г/ = ц + 1,..., п.

Алгоритм Л о решения задачи тп-ПВ состоит в решении одномерных задач вида 1 для каждого в € В. Для решения одномерной задачи используются рекуррентные соотношения из леммы 2.1. Для задачи ПВО удается применить аналогичную схему построения алгоритма. Оценка мощности множества В и трудоемкости решения одномерной задачи приводит к следующей теореме.

Теорема 2.2. Если размерность к пространства Лк фиксирована, то задачи т-ПВ и ПВО с целочисленными координатами векторов решаются точно за псевдополиномиальное времяО(ктп(тЪ)к~1 ^ в случае неотрицательных координат и в случае координат произвольного знака.

Результаты раздела получены в соавторстве с Э.Х. Гимади и Ю. В. Глазковым.

В разделе 2.3 осуществляется построение точного алгоритма решения задачи т-ПВ, полиномиального при фиксированном к. Таким образом, вопрос, поставленный в разделе 2.1, получает для задачи т-ПВ положительный ответ.

Идея алгоритма основана на следующих доказанных в работе фактах:

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

Утверждение 2.2. Набор т векторов, дающих максимальные проекции на направление, изменяется только при переходе направления через гиперплоскости, перпендикулярные векторам вида ьг — г>3

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

Способ построения множества представителей основан на применении леммы из работы [2].

Семейством областей принадлежности решения (ОПР) для данных ненулевых векторов и^, и?, ■ ■ ■, щ назовем семейство максимальных по включению связных подмножеств пространства не пересекающихся с ортогональными гиперплоскостями для векторов щ,и2, ■ • ■ Набор векторов пространства К*", содержащий ровно по одному вектору из каждой области семейства ОПР, назовем семейством представителей областей

принадлежности решения для векторов щ,и2,. ■ ■

Лемма [2]. Семейство представителей ОПР для ненулевых векторов щ, «2, • • •, щ в пространстве К*11 имеет мощность 0(Ык~1) и может быть найдено за время 0(к21к).

Алгоритм Ар заключается в построении семейства представителей ОПР для множества векторов {г^ — «¿||1 п}. Для каждого из пред-

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

Теорема 2.4 Алгоритм Ар находит оптимальное решение задачи т-ПВ за время 0{к2п2к).

Результаты раздела получены в соавторстве с Э.Х. Гимади и А. В. Пяткиным.

В разделе 2.4 приведен рандомизированный алгоритм Ал решения задачи т-ПВ. Идея алгоритма основана на утверждении 2.1, а также на том факте, что отношение проекций векторов на почти параллельные направления близко к единице.

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

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

Теорема 2.5. Алгоритм Ац приближенного решения задачи т-ПВ имеет оценки относительной погрешности

= 0(ФЪ),

вероятности несрабатывания

(ЬтЗр)*-1 Л

¡А* =ехр —

тт\/к

и временной сложности Тал — 0(пкЬ).

Следствие 2.1. Алгоритм Ац с параметрами фо = ^ иЬ = к3//2п(Ы п)к, за время Тан = С){пкл>/21п'£ п) находит асимптотически точное решение

задачи т-ПВ с оценками относительной погрешности £= 0(1/(21п2п)) и вероятности несрабатывания = 0(1/п) и является асимптотически точным.

Результаты раздела получены в соавторстве с Э. X. Гимади.

Автор выражает искреннюю благодарность своему научному руководителю Эдуарду Хайрутдиновичу Гимади за постоянную поддержку и внимание к работе.

Список литературы

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

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

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

[4] Гимади Э. X., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипе-риодически повторяющегося фрагмента при заданном числе повторов // Сиб. журн. индустриальной математики. 2006. Т. IX, № 1(25). С. 55-74.

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

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

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

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

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

[10] Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions 11 SIAM Journal on Computing. 1980. N 9. P. 846.

[11] 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.

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

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

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

Публикации автора по теме диссертации

Статьи в журналах

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

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

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

[18] A. Ershov, I. Ivanov, V. Kornienko, S. Preis, A. Rasskazov, I. Rykov A new scheduling engine for PLM // International Journal of Product Lifecycle Management. 2006. V. 1. № 2. C. 164-180.

Прочие публикации

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

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

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

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

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

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

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

[26] Gimadi Е., 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.

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

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

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

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

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

[32] 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

Рыков Иван Александрович

Алгоритмы с оценками качества для задач календарного планирования, упаковки и выбора подмножества векторов

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 6.10.09. Формат 60x84 1/16. Усл. печ. л. 1,2. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 115.

Отпечатано в ООО "Омега Принт" 630090, Новосибирск, пр. Лаврентьева, 6.

Введение

Глава 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.

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

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

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

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