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

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

□и^4 ■ -

Щербинина Татьяна Александровна

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

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

^ 5 V и ^

Омск - 2009

003471424

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Омский государственный университет им. Ф.М. Достоевского"

Научный руководитель: кандидат физико-математических наук

Сервах Владимир Видентьевич

Официальные оппоненты: доктор физико-математических наук, профессор

Ведущая организация: Вычислительный центр РАН, Москва

Защита состоится 30 июня 2009 года в 1500 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6.

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

Автореферат разослан 21 мая 2009 г.

Гимади Эдуард Хайрутдинович

кандидат экономических наук, доцент Ляхов Олег Алексеевич

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

С.Б. Сорокин

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

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

В области календарного планирования большое внимание уделяется исследованию задач с возобновимыми или складируемыми ресурсами. Наиболее изучена задача с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для данной задачи в работах Гимади Э.Х., Серваха В.В., Шафранского В.В., Blazewicz J., Brucker Р., Knust S., Ulusoy G. и других предложены алгоритмы точного и приближенного решений. Задачи с другими критериями оптимизации исследованы относительно слабо, поэтому возникает необходимость в построении как точных, так и приближенных алгоритмов решения таких задач.

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

В связи со сложностью рассматриваемых задач значительное число исследований посвящено разработке приближенных алгоритмов с гарантированной оценкой точности. Особое значение имеют аппроксимационные схемы, с помощью которых за полиномиальное время от длины входа можно получить решение задач с любой наперед заданной точностью. Такой подход использовали Воегингер Г.Д., Ковалев М.Я., Левнер Е.В., Севастьянов C.B., Ibarra О. и другие. Построение аппроксимационных схем решения NP-трудных задач является одним из перспективных направлений дискретной оптимизации.

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

Для достижения поставленной цели решались следующие задачи:

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

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

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

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

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

Основные результаты работы заключаются в следующем:

1. Доказано, что задачи со складируемыми ресурсами и критериями средневзвешенного времени завершения работ и чистой приведенной прибыли являются ЛгР-трудными в сильном смысле. В частном случае, когда работы не связаны отношением предшествования, показана Л^Р-трудность данных задач.

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

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

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

завершения работ.

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

На защиту выносятся:

1. Доказательство /VP-трудности задач календарного планирования со складируемыми ресурсами с критериями средневзвешенного времени завершения всех работ и чистой приведенной прибыли.

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

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

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

Внедрение результатов работы. Результаты работы используются в учебном процессе в Омском государственном университете им. Ф.М. Достоевского.

Апробация работы. Основные результаты диссертации докладывались на XXIX Региональной научной студенческой конференции "Молодежь третьего тысячелетия" (Омск, 2005), XVIII International Conference of the European Chapter on Combinatorial Optimizations (Минск, 2005), I международной школе-семинаре "Проблемы оптимизации сложных систем" (Новосибирск, 2005), 12th IFAC Symposium on Information Control Problems in Manufacturing (Saint-Etienne, France, 2006), III Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2006), XIII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2007), Всероссийской научной молодежной конференции "Под знаком Е" (Омск, 2007), Всероссийской конференции "Дискретная оптимизация и исследование операций" (Владивосток,

2007), International Conference of Operations Research in the Service Industry (Saarbrucken, 2007), 14-й Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2008), а также на семинарах в Омском государственном университете, Институте математики им. C.JI. Соболева СО РАН и его Омском филиале.

Публикации. Результаты по теме диссертации опубликованы в 13 работах, одна из них в рецензируемом издании из списка ВАК.

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка используемой литературы, включающего 93 наименования. Материал изложен на 101 странице текста, включая 8 рисунков и 4 таблицы.

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

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

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

В 1.1 приводится классическая постановка задачи календарного планирования с ограниченными ресурсами. Пусть имеется проект, который состоит из множества взаимосвязанных работ V = (1,..., N}. Связи задаются технологией выполнения проекта и определяются отношениями предшествования вида i —» j, это означает, что работа j не может начать свое выполнение до завершения работы i. Данная структура может быть представлена ориентированным ацикличным графом G = (V, Е), где V - множество вершин, а Е = {(г, j g V, г —> j} - множество дуг. Рассматриваются ресурсы двух видов: возобновимые Кг и складируемые Ка. На период планирования проекта Т в интервале времени [i — l,t) имеется qu(t) единиц ресурса

к £ К = Кг и Ка, 1 — 1,2,... ,Т. Работа 3 € V характеризуется длительностью р^ е и потребностью гу(т) в ресурсе к € К в интервале [г — 1,г), т = 1,2,... отсчитывая от начала выполнения работы 3 € V. Для каждой работы определен директивный срок ее завершения £ . Прерывания процесса выполнения работ не допускаются. Требуется определить сроки выполнения работ проекта с учетом технологического порядка и ограничений на ресурсы, при которых достигается оптимальное значение некоторой целевой функции. Пусть - время начала выполнения работы 3 £ V. Вектор 5 = (¿1,52, • • •, называется расписанием выполнения работ. С использованием введенных обозначений ограничения рассматриваемой задачи календарного планирования могут быть записаны в виде:

Е Е - *,■) < £ к е Ка; ¿ = 1,2,..., Г; Е гф - 5,) < кеКг, 1 = 1,2,..., Т;

Si+Pi<Sj, (м')еЕ;

5j +pJ < ¿е V,

где Л^ = {3 е У\з3 < I < В] + Р]} - множество работ, выполняемых на интервале [4 — 1,4).

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

1. Минимизировать общий срок выполнения всех работ Сшах.

2. Минимизировать максимальное запаздывание работ Ьтах.

3. Минимизировать средневзвешенное время завершения всех работ Тли^Су

4. Минимизировать суммарный взвешенный штраф за нарушение директивных сроков Ег^-Т).

5. Минимизировать взвешенное число невыполненных в срок работ Е ю^. В 1.2 описываются частные случаи задачи календарного планирования

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

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

сурса - финансовый. На начало периода [i — l,f) в наличии имеются финансовые ресурсы объемом K(t), t — 1,2,...,Т. Работа j G V характеризуется длительностью Pj G Z+ и потребностью в складируемом ресурсе г,(т) для каждого периода [т — 1,т), г = 1,2,... ,pj, отсчитывая от начала выполнения работы j G V. Обозначим через cj(r) > 0 - прибыль работы j G V в момент времени т = 1,2,..., pj. Последовательность величин (cj(l),cj(2),... ,Cj(pj)) называется потоком поступлений работы j G V. Поток поступлений с помощью операции дисконтирования может быть приведен к началу выполнения работы j G V, и тогда чистая приведенная прибыль от выполнения работы составит: NPVj = £ (н^р7* гДе ro ~ Чена капитала на рынке. Предполагается, что все работы выполняются непрерывно. Получаем следующую модель задачи:

NPV;•

NPV(S) = Z - max>

J6V (1 + гоГ при условиях t t

Е £ rjit' - Sj) < Y, K(t'), i = 1,2,... ,T; t'=lj&Nt, t'=1

Si+Pi<Sj, (i,j)çE\ Sj G{0,l,...,r-1}, j G F.

В п. 1.4 задача календарного планирования с учетом ограничений на ресурсы формулируется как задача целочисленного линейного программирования. ЛП-релаксация данной задачи используется для построения верхней (нижней) оценки значений целевой функции в третьей главе.

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

В 2.1 описываются положения современной теории сложности, на основе которых дается обзор сложности изучаемых в работе задач. В работе Гимади Э.Х., Залюбовского В.В. и Севастьянова C.B. для задачи с ресурсами складируемого типа и критерием общего времени завершения всех работ проекта предложен полиномиальный алгоритм построения точного решения. Насколько нам известно, анализ сложности задач календарного планирования с другими критериями оптимизации не проводился.

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

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

Теорема 2.1. Задача календарного планирования проектов со складируемыми ресурсами и критерием средневзвешенного времени завершения работ является NP-трудной в сильном смысле.

К данной задаче полиномиально сводится задача о клике. В случае, если работы выполняются независимо, доказана NP-трудность задачи, к ней сведена булева задача о рюкзаке.

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

В 2.3 аналогичные результаты приводятся для задачи календарного планирования с критерием чистой приведенной прибыли, т.е. доказана сильная TVP-трудность в общем случае и ЛгР~трудность задачи с независимыми работами.

В 2.4 описываются алгоритмы решения задач календарного планирования со складируемыми ресурсами и независимыми работами с критериями средневзвешенного времени завершения всех работ и чистой приведенной прибыли. Для данных задач предложены алгоритмы, основанные на схеме динамического программирования (ДП). Трудоемкость алгоритмов составляет 0(NT2{q( 1) + l)(g(2) + 1)... (q(T) + 1)) операций.

В случае, если горизонт планирования ограничен некоторой заданной величиной, то получено следующее утверждение

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

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

В этом же параграфе показана полиномиальная разрешимость задачи с критерием средневзвешенного времени выполнения работ проекта, если все весовые коэффициенты равны 1. Трудоемкость алгоритма составляет 0(N log N).

Основные результаты данной главы опубликованы в [1, 3, 7, 12, 13].

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

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

Идея алгоритма заключается в переборе всевозможных частичных состояний выполнения работ проекта, а для каждого состояния по рекуррентной формуле строится лучшее допустимое частичное расписание. Введем основные обозначения. Разобьем частичный порядок выполнения работ на К цепей, В^ - суммарная длительность работ цепи к, к = 1,2,...,К. Вектор х = (х\,Х2,-..,хк) называется состоянием выполнения работ проекта, 0 = (0,0,..., 0) - начальное состояние, В = {В\, В2, ■ ■ ■, В к) - конечное состояние. Обозначим через X = {х = (хих2,.. .,хк)\хк е {0,1,...,^}, к = 1,2 ,...,К} множество всех состояний. Переход между состояниями задается булевыми векторами 5 — (¿1,¿2,.■ •,, где дк 6 {0,1}, к = 1,2,...,К. Вектор <5 называется допустимым, если соблюдаются ограничения на ресурсы. Множество допустимых управлений, приводящих в состояние х, обозначим через Дх. Пусть £(х) - оптимальное значение целевой функции для частичного расписания, соответствующего состоянию х.

В работе Серваха В.В. было предложено рекуррентное соотношение для задачи с возобновимыми ресурсами и критерием Сгаах. В данной главе получено рекуррентное соотношение для задачи с критерием Е гп^С^. Дх) = тт(£(х — 5) + £ € Х\{0}, где Л^ - множество еще не

завершенных работ для состояния х. Трудоемкость алгоритма составляет 0(2ККМВ1В2 ■ ■ ■ В к) операций, где М - число видов ресурсов.

Для задачи с произвольными ресурсами и другими рассматриваемыми критериями предложенная выше схема требует модификации, так как в этих случаях стоимость перехода х — 5 —► х зависит не только от состояния х, но и от времени, когда это состояние достигается. Расширенным состоянием будем называть вектор х2, ■ • •,Хк). Через Ь{Ь,х) обозначим оптимальное значение целевой функции для частичного расписания, соответствующего состоянию (¿, х). Расширение множества состояний позволяет обобщить предложенный алгоритм ДП на случай произвольных ресурсов и различных

критериев.

Рекуррентное соотношение для задачи с NPV- критерием: 1,(0,0) =0;

L(t, х) = mg [b{t - 1, х - + Е i ,

х € Х\{0}, t = 1,2,... ,Т, где S(i, х) - множество работ, начавшихся в момент времени t.

Были получены также рекуррентные соотношения и для задач с критериями Lmax, T,WjTj, YLWjUj. Трудоемкость предложенных алгоритмов составляет 0(2КВКМВ1В2... Вк), где В — Е Bk- Проанализировав временную

fc=1

сложность алгоритма динамического программирования в зависимости от величины К, получили следующую

Теорема 3.1. Если ширина частичного порядка выполнения работ ограничена некоторой заданной величиной К, то задача календарного планирования с ограниченными ресурсами и критерием средневзвешенного времени завершения всех работ псевдополиномиалъно разрешима.

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

В 3.2 приводятся алгоритмы АВВ\ и АВВ2 решения задач календарного планирования с ограниченными ресурсами, основанные на схеме метода ветвей и границ. В алгоритме ABBi последовательно фиксируются сроки выполнения работ проекта. Для текущей подзадачи v через Sv обозначим множество работ, для которых фиксировано время начало выполнения Sj. Для остальных работ определены ранние времена начала выполнения Ц. Ветвление осуществляем по допустимой работе k EV\Sv: либо фиксируем начала выполнения работы к, либо сдвигаем ранний срок ее выполнения на единицу.

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

1. Работа г выполняется раньше работы j.

2. Работа j выполняется раньше работы г.

3. Работы inj выполняются параллельно в одном временном интервале.

В 3.3 описывается гибридный алгоритм, основанный на комбинации АВВ2 с алгоритмом ДП, описанном в 3.1. При исследовании алгоритма динамического программирования получено следующее

Следствие 3.1. Если ширина частичного порядка выполнения работ ограничена некоторой заданной величиной К, то задача календарного планирования с ограниченными ресурсами и единичными длительностями работ полиномиально разрешима за 0(NKM(^jf)K).

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

1. В схеме алгоритма АВВ2 ветвление осуществлять так, чтобы

ширина частичного порядка уменьшалась.

2. Если позволяет объем требуемой памяти, то подзадачу решаем алгоритмом динамического программирования.

В 3.3 приводятся результаты вычислительного эксперимента. За основу тестовых примеров были взяты задачи из известной электронной библиотеки PSPLib (http://wwui.bwl.uni-kiel.de/Prod/psplib/index.html).

Основные результаты данной главы опубликованы в [3, 5, 8].

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

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

Под вполне полиномиальной аппроксимационной схемой (FPTAS) будем понимать семейство (1 + е)-приближенных алгоритмов при всевозможных О < е < 1 с временной сложностью, полиномиально зависящей от длины входа задачи и

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

Теорема 4.1. Если ширина частичного порядка выполнения работ ограничена некоторой заданной величиной К, то для задачи календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ существует вполне полиномиальная аппроксимационная схема трудоемкости 0(2ККМ.

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

В 4.3 строится вполне полиномиальная аппроксимационная схема для разномаршрутной задачи теории расписаний. Пусть имеется множество п требований и Ь обслуживающих приборов. Каждое требование обслуживается приборами в заданной, специфической для него последовательности. Через N обозначим общее количество операций обслуживания всех требований. Предполагается, что процесс обслуживания требования может включать повторные обращения к одним и тем же приборам. Известны также длительности всех операций. Прерывания выполнения операций не допускаются. Каждый прибор не может обслуживать более одного требования одновременно. Необходимо построить оптимальное по быстродействию расписание процесса обслуживания всех требований. Эта задача является ЛГР-трудной в сильном смысле.

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

Следствие 4.1. Если в разномаршрутной задаче число требований ограничено константой п, то для ее решения существует вполне полиномиальная аппроксимационная схема трудоемкости 0^2ппЬЫ2п

Результаты четвертой главы опубликованы в работах [2, 4, 6, 9-111-

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

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемых журналах из списка ВАК

1. Сервах В.В., Щербинина Т.А. О сложности одной задачи календарного планирования со складируемыми ресурсами // Вестник НГУ. Серия: Математика, механика, информатика. - 2008. - Т. 8, - вып. 3. -С. 105-111.

В других изданиях

2. Сервах В.В., Щербинина Т.А. Аппроксимационная схема для одной задачи планирования проектов при ограниченных ресурсах // Труды ИВМиМГ, серия Информатика, 5. - Новосибирск, 2005. - С. 170-178.

3. Сервах В.В., Щербинина Т.А. О задаче календарного планирования проекта с различными критериями и складируемыми ресурсами // III Всероссийская конференция "Проблемы оптимизации и экономические приложения". - Омск, 2006. - С. 125.

4. Щербинина Т.А. Приближенное решение задачи календарного планирования с ограниченными ресурсами // Препринт, Издательство ОмГУ, 2006. - 15 с.

5. Сервах В.В., Щербинина Т.А. Гибридные алгоритмы для некоторых задач календарного планирования проектов // XIII Всероссийская конференция "Математическое программирование и приложения". - Екатеринбург, 2007. - С. 213-214.

6. Щербинина Т.А. О задаче календарного планирования с возобновимыми ресурсами // Всероссийская научная молодежная конференция "Под знаком Е". - Омск, 2007. - С. 50-51.

7. Сервах В.В., Щербинина Т.А. О сложности задачи календарного планирования со складируемыми ресурсами // VI Всероссийская конференция "Дискретная оптимизация и исследование операций",— Владивосток, 2007. - С. 136.

8. Сервах В.В., Щербинина Т.А. Алгоритмы решения задач календарного планирования проектов с различными критериями // XIV Байкальская международная школа-семинар "Методы оптимизации и их приложения". - Иркутск, 2008. - С. 506-512.

9. Servakh V.V., Shcherbinina T.A. On some approximation of solution of resource constrained project scheduling problem // Abstract of International Conference of the European Chapter on Combinatorial Optimizations. -Minsk, 2005. - P. 64.

10. Servakh V.V., Shcherbinina T.A. A fully polynomial time approximation scheme for two project scheduling problem // Preprints 12th IFAC Symposium on Information Control Problems in Manufacturing. - France, 2006. - Vol. 3. - P. 131-135.

11. Servakh V.V., Shcherbinina T.A. A Fully Polynomial Time Approximation Scheme For Two Project Scheduling Problems. Reprinted from information control problems in manufacturing 2006, A Proc. Vol. from the 12th IFAC International Symposium, 3 V., Ed. by A. Dolgui, G. Morel and C.E. Pereira, Pages XV-XXXVII, Copyright (2006), with permission from Elsevier, 2007. - P. 129-134.

12. Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Abstract of International Conference of Operations Research in the Service Industry. - Germany, 2007. - P. 167.

13. Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Operations Research Proceeding. Springer. - Germany, 2007. - P. 427-431.

Отпечатано с оригинал-макета, предоставленного автором

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

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира, 11а тел.: (3812) 65-47-31 Лицензия ПЛД № 58-47 от 21.04.1997.

Введение

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

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

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

1.3. Задача календарного планирования проектов с критерием чистой приведенной прибыли.

1.4. Модель целочисленного линейного программирования

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

2.1. Алгоритмическая сложность решения задач

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

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

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

3. Алгоритмы нахождения точного решения некоторых задач календарного планирования

3.1. Алгоритмы, основанные на методе динамического программирования

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

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

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

4.1. Предварительные сведения.

4.2. Задача календарного планирования с критерием общего времени завершения работ.

4.3. Задача календарного планирования с критерием среднего времени завершения всех работ.

4.4. Разномаршрутная задача теории расписаний.

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

Научный подход к календарному планированию проектов предложен и применен в конце 50-х годов прошлого века. Были разработаны такие технологии как PERT (Project Evaluation and Review Technique) [46, 65] и CPM (Critical Path Method) [71, 75]. Характерной особенностью этих технологий является представление проекта в виде комплекса взаимосвязанных работ. Однако возможности указанных разработок были ограничены, так как в них не учитывались реальные ограничения на используемые ресурсы.

В дальнейшем, после создания теории сложности, было установлено, что большинство задач календарного планирования с учетом ограничений на ресурсы являются iVP-трудными. Эти задачи можно рассматривать, например, как обобщения разномаршрутной задачи теории расписаний (Job-shop) [47], задачи построения конвейерного расписания (Flow-shop)\58], задачи с параллельными приборами [92], задача о камнях [57] и т. д.

В настоящее время ведутся исследования структуры и вычислительной сложности указанных задач календарного планирования, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения [7,12,16,22,28,36—38,48,50,62]. Особую актуальность эти задачи приобретают при планировании крупномасштабных проектов, требующих больших затрат ресурсов [10, 8, 9, 81].

Среди подходов к получению оптимальных решений задач календарного планирования следует выделить схему динамического программирования [2], метод ветвей и границ [8 — 10,81], различные алгоритмы комбинаторного типа [11, 14, 16, 23, 36, 37, 57, 61].

Другим перспективным направлением является сведение задач построения расписаний к задачам целочисленного линейного программирования (ЦЛП). Данный подход используется, например, в [10, 81]. В ряде известных методов решения задач ЦЛП применяется приведение исходной задачи к последовательности задач непрерывной оптимизации. На таком подходе основаны алгоритмы отсечения [4, 15, 18, 39, 42], ветвей и границ [20, 42], декомпозиции [45], перебора L-классов [19| и др.

Задачи календарного планирования с ограничениями па ресурсы можно разбить два класса. К первому относятся задачи с временными критериями (общее или средневзвешенное время завершения всех работ, штраф за нарушение директивных сроков, число невыполненных в срок работ и т. д. [47,49 — 51,59,72]). Ко второму классу - задачи с критериями, связанными с эффективным использованием ресурсов или получением прибыли, в частности, задачи минимизации общего потребления ресурсов (Resource leveling problem), сглаживания потребляемых ресурсов [Resource Investment problem), максимизации чистой приведенной прибыли (Net Present Value problem) [53, 68, 72]. В диссертации рассматриваются задачи из обоих классов.

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

Наиболее изучена задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для данной задачи в [44, 53, 68, 69, 90] предложены алгоритмы точного и приближенного решений. Однако задачи такого типа с другими критериями оптимизации исследованы относительно слабо, поэтому возникает необходимость в построении как точных, так и приближенных алгоритмов решения таких задач.

В связи со сложностью рассматриваемых задач значительное число исследований посвящено разработке приближенных алгоритмов с гарантированной оценкой точности. Особое значение имеют аппроксимационные схемы, с помощью которых за полиномиальное время от длины входа можно получить решение задач с любой наперед заданной точностью. Такой иодход использовали в [5, 67, 73] и других работах. Построение аппроксимаци-онных схем решения NP-трудных задач является одним из перспективных направлений дискретной оптимизации.

Определенные успехи достигнуты при исследовании задачи календарного планирования со складируемыми ресурсами, в которых минимизируется общее время завершения всех работ [6, 8 — 10,14,16] Было доказано, что данная задача является полиномиально разрешимой [7] и предложен алгоритм ее решения. Поэтому актуальным является исследование сложности указанных задач с другими критериями оптимизации.

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

Диссертация состоит из введения, четырех глав и заключения.

Основные результаты диссертации заключаются в следующем:

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

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

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

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

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

Заключение

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

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

2. Беллман Р. Динамическое программирование.— Москва: ИЛ, I960.- 400 с.

3. Вереснев В.Л., Гимади Э.Х., Деменьтьев В. Т. Экстремальные задачи стандартазации.— Новосибирск: Наука, 1978.— 336 с.

4. Булатов В.П. Методы погружения в задачах оптимизации.— Новосибирск: Наука, 1977.— 161 с.

5. Гене Г.В., Левнер Е.В. Эффективные приближенные алгоритмы для комбинаторных задач.— Препринт, Москва, ЦЭМИ, 1981.— 38 с.

6. Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений.— Новосибирск: Новосиб. ун-т, 1982.— 80 с.

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

8. Гимади Э.Х., Пузынииа Н.М. Задача календарного планирования крупномасшабного проекта в условиях ограниченных ресурсов: опытпостроения математического обеспечения // Управляемые системы.— Новосибирск: Ин-т мат. СО АН СССР, 1983. Вып. 23.- С. 24-32.

9. Гимади Э.Х., Пузынина Н.М., Севастьянов С.В. О некоторых экстремальных задачах реализации крупный проектов типа БАМ j j Экономика и мат. методы.— 1979.— Вып. 5.— С. 1017-1020.

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

11. Гордон С.В., Сотсков Ю.Н., Танаев B.C. Теория расписаний. Одностадийные системы.— М.: Наука, 1989.— С. 336-342.

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

13. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика.— 2004.- N 3.- С. 48-54.

14. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования.— М.: Наука, 1965.— 296 с.

15. Ковалев М.М. Дискретная оптимизация (целочисленное программирование).— Минск: БГУ, 1977.— 192 с.

16. Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов // Изв. АН СССР. Техническая кибернетика.— 1977.— Vol. 4,- С. 75-81.

17. Колоколов А.А. Методы дискретной оптимизации.— Учебное пособие — Омск: ОмГУ, 1984 — 75 с.

18. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций.— Новосибирск,— 1994.- Т. 1, N 2.- С. 18-39.

19. Корбут А.А., Финкелъштейн Ю.Ю. Дискретное программирование.— М.: Наука, 1969.- 368 с.

20. Кук С.А. Сложность процедур вывода теорем // Киберн. сб. Новая серия.— 1975.— вып. 12.— С. 5-15.

21. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресерсов.— М.: Наука, 1983.- 208 с.

22. Моудер Дж., Элмаграби С. Исследование операций.— Т. 2. Модели и применения.— М.: Мир, 1981.— 677 с.

23. Левнер Е.В. Сетевой подход к задачам теории расписаний. Исследования по дискретной математике.— М.: Наука, 1973.— С. 135-150.

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

25. Попков В.К. Математические модели связности. В трех частях. ИВМ и МГ СО РАН.- Новосибирск, 2000-2002 560 с.

26. Раетригин JI.A. Статистические методы поиска.— М.: Наука, 1968.- 376 с.

27. Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретный анализ и исследование операций. Сер. 2.— 2000. Т. 7, N 1 — С. 75-82.

28. Сервах В.В., Щербинина Т.А. Алгоритмы решения задач календарного планирования проектов с различными критериями //VI Байкальская международная школа-семинар "Методы оптимизации и их приложения".- Иркутск,- 2008.— С. 506-512.

29. Сервах В.В., Щербинина Т.А. Аппроксимационная схема для одной задачи планирования проектов при ограниченных ресурсах // Труды ИВМиМГ, серия Информатика, 5 — Новосибирск, 2005 — С. 170-178.

30. Сервах В.В., Щербинина Т.А. Гибридные алгоритмы для некоторых задач календарного планирования проектов // XIII Всероссийская конференция "Математическое программирование и приложения".— Екатеринбург,- 2007.- С. 213-214.

31. Сервах В.В., Щербинина Т.А. О задаче календарного планирования проекта с различными критериями и складируемыми ресурсами // III Всероссийская конференция "Проблемы оптимизации и экономические приложения".— Омск,— 2006.— С. 125.

32. Сервах В.В., Щербинина Т.А. О сложности задачи календарного планирования со складируемыми ресурсами j j XIV Всероссийскаяконференция "Дискретная оптимизация и исследование операций".— Владивосток,— 2007 — С. 136.

33. Сервах В.В., Щербинина Т.А. О сложности одной задачи календарного планирования со складируемыми ресурсами // Вестник НГУ. Серия: Математика, механика, информатика.— 2008.— Т. 8,— вып. 3.— С. 105-111.

34. Схрейвер А. Теория линейного и целочисленного программирования.— Т. 2,- М.: Мир, 1991.- 342 с.

35. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы.— М.: Наука, 1984.— 384 с.

36. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы.— М.: Наука, 1989.— 328 с.

37. Танаев B.C., Шкурба В.В. Введение в теорию расписаний.— М: Наука, 1975.- 256 с.

38. Шевченко В.Н. Качественные вопросы целочисленного программирования.— М.: Физматлит.— 1995.— 190 с.

39. Щербинина Т.А. О задаче календарного планирования с возобновимыми ресурсами // Всероссийская научная молодежная конференция "Под знаком £".— Омск,- 2007.- С. 50-51.

40. Щербинина Т.А. Приближенное решение задачи календарного планирования с ограниченными ресурсами // Препринт, Изд-во ОмГУ,— 2006,- 15 с.

41. Ху Т. Целочисленное программирование и потоки в сетях.— М.: Мир, 1974.- 520 с.

42. Akers S.E. A graphical approach to production scheduling problems. // Oper. Res.- 1956,- Vol. 4, N 2.- P. 244-245.

43. Baroum S.M., Patterson J.H. The development of cash Cow weight procedures for maximizing the net present value of a project // Journal of Operations Management 1996.- Vol. 14, N 3.- P. 209-227.

44. Benders J.F. Partitioning Procedures for Solving of Mixed-Variables Programming Problems // Numer. Math.— 1962.— Vol. 4, N 3.— P. 238-252.

45. Bigelow C.G. Bibliography on Project Planning and Control by Network Analysis // Oper. Res.- 1962.- Vol. 10.- P. 728-731.

46. Blazewicz J., Lenstra J.K., and Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // Discrete Applied Mathematics.- 1983.- Vol. 5, N 1 — P. 11-24.

47. Blazewicz J., Cellary W., Slowinski R., Weglarz J. Scheduling under Resource Constraints. Deterministic Models. Baltzer, Basel.— 1986.

48. Bottcher J., Drexl A., Salewski F. Project scheduling under partially renewable resource constraints // Management Science.— 1999.— Vol. 45,— N 4.- P. 543-559.

49. Brucker P., Drexl A., Mohring R., Neumann K. and Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods j I Eur. Jour, of Oper. Res.- 1999.- Vol. 112.- P. 3-41.

50. Brucker P., Knust S., Schoo A., and Thiele 0. A branch and bound algorithm for the resource-constrained project scheduling problem // Eur. Jour, of Oper. Res.- 1998.- Vol. 107,- P. 272-288.

51. Demeulemeester E., Herroelen W., Van Dommelen P. An optimal recursive search procedure for the deterministic unconstrained max-npv project scheduling problem. Paper, Workshop on Production Planning and Control, Mons (Belgium),- 1996.- P. 340-343.

52. Doersch, R.H. and Patterson, J.H. Scheduling a Project to Maximize Its Net Present Value: A Zero-One Programming Approach // Management Science.— 1977 Vol. 23.- P. 882-889.

53. Elmaghraby S.E. and Herroelen, W.S. The Scheduling of Activities to Maximize the Net Present Value // Eur. Jour, of Oper. Res.— 1990.— Vol. 49.- P. 35-49.

54. Eremeev A. V. and Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the First International Conference on Evolutionary Computation and Its Applications.- Moscow, 1996,— P. 297-303.

55. Garey M.R., Johnson D.S. Complexity result for multiprocessor scheduling under resource constraints // SIAM J. Comput.— 1975.— Vol. 4,— N 4.— P. 397-411.

56. Garey, M.R. and Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness.— Freeman, New York, 1979.— 175 p.

57. Garey M.R., Johnson D.S., and Sethi R. The complexity of flow shop and job shop scheduling // Math. Oper. Res.— 1976—Vol. 1, N 2 — P. 117-129.

58. Gimadi E. and Sevastianov S. On Solvability of the Project Scheduling Problem with Accumulative Resorces of an Arbitrary Sign // Operations Research Proceedings, Springer, 2002.— P. 241-246.

59. Grinold R. C. The payment scheduling problem. // Naval Research Logistics Quarterly.- 1972.- Vol. 19, N 1 P. 123-136.

60. Hardgrave W. W., Nemhauser G. A Geometric Model and Graphical Algorithm for a Sequencing Problem // Oper. Res.— 1963.— Vol. 11, N 6.- P. 889-900.

61. Herroelen W., Demeulemeester E., De Reyck B. A classification scheme for project scheduling // Project schedling: recent models, algorithms, and applications (edited by Jan Weglarz)- USA.- 1999.- P. 1-26.

62. Herroelen W.S., De Reyck B. and Demeulemeester E.L. Resource-Constrained Project Scheduling: A Survey of Recent Developments // Сотр. and Oper. Res.- 1998 Vol. 25,- P. 279-302.

63. Herroelen W.S. and Galiens E. Computational Experience with an Optimal Procedure for the Scheduling of Activities to to Maximize the Net Present Value of projects // Eur. Jour, of Oper. Res.— 1993.— Vol. 65.— P. 274-277.

64. Fazar W. The Origin of PERT // The controller.- December, 1962 — P. 598-602, 618-621.

65. Jansen K., Solis-Oba R., Sviridenko M. Makespan minimization in job shops: A linear time approximation scheme // SIAM Journal on Discrete Mathematics.- 2003.- Vol. 16, N 2.- P. 288-300.

66. Ibarra 0., Kim C.E. Fast approximation algorithms for the knapsack and sum of subset problems // Journ. of the АСМ,— 1975.— Vol. 22.— P. 463-468.

67. Icmeli 0., Erenguc S.S. A branch and bound procedure for the resource constrained project scheduling problem with discounted cash Cows // Management Science.- 1996.- Vol. 42, N 10.- P. 1395-1408.

68. Icmeli 0., Erenguc S.S. A tabu search procedure for the resource constrained project scheduling problem with discounted cash Cows // Сотр. and Oper. Res.- 1994.- Vol. 21, N 8,- P. 841-853.

69. Karp R.M. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatchar (eds.) // Complexity of Computer Computation. Prenum Press. New York,- 1972.- P. 85-103.

70. Kelley I.E. Critical-Path Planning and Scheduling: Mathematical Basis // Oper. Res.- 1961.- Vol. 9.- P. 296-320.

71. Kolish, R. and Padman, R. An Integrated Survey of Deterministic Project Scheduling // OMEGA Jour, of Sched.- 2001,- Vol. 29,- P. 249-272.

72. Kovalyov M. Improving the complexities of approximation algorithm for optimization problems. // Oper. Res. Let — 1995 — Vol. 17 — P. 85-87.

73. Lerda-Olberg S. Bibliography on Network-Based Project Planning and Control Techniques: 1962-1965 // Oper. Res.- 1966.- Vol. 15 — P. 925-931.

74. Middendorf, M. and Timkovsky, V. G. Transversal graphs for partially ordered sets: Sequencing, Merging and Scheduling problems // Journal of Combinatorial Optimization 1999 - Vol. 3, N 4 — P. 417-435.

75. Neumann K., Schwindt C. and Zimmermann J. Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Funsctions. -Springer-Verlag, 2002,- P. 105-110.

76. Ozdamar L. and Ulusoy G. A Survey on the Resource-Constrained Project Scheduling Problem // IEE Transactors.- 1995.- Vol. 27.- P. 574-586.

77. Project scheduling: recent model, algorithm and applications // edt. by Jan Weglarz. Kluwer Academic Publishers.— 1999.— 552 p.

78. Russell A.H. Cash Cows in networks. Management Science.— 1970.— Vol. 16, N 5.- P. 357-373.

79. Schirmer F., Drexl A. Allocation of partially renewable resources: Concept, capabilities, and applications. Networks.— 2001.— Vol. 37.— P. 21-34.

80. Servakh V.V., Shcherbinina T.A. A fully polinoinial time approximation scheme for two project scheduling problem // Preprints 12th IFAC Symposium on Information Control Problems in Manufacturing.— France2006,- Vol. 3.- P. 131-135.

81. Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Abstract of International Conference of Operations Research in the Service Industry.— Germany,— 2007,- P. 167.

82. Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Operations Research Proceeding. Springer.- Germany 2007,- P. 427-431.

83. Servakh V.V. A Dynamic algorithm for some Project Management Problems j j Proceedings of the International Workshop "Discrete optimization methods in scheduling and computer-aided design".— Minsk,- 2000.- P. 90-92.

84. Servakh V.V., Shcherbinina Т.A. On some approximation of solution of resource constrained project scheduling problem. // Abstract of International Conference of the European Chapter on Combinatorial Optimizations Minsk,— 2005.— P. 64.

85. Smith-Daniels D.E., Smith-Daniels V.L. Maximizing the net present value of a project subject to materials and capital constraints // Journal of Operations Management — 1987 — Vol. 7 — P. 33—45.

86. Talbot F.B. Resource-constrained project scheduling problem with time-resource tradeoffs: The non preemtive case // Management Science.— 1982.- Vol. 28, N 10.- P. 1197-1210.

87. Ullman J.D. NP-complete scheduling problems // J. Comput. System Sci.- 1975.- Vol. 10, N 4,- P. 384-393.

88. Yang K.K., Talbot F.B. and Patterson J.H. Scheduling a Project to Maximize Its Net Present Value: An Integer Programming Approach // Eur. Jour, of Oper. Res.- 1992,- Vol. 64,- P. 188-198.