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

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

/Г

Постовалова Ирина Павловна

СТРУКТУРНАЯ ОПТИМИЗАЦИЯ СЛОЖНЫХ СЕТЕВЫХ ПРОЕКТОВ

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

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

Челябинск-2005

Работа выполнена на кафедре информационных систем и технологий Челябинского института(ф) ГОУ ВПО «Российский государственный торгово-экономический университет».

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

наук, профессор Дыхнов Алексей Евгеньевич.

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

наук, профессор Мазуров Владимир Данилович,

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

Рольщиков Виктор Евгеньевич.

Ведущая организация: ГОУ ВПО «Челябинский

государственный педагогический университет».

Защита состоится " 25 " ь!АСиЯ_2005 г.

в Л часов на заседании диссертационного совета Д 212.296.02 по присуждению учёной степени кандидата физико-математических наук при ГОУ ВПО «Челябинский государственный университет» по адресу: 454021, г. Челябинск, ул. Братьев Кашириных, 129, ЧелГУ.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Челябинский государственный университет».

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

Ученый секретарь диссертационного совета

д-р физ.-мат. наук, профессор /^дО^?// /В.И. Ухоботов /

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

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

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

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

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

1 Основные положения по разработке и применению систем сетевого планирования и управления, 3 изд. - М.: Экономика, 1974. - 216 с.

критерию «время - затраты». Об актуальности данной оптимизации свидетельствуют труды ряда учёных: Wu Y and Li С (1994), Kamburowski J (1995), De P и другие (1995,1997), Demeulemeester E и другие (1996,1998), Skutella M (1998), Akkan С и другие (2000), Yang НН и Chen YL (2000), Vanhoucke M и другие (2002).

К сожалению, практически все доступные современные программы по СПУ не подсказывают оптимальные решения в части управления затратами (так же, как и по любому другому вопросу). Они лишь обеспечивают возможность достаточно серьёзного анализа отчётных и плановых показателей на основании данных графика. Это высказывание относится, в частности, к программе MS Project2. Переход от анализа «узких мест» к процессу принятия решения вызывает качественное усложнение - замену простой имитационной схемы производства его оптимизационной моделью. Такой метод управления проектами является, несомненно, полезным.

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

Цель работы. Упрощение структуры сложных сетевых графиков «работы - дуги» на этапах проектирования и оптимизации.

Методы исследования. Использован теоретико-множественный подход. Теоретические исследования проведены на базе методов теории ориентированных графов.

Научная новизна:

Разработаны новые методы структурной оптимизации:

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

десуперпозиции сети, основанный на итеративной комбинации последовательных и параллельных десуперпозиции (ППД), перемежаемых с модульной десуперпозицией;

У декомпозиции проекта на критическую и резервные подсети, заключающийся в удалении резервных и (или) стягивании насыщенных дуг с применением ППД (в том числе антипараллельной) при по-

2 Куперштейн В.И. Современные информационные технологии в делопроизводстве и управлении: Изучаем вместе с BHV.- СПб.: БХВ - С.-Петербург, 2000.-256 с.

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

Теоретическая и практическая ценность:

1. Результаты диссертации могут быть использованы для дальнейшего развития теории СПУ.

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

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

Реализация работы. Практическими результатами работы явились разработки математического и программного обеспечения по построению и оптимизации сетевой модели «работы - дуги», зарегистрированные в отраслевом фонде алгоритмов и программ (ОФАП) и в Информационно-библиотечном фонде РФ. Результаты используются при чтении лекций и выполнении лабораторно-практических занятий по дисциплине «Высшая математика» и «Экономико-математические методы» в РГТЭУ.

Апробация работы. Основные положения диссертационной работы докладывались на научно-технических конференциях, симпозиумах и методических семинарах: "International Conference Distributed Systems: Optimization and Economic-Environmental Applications" Ekaterinburg, 30 May-2 June 2000; конференция «Вычислительные технологии - 2000», Новосибирск; Всероссийская конференция «Алгоритмический анализ неустойчивых задач», Екатеринбург, 26 фев-раля-2 марта 2001 г.; Симпозиумы по прикладной и промышленной

3 Экономико-математическое моделирование: Учебник финансовой академии при правительстве РФ, рек. УМО по образованию для студентов вузов / Под общ. ред. И. Н. Дрогобыцкого. - М.: Изд-во Экзамен, 2004. - 800 с.

математике, Сочи, 2000, Самара, 2001, Сочи 2002; Сочи 2004, а также на научных конференциях и методических семинарах в ЧИ(ф) МГУК (РГТЭУ) 2000 - 2004 гг., семинарах ЧелГУ, ЮУрГУ 2004 г.

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

Структура и объём работы. Диссертация состоит из введения, четырёх глав, основных выводов, списка литературы и приложений. Работа изложена на 85 печатных листах формата А4 (размер шрифта - 14 пт, междустрочный интервал - полуторный), содержит 33 рисунка, 19 таблиц, списков литературы из 161 наименований и приложений на 30 страницах. Общий объём работы -115 страниц.

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

Во введении обоснована актуальность задач исследований, сформулирована цель, указаны методы и дан обзор результатов диссертации.

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

В пункте 1.1 сделан обзор методов СПУ. Современная теория СПУ состоит из двух этапов: построения сетевой модели комплекса работ (п. 1.1.1) и использования сетевой модели для планирования и управления при реализации комплекса работ (п. 1.1.2).

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

представленную парой номеров начального и конечного событий, принадлежащих множеству вершин новой сети типа «работы - дуги»4. Прежние дуги-связи называют фиктивными работами. Однако при этом резко увеличивается число узлов и дуг. Фиктивные работы - это просто связи, и функции на них не определены. Количество фиктивных работ стремятся сократить5.

4 Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.432 с.

5 Эддоус М, Стэнсфилд Р. Методы принятия решений / Пер. с англ. Под ред. член-корр. РАН И.И. Елисеевой. - М.: Аудит, ЮНИТИ, 1997.- 590 с.

Наиболее полные варианты сокращения предложены Разумо-вым И.М., Беловой Л.Д., Ипатовым М.И., Проскуряковым A.B. в их совместной работе6. Однако просматриваются две проблемы.

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

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

Среди большого списка просмотренной учебной и научной литературы нечто похожее удалось найти только в работе Гришина А.П. - это «синтез рёберной сетевой модели на основе расширения матрицы бинарных отношений непосредственного предшествования элементарных работ»7. Матричная форма трудно обозрима и затрудняет исключение ненужных элементарных фиктивных операций, а алгоритм составления матрицы смежности вершин, исходя из матрицы смежности рёбер, сложнее предлагаемого в диссертации нового элементарного алгоритма генераций событий. В работе Гришина А.П. рассмотрен неадекватный его же теории пример орграфа с орцикла-ми, который, очевидно, не может быть сетевым графиком. Также сформулирована теорема о правильной нумерации вершин орграфов, непригодная для сетей проектов: «для того, чтобы рёбра ориентированного графа можно было упорядочить, необходимо и достаточно, чтобы граф был деревом». Богомоловым А.М.8 доказана исчерпывающая теорема о том, что «в орграфе G существует правильная нумерация вершин тогда и только тогда, когда G - бесконтурный орграф».

Далее рассматривается комплексная оптимизация - процедура установления компромиссного соотношения между затратами и продолжительностью проекта.

6 Сетевые графики в планировании: Учеб. пособие / Разумов И.М., Белова Л.Д., Ипатов М.И., Проскуряков A.B. - 3-е изд., перераб. и доп. - М.: Высш. школа, 1981.-168 с.

7 Гришин AJI. Исследование операций, ч. 1. - М.: МАИ, 1975.

8 Богомолов A.M. Алгебраические основы дискретных систем. - М.: Наука: Физматлит, 1997. - 397 с.

В работе Филлипса Д. и Гарсиа-Диаса А.9 есть обзор зарубежных программ, в которых в той или иной форме определяется данный компромисс с использованием в них именно сетевых графиков «работы —дуги».

Классикой по решению данной задачи, позволяющей найти точный оптимум, является процедура, описанная в основополагающих статьях Келли и Уолкера, а также Фалкерсона, основанная на линейном программировании и осуществляющаяся с помощью потокового алгоритма в сети. Даже для лучших потоковых алгоритмов порядка 0(л3) с увеличением п возникает проблема упрощения структуры сети, потребность в десуперпозиционных и декомпозиционных методах.

И при небольших п целесообразно применение декомпозиционных методов. Например, в работе Разумова И.М., Беловой Л.Д. и других рассматривается алгоритм Келли для сетевого графика, представленного на рис. 1.1 (нумерация, как в диссертации), где над дугами указаны интервалы изменения продолжительностей работ, а работы (1,3), (0,2) неизменны.

Рис. 1.1. Сетевой график по алгоритму Келли

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

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

1. Разработка метода проектирования сетевой модели «работы -дуги» с возможно меньшим количеством фиктивных операций.

9 Филлипс Д., Гарсиа-Диас А- Методы анализа сетей: пер. с англ.- М.: Мир, 1984.

2. Структурная оптимизация сетевых графиков «работы - дуги» в оптимизационных алгоритмах с разработкой и применением декомпозиционных и десуперпозиционных методов.

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

Вторая глава посвящена эффективному синтезу сетевой модели «работы - дуги». В п.2.1 рассмотрено формирование сетевого графика «работы - дуги», исходя из списков предшественников. Обычно исходная информация о проекте представляется перечнем операций д,-, г = 1, ..., и. Для каждой д,- известен список (7(д,) предшествующих операций. В алгоритме предусмотрено формирование минимального списка <3_(аг) непосредственно предшествующих операций, а также полного списка б+(Д/) всех предшествующих операций. Заметим, что (7_(а/) = (?+(д,) = 0(а,)\ {а*}, где Г(д() - отображение, совпа-

дающее с минимальным списком последующих работ; 0(д,) - кон-традостижимое множество операции д,-.

Построение Сг_(а,) сводится к последовательному просмотру д,-, и исключению тех Д,- € С(а,), которые являются дальними предшественниками ((?*) других операций множества (?(а,). С этой целью, пока <7(д,) не стабилизируется, выполняются в цикле следующие действия:

Я/ 6 ОД) => ад = Ну, где Щ = ад\ о.у

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

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

Если Сг+(Д/) с (?+(д*), то добавляется всего одна фиктивная операция , при этом заменяется на <?_(«/))

При отсутствии вложенности добавляются две фиктивные операции а' и а": <?_(д') = (7_(д") = (?_(«,) п в_(ак); в_(д,) и в_(ак) заменяются на д' и и д" и

В п.2.3 рассмотрен новый простейший алгоритм генерации событий. После устранения пересечений множеств генерируются события по одному на каждую группу (?_(д,-) одинакового состава, начиная С (7_(а,)=0. Завершающее событие соответствует окончанию операций, для которых

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

Таблица 2.5 Пример_

щ с (ад (я,)

А, В, С - -

В В —

Е С,£> в

^ А, Б в

С Е с, о, в

Я А,Е с, д в

I А, в Е, С, Д В

3 А, И, В

к Е,3 ^ С, А, И, В

ь в, К Е, У, С, А, Д В

Таблица 2.6

Результаты вычислений _

а1 Начальные события Конечные события

А,ВГС„ - 0 зз^Ы, 3

Ж - ->1 ' 2

Е, С' \ V. С, Б' з X 5,8

Г, А', А" -------> 4 ' 8,6,7

С, Е', Е" Е 5 7,6,9

Н А',Е' 6 11

1,0' А",в 7 11,10

Р,С' 8 9

К Е\3 9 10

Ь в',К 10 И

£> 2 3,4

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

При учёте вложенностей (7+(Д() добавляются 8 фиктивных операций, иначе потребовалось бы 11 фиктивных операций.

Эффективность метода по уменьшению количества фиктивных работ проверена на нескольких важных классах тестовых задач, охватывающих практически все встречающиеся составные части проектов: класс задач со Ступенчатым Набором Предшественников из п

операций: ад=0,1< г < л; С(а,)=0 ^, и + 1 < I < 2и (СНПл); класс

задач с Полным Набором Предшественников из и операций (ПНПи); класс задач с (л - 1) Элементными Наборами Предшественников из п операций (л - 1ЭНПл)

При преобразовании типа сети задачи из класса СНПл добавляется минимальное количество: л — 1 фиктивная работа и л + 2 события вместо п(п + 1)/2 фиктивных работ и 4л событий при непосредственном преобразовании методом растяжения вершин. требует большого количества фиктивных операций. Но и в этом случае предложенный метод приводит к сокращению количества фиктивных работ до минимально возможного. Для ПНПл добавляется всего 2(2" - п -1) фиктивных операций из возможных я2л_1 связей. Для л-1ЭНПл аналогично 6л-12 вместо л2-л.

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

Глава 3 посвящена комплексной оптимизации проекта с выпуклой ломаной зависимостью (ВЛЗ) «стоимость - время».

В п.3.1 описан поиск минимального сечения в сети критических работ. Каждое звено ВЛЗ проекта характеризуется угловым коэффициентом ик и проекцией А на ось времени. Наибольшую трудность ♦ представляет определение параметра ик, соответствующего минимальному сечению сети проекта. Минимальное сечение находится из условия минимизации стоимости сокращения проекта на единицу времени за счёт работ сечения.

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

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

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

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

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

После того, как сечение резервной подсети определено, следует найти (п.3.3) условно-минимальную величину изменения длительности Л (лимит сечения подсети), при которой часть операций подсети становятся критическими.

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

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

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

шш К1к =Лк = шш Яц.

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

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

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

Глава 4 посвящена структурной оптимизация при реализации комплекса работ с разработкой и применением декомпозиционных и десуперпозиционных методов. В п.4.1 показана связь с методом диа-коптики. Термин «суперпозиция» встречается в работе Яблонского СВ.10, где рассматривается разложение сетей, основанных на неориентированных графах. Так как в ней структурный процесс идёт от подсетей (нетривиальных, неразложимых) к получению общей исходной сети, то говорится о суперпозиции. В диссертации с целью упрощения исходной сети, выделяется подсеть, которая заменяется квазидугой, и данный процесс продолжается до образования тривиальной сети. В этом случае можно говорить об обратной суперпозиции или десуперпозиции.

Ориентация сетей позволяет однозначно выделять в исходной сети неразложимые минимальные подсети, рассмотренные в разделе 4.2. которые могут быть трёх видов (см. рис. 4.1).

Назовём неразложимую подсеть, не сводимую к первому и второму виду, модулем.

ю

Яблонский С В. Введение в дискретную математику: Учеб. пособие для вузов /Под ред. В А Садовничего,- 3-е изд., стер. - М: Высш. шк., 2002,- 384 с.

50->0-Х)( * °<С1^0 {

а) б) в)

Рис. 4.1. Минимальные подсети:

а) подсеть последовательных операций;

б) подсеть кратных операций;

в) минимальный модуль

В п.4.3 представлен алгоритм десуперпозиции сети. Десуперпо-зиция сети сводится к повторению следующих этапов:

1. Если сеть тривиальная, то есть состоит только из одной операции (может быть обобщённой), то десуперпозиция заканчивается.

2. Последовательно объединяются минимальные подсети 1 и 2 вида в отдельные обобщённые операции. Назовём этот процесс последовательно-параллельной десуперпозицией (ППД). В силу элементарной структуры этих подсетей алгоритмы объединения выписываются явно.

3. Выделяется модуль.

4. Для модуля выполняется оптимизация потоковым алгоритмом или методом сечений11. В результате модуль заменяется отдельной обобщённой операцией.

5. Возврат к 1.

В п.4.4 описан алгоритм объединения нескольких последовательных операций, а в п.4.5 описан алгоритм объединения кратных операций.

Обратная суперпозиция модулей рассмотрена в п.4.6.

Рассматривается ациклический орграф (V; Е) с двумя полюсами: ^ (исхода) и I (захода). В п.4.6.1. сформулированы основные понятия.

Далее используем обозначения монографии Кристофидеса Н. • для множеств достижимостии контрадостижимости Приводим эквивалентное определение множества вершин, достижимых из множества Л:

11 Дыхнов А. Е. Оптимальное сетевое планирование методом сечений. В сб. Ученые записки Ур СЭИ АТиСО. Вып. II -Челябинск, 1999-С. 125-129.

Совокупность формул (4.1) может быть использована как шаблон для определения других функций. Так определение контрадости-жимых множеств О*(5), 0(5) получается заменой Г на Г" (и, разумеется, Я на О).

Введём дополнительно функции «достижимость только» из множества Л', - обозначим и «контрадостижимость только» из Л' - О! (5), являющиеся сужением указанных выше функций. Их определения получаются заменой Г на Г! и Г '!, где Г !(5) = Г(£) \ Г(Г' (Г(5)) \ Я); Г"1 !(5) = Г"1 (5) \ Г'1 (Г(Г1 (5)) \ 5)

Для последних функций уместны и более простые выражения, например, для но приведён-

ные выше требуют, вообще говоря, меньше операций. Удобны также функции:

= Б; (7(5) = 0(5) ХБ; Р!(5) = К!(5) \ 8; С!(5) = 0!(5)\Б.

Далее используется дополнительное сужение функций за счёт удаления из К подмножества НУ: Г^]-))^), Л^-чЖ) и так далее. Функции, определённые на подмножестве А С V, обозначаются аналогично: Г(8|Л), £(5 ¡Л)...

Пусть Ни К- Начальная и Конечная вершины модуля. Рассмотрен ряд лемм с доказательствами.

Лемма 4.1. Среди вершин модуля, смежных началу Н(концу К), существует вершина с полустепенью захода (исхода) единица, что эквивалентно утверждению: |Г! (Н) ] > 0, (| Г"1! (К) | > 0).

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

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

Введём обозначения для следующих множеств:

1) ГПН и ВПК - Группа из нескольких ПН и Все ПН для рассматриваемой Я.

2) Р=Ни ГПН - Росток возможного модуля.

3) .МД = Ли(Г(Я) \ Я(ГПН)))) - Множество вершин возможного модуля (кроме К и других ПН £ Р), Достижимых только из вершин

4) T=mHKJ МД- Тело возможного модуля.

5) СД = ^(Т)- Слой, Достижимый из Г, из которого удалены

вершины v е Т. Согласно монографии Кристофидеса Н. слой - это множество таких вершин х}, которые достижимы из вершин Xt е Т с использованием путей (орцепей) длины 1, то есть существуют дуги (х„ Xj). В работе12 множество таких вершин называется 1-ым ярусом. В работе1 - 1-ым слоем.

Лемма 4.2. Вершина не может бьпь одновременно ПослеНача-лом и ПредКонцом: ПН * ПК.

Назовём ГПН минимальной, если никакому подмножеству ГПН не соответствует модуль. В п.4.6.2 доказывается основная теорема и обосновывается замечание.

Теорема 4.1. Для того чтобы подграф был модулем, необходима и достаточна представимость множества его вершин в виде списка {#, ГПН, МД, СД}, где \сд\ = 1, а ГПН-минимальна.

Замечание. Если \ СД\ > 1 и СД содержит вершину К* (возможный конец), достижимую только из МД, то К* не может быть концом какого-либо модуля (СД следует почистить, переведя К* в МД).

В п.4.6.3 доказываются леммы и производится оценка количества Групп из ПослеНачал (ГПН).

Лемма 4.3. Для V ///// соответствующий слой СД не пуст:

\сд\ >0

Лемма 4.4. При разбиении Группы ПослеНачал модуля (ГПН) на две непересекающиеся части ГПНХ и ГПН2 соответствующие слои СД„ / = 1, 2 имеют кроме К и другие точки пересечения, или

Следствие. Если слои СД\ (для ГПН{) и СД2 (для ГПН2) не пересекаются, то объединению ГПН = ГПН\ и ГПЩ не соответствует модуль! Поэтому не нужно просматривать все подмножества ВПН для выявления модуля. Не имеет смысла объединять два подмножества с непересекающимися слоями СД.

Для оценки количества подмножеств / ////при выявлении модуля рассмотрен пример сети с ПослеНачалами, изображённой на

12 Князев A.B. Верхние оценки экспонентов псевдосимметрических графов // Дискретная математика. -М.: Наука, 1990, том 2, вып. 4,- С. 63-71.

13 Карзанов A.B. Нахождение максимального потока в сети методом предпото-ков.-ДАН СССР, 1974, том 215, № 1.-С. 49-53.

16

{2&+2}. Вершина (2А+2), являющаяся стоком, представлена в виде выделенного кольца, благодаря чему изображение сети имеет центральную симметрию к-то порядка относительно вершины 1 - истока.

Для этой сети с количеством вершин и количеством

дуг ш — 4к лемма 4.4 позволяет уменьшить количество проверяемых подмножеств ГПНс (2* - 1) при полном переборе до (к1 - к + 1), то есть задача имеет полиномиальную сложность.

Рис. 4.12. Пример сети с центральной симметрией -го порядка

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

1. Выполнить ППД, которую следует также выполнять после образования каждой М-дуги.

2. Найти Я, К по соответствующим множествам ПН, ПК.

3. Построить списки {Н, ПН, МД, СД), начиная со списков, не содержащих других Я; почистить СД.

4. Используя теорему 4.1 и замечание к ней, выделить модули, либо исключить К, ПН, или Я из рассмотрения, после чего скорректировать списки.

5. Рекурсивно пересматривать списки, объединяя ГПН с пересекающимися СД, пока не будет исчерпано 2777Ядля каждой Н.

Грубая оценка сверху для количества операций: 0(тп2), так как

2

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

В п.4.6.6 показано, что алгоритм с оценкой О (тп) можно получить, заменив пункты алгоритма 3, 4, 5 следующим итерационным процессом с удалением пройденных дуг. Количество проверяемых

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

Рассмотрим следующий итерационный процесс:

= и(Г(#) \ Я(ГПН))))\-пУк)\Ы+(Н)),

Здесь Н - возможное начало с наибольшим номером (подразумевается правильная нумерация), начальная группа ГПН - произвольное ПослеНачало ПН, начальное множество .У - росток {Я, ПН). Я+(Я) - Множество вершин с номерами, не меньшими номера Н, 7/_(Я) - соответствующее дополнение. Итерации продолжаются, пока S увеличивается.

Далее рассматривается пограничное множество Z, состоящее из элементов Я, (8) с положительной степенью. Zестественным образом разбивается на два подмножества

верхняя доля разреза, порождённого разбиением , за вычетом

Я.

В зависимости от конфигурации Zпpинимaютcя решения об исключении элементов из множеств УН,УК,Упн, Упк:

1. г.пГ = 0л\г+\ = 1. Найден модуль (Н-К), где К = 2+. ГПН,

ГПК аннулируются. Если ГПН = ВПН (ГПК = ВПК), то аннулируется Я (или соответственно К)...

Применение итерационного процесса к фрагменту сети выполнено в п ,4,6,7,

В п.4.7 рассмотрен декомпозиционный метод удаления и (или) стягивания дуг - операций, а также антипараллельная десуперпози-ция.

Далее употребляется кусочно-постоянная производная которая задаётся двумя возрастающими последовательностями чисел - абсцисс границ 5* звеньев ломаной и их угловых коэффициентов о*. В процессе оптимизации удобно вместо длительности Ц операции и её полного резерва использовать одну сборную переменную

- номера начального и конечного событий для работы (},]),

^тпах

- наибольшая длительность работы,

-ранний срок начального события,

18

/" - поздний срок конечного события.

При Еу ^ 0 эта переменная равна текущему значению времени . сокращения (?,™ах - ^) длительности операции. При е,у < 0 длительность операции максимальна, а модуль | Е,у | равен полному резерву операцииЛу.

Представим с'(0 в виде перемежающейся последовательности: -оо (0) 0 (01) 81 (^2) 5г ... (Ащ) 5т. В скобках стоят угловые коэффициенты: 0<а\<а2< ... Справа и слева от углового коэффициента записаны границы соответствующих интервалов для е. Переменная е двойственна потоковой переменной ф.

На отдельных этапах оптимизации возможно дополнительное упрощение сети проекта за счёт операций, длительность которых не изменяется. На начальном этапе часто многие операции имеют резервы , и на стадии определения минимального сечения соответствующие дуги целесообразно удалить из сети. Для последующих этапов оптимизации характерны операции с предельным сокращением (е = Ьт). Положительные пересечения таких дуг - операций запрещены, что упрощает поиск минимального сечения.

Среди несокращаемых дуг выделим те, для которых запрещены или невозможны также отрицательные пересечения. Примерами таких дуг с запрещённым пересечением могут служить: а) дуги, инцидентные полюсам, то есть начальные и заключительные операции;

б) дуги наружного контура плоской сети для планарных графов;

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

Подсеть, полученную удалением резервных дуг и

стягиванием несокращаемых дуг (8 = бщах) будем называть й-сегью. К л «сети может быть применена ППД. Удаление дуг не вызывает дополнительных трудностей, но при слиянии вершин возможен вариант антипараллельной десуперпозиции, не встречавшийся ранее в п.4.2 -4.6. Удалось её обобщить с параллельной десуперпозицией.

Пусть - множество номеров параллель-

ных (/ е / и антипараллельных (/ 6 I") дуг, вообще говоря, обобщённых (квазидуг). Начало квазидуги определяется минимальным номером среди слитых вершин, инцидентных дуге. К очередному

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

Здесь

г, = mах min уу; г2 = min max yi}; у = Я, (t{J - е{).

В свою очередь [т^тд] - сегменты значений параметров сокращения составляющих квазидуг,

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

. раций:

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

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

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

2. Предложен метод десуперпозиции сети, для которого:

2.1. Представлены новые функции, определённые на подмножестве Л' вершин графа: - «достижимость только» из 5, 0!(£) -«контрадостижимость только» из S.

2.2. Разработаны методы следующих десуперпозиций сетевых графиков «работы - дуги»: последовательно-параллельной (ППД) и модульной.

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

3. Рассмотрена декомпозиция проекта на критическую и резервные подсети, а именно:

3.1. Разработан декомпозиционный метод удаления резервных и (или) стягивания насыщенных дуг с применением ППД (в том числе антипараллельной) при поиске минимального сечения.

3.2. Предложен эффективный (по количеству операций) алгоритм выравнивания минимальных резервов вместо МКП для пересчёта резервов.

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

Представленные в п.2-3 методы использованы для решения задачи комплексной оптимизации проекта с ВЛЗ «стоимость - время».

Список основных публикаций по теме диссертации:

1. Дыхнов А.Е., Постовалова ИЛ. Формирование сетевой модели с минимумом фиктивных операций // Электронные публикации докладов конференции Вычислительные технологии - 2000.- Новосибирск, ИВТ СО РАН, 2000 - http://www.ict.nsc.ru/ws/ct-2000.

2. Дыхнов А.Е., Постовалова И.П. Эффективный алгоритм формирования сети «дуга-работа» // Обозрение прикладной и промышленной математики: Тез. докл. Первого Всерос. Симпозиума в Сочи. - М.: Научное изд-во ТВП, 2000, том 7, вып. 2. - С. 341-342-Деп. в ВИНИТИ РАН, Вычислительные науки: 01.03-93.328.

3. Дыхнов А.Е., Постовалова И.П. Минимальное сечение сети проекта // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. - Екатеринбург: Изд-во Урал, ун-та, 2001. -С. 210-211.

4. Дыхнов А.Е., Постовалова И.П. Расчет резервов работ при оптимизации проекта // Научный вестник. - Челябинск, ЧИ МГУК, 2001,№1.-С.77-78.

5. Дыхнов А.Е., Постовалова И.П. Декомпозиция при оптимизации проекта с выпуклой кривой минимальной стоимости // Обозре-

ние прикладной и промышленной математики: Тез. докл. Второго Всерос. Симпозиума в Самаре.-М.: Научное изд-во ТВП, 2001, том 8, вып. 1. - С. 161- Деп. в ВИНИТИ РАН, Вычислительные науки: 02.07-93.295.

6. Дыхнов А.Е., Постовалова И.П. Обратная суперпозиция ациклической двухполюсной сети // Обозрение прикладной и промышленной математики: Тез. докл. Третьего Всерос. Симпозиума в Сочи. - М.: Научное изд-во ТВП, 2002, том 9, вып. 3- С. 608. - Деп. в ВИНИТИ РАН, Вычислительные науки: 04.02-93.527.

7. Дыхнов А.Е., Постовалова И.П. Удаление или стягивание дуг - операций при оптимизации проекта // Обозрение прикладной и промышленной математики: Тез. докл. Третьего Всерос. Симпозиума в Сочи. - М: Научное изд-во ТВП, 2002, том 9, вып. 3. - С. 608-609.

8. Дыхнов А.Е., Постовалова И.П. Декомпозиция проекта при удалении или стягивании дуг-операций // Научный вестник. - Челябинск, ЧИ (ф) РГТЭУ, 2003, № 3. - С. 81-85.

9. Дыхнов А.Е., Постовалова И.П. Сечение резервной подсети проекта // Научный вестник. - Челябинск, ЧИ (ф) РГТЭУ, 2003, № 3.-С. 79-81.

10. Дыхнов А.Е., Постовалова И.П. Эффективный синтез сетевой модели «Работы-Дуги» // Свидетельство об отраслевой регистрации разработки № 2687, 17.06.2003. - Москва, МОРФ, ГКЦИТ, ОФАП, 2003.

11. Дыхнов А.Е., Постовалова И.П. Эффективный синтез сетевой модели «Работы-Дуги» // Государственная регистрация в Информационно-библиотечном фонде РФ: № 50200300521, 24.06.2003-Москва, МОРФ, ГКЦИТ, 2003.

12. Дыхнов А.Е., Постовалова И.П. Функция «достижимость только» при десуперпозиции ациклических орграфов // Обозрение прикладной и промышленной математики: Тез. докл. Пятого Всерос. Симпозиума в Сочи-Москва, Научное изд-во ОПиПМ, 2004, том 11, вып. 4.-С. 795-796.

13. Постовалова И.П. Последовательно-параллельная декомпозиция проекта // Научный вестник. - Челябинск, ЧИ (ф) МГУК, 2001, №1.-С. 79-80.

14. Дыхнов А. Е., Постовалова И. П. Десуперпозиция ациклических двухполюсных сетей // Электронный журнал: Известия Челябинского научного центра. - Челябинск, 2005, вып. 1(27). - С. 13-18.

Подписано в печать 15.04.2005 г. Формат 60x90 У\б. Усл.печл. 1,38. Уч.-изд. л. Тираж 100 экз. Заказ . Бесплатно.

ГОУ ВПО «Челябинский институт (ф) РГТЭУ» 454091 ул. Орджоникидзе 50, Челябинск

Of. M-Of. S3

ВВЕДЕНИЕ

1. ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.1. Обзор методов сетевого планирования и управления (СПУ)

1.1.1. Построение сетевой модели комплекса работ. Типы сетевых графиков и их преобразования

1.1.2. Использование сетевой модели для планирования и управления при реализации комплекса работ

1.2. Задачи исследования

2. ЭФФЕКТИВНЫЙ СИНТЕЗ СЕТЕВОЙ МОДЕЛИ «РАБОТЫ - ДУГИ»

2.1. Формирование сетевого графика «работы - дуги», исходя из списков предшествующих операций

2.2. Алгоритм добавления фиктивных операций с целью исключения пересечений списков предшественников

2.3. Генерация событий

2.4. Эффективность метода

2.5. Порядок сравнения списков предшествующих операций

3. КОМПЛЕКСНАЯ ОПТИМИЗАЦИЯ ПРОЕКТА С ВЫПУКЛОЙ ЛОМАНОЙ ЗАВИСИМОСТЬЮ (ВЛЗ) «СТОИМОСТЬ - ВРЕМЯ»

3.1. Поиск минимального сечения в сети критических работ

3.2. Сечение резервной подсети проекта

3.3. Накопительный итерационный метод для определения лимита сечения резервной подсети

3.3.1. Алгоритм выравнивания минимальных резервов

3.3.2. Пример по накопительному итерационному методу

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

4. СТРУКТУРНАЯ ОПТИМИЗАЦИЯ ПРИ РЕАЛИЗАЦИИ КОМПЛЕКСА РАБОТ С РАЗРАБОТКОЙ И ПРИМЕНЕНИЕМ ДЕСУПЕРПОЗИ

ЦИОННЫХ И ДЕКОМПОЗИЦИОННЫХ МЕТОДОВ

4.1. Понятие метода диакоптики

4.2. Минимальные подсети

4.3. Алгоритм десуперпозиции сети

4.4. Алгоритм объединения нескольких последовательных операций

4.5. Алгоритм объединения кратных операций

4.6. Десуперпозиция модулей

4.6.1. Основные понятия

4.6.2. Основная теорема

4.6.3. Оценка количества Групп из ПослеНачал (ГПН)

4.6.4. Алгоритм выделения модулей

4.6.5. Пример к алгоритму с оценкой С? (тп )

4.6.6. Итерационный процесс с удалением пройденных дуг

4.6.7. Применение итерационного процесса к фрагменту сети

4.7. Удаление и (или) стягивание дуг-операций и антипараллельная де-суперпозицией

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

Актуальность темы. В эпоху рыночных экономических отношений возрастает роль эффективных сетевых проектов, используемых экономистами, финансистами, политиками, учеными, инженерами и другими специалистами во всех сферах общественной и производственной деятельности. Об этом свидетельствует появление множества программных продуктов по сетевому планированию и управлению (СПУ): за рубежом [39, 54], а в России - следующих наиболее доступных пользователю: Microsoft Project, Project Expert, Time Line, Project Management Software, Primavera Project Planner, Галактика, Проект-Менеджмент и других.

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

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

В основных положениях по разработке и применению СПУ [74], а также в существующих методах СПУ [14, 55, 66, 71, 100, 105, 108] отсутствуют методы, алгоритмы и программы по построению эффективных сетевых графиков сложных проектов типа «работы - дуги» с минимальным количеством фиктивных работ. Построение сетевых моделей базируется на использовании ряда правил, на опыте и знаниях ответственного исполнителя, логически выстраивающего технологические цепочки последовательности работ [10, 44, 80, 91]. При этом имеет место многовариантность и большая трудоемкость процесса проектирования. Так, например, для проекта со ступенчатым набором предшественников из п операций количество фиктивных операций может изменяться от порядка линейного до я2, а для проекта с полным набором предшественников из п операций, частью которого является любой другой проект, может изменяться от 2{Т- п -1) до пТ~\

Структурная оптимизация сетевых графиков «работы - дуги» на этапе проектирования, приводящая к уменьшению количества вершин и дуг сети, способствует также повышению эффективности их реализации в оптимизационных алгоритмах. Такие двухполюсные сети используются, например, при оптимизации сетевых графиков по критерию «время - затраты». Об актуальности данной оптимизации свидетельствуют труды ряда учёных: Wu Y and Li С (1994), Kamburowski J (1995), De Р и другие (1995, 1997), Demeulemeester Е и другие (1996, 1998), Skutella М (1998), Akkan С и другие (2000), Yang НН и Chen YL (2000), Vanhoucke М и другие (2002).

К сожалению, практически во всех доступных современных программах по СПУ [59, 80, 99] не подсказываются оптимальные решения в части управления затратами (так же, как и по любому другому вопросу). Они лишь обеспечивают возможность достаточно серьёзного анализа отчётных и плановых показателей на основании данных графика. Переход от анализа «узких мест» к процессу принятия решения вызывает качественное усложнение - замену простой имитационной схемы производства его оптимизационной моделью. Такой метод управления проектами является, несомненно, полезным.

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

1) На практике приходится рассматривать все более сложные проекты, при этом теряется наглядность и возможность увидеть структуру сети непосредственно.

2) Производство требует оперативного управления, поэтому время и стоимость сетевого планирования должны быть по возможности малыми, то же можно сказать о времени и стоимости самого производства.

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

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

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

Цель работы. Упрощение структуры сложных сетевых графиков «работы - дуги» на этапах проектирования и оптимизации.

Методы исследования. Использован теоретико-множественный подход. Теоретические исследования проведены на базе методов теории ориентированных графов.

Численный анализ сетевых моделей проведён на ЭВМ с использованием принципов построения программного обеспечения [48, 50, 60, 77].

Научная новизна:

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

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

Теоретическая и практическая ценность:

1. Результаты диссертации могут быть использованы для дальнейшего развития теории СПУ.

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

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

Реализация работы. Практическими результатами работы явилисьразра-ботки математического и программного обеспечения по построению и оптимизации сетевой модели «работы - дуги», зарегистрированные в отраслевом фонде алгоритмов и программ (ОФАП) и в Информационно-библиотечном фонде РФ. Результаты использованы в научно-исследовательских работах, выполняемых на кафедре «Информационные системы и технологии» Челябинского института (филиала) Московского государственного университета коммерции (Российского государственного торгово-экономического университета) в 20002004 г.г., а также используются при чтении лекций и выполнении лабораторно-практических занятий по дисциплине «Высшая математика» и «Экономико-математические методы».

Апробация работы. Основные положения диссертационной работы докладывались на научно-технических конференциях, симпозиумах и методических семинарах: "International Conference Distributed Systems: Optimization and Economic-Environmental Applications" Ekaterinburg, 30 May-2 June 2000; конференция «Вычислительные технологии - 2000», Новосибирск; Всероссийская конференция «Алгоритмический анализ неустойчивых задач», Екатеринбург, 26 февраля-2 марта 2001 г.; Симпозиумы по прикладной и промышленной математике, Сочи, 2000, Самара, 2001, Сочи 2002; Сочи 2004, а также на научных конференциях и методических семинарах ЧИ (ф) МГУК (РГТЭУ) в 2000 -2004 г.г., семинарах ЧелГУ, ЮУрГУ 2004 г.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

2. Предложен метод десуперпозиции сети, для которого:

2.1. Представлены новые функции, определённые на подмножестве S вершин графа: R\(S) - «достижимость только» из S, Q!(5) - «контрадостижи-мость только» из S.

2.2. Разработаны методы следующих десуперпозиций сетевых графиков «работы - дуги»: последовательно-параллельной (ППД) и модульной.

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

3. Рассмотрена декомпозиция проекта на критическую и резервные подсети, а именно:

3.1. Разработан декомпозиционный метод удаления резервных и (или) стягивания насыщенных дуг с применением ППД (в том числе антипараллельной) при поиске минимального сечения.

3.2. Предложен эффективный (по количеству операций) алгоритм выравнивания минимальных резервов вместо МКП для пересчёта резервов.

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

Представленные в п.2-3 методы использованы для решения задачи комплексной оптимизации проекта с BJ13 «стоимость - время».

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. -М.: Наука, 1975- 119 с.

2. Алгоритмы и программы решения задач на графах и сетях / Нечепу-ренко М.И., Попков В.К., Майнагашев С.М. и др. Новосибирск: Наука (Сиб. отд-ние), 1990.-513 с.

3. Алексеев A.M., Козлов Л.А., Крючков В.Н. Сетевые модели в перспективном планировании развития производства. Новосибирск: Наука, 1974. - 110с.

4. Андрианова Г. Сетевое планирование в новых условиях экономического стимулирования НИИ и КБ. М.: ВНИИЭМ, 1969- 26 с.

5. Басакер Ф., Саати Т. Конечные графы и сети. М.: Наука, 1974.

6. Батищев Д.И., Старостин Н.В. Задачи декомпозиции графов: Методические указания по проведению лабораторных работ: электронный вариант метод пособия. Нижегородский Госуниверситет, 2001 - 13 с.

7. Бергман А.К. Экономико-математическое моделирование производственных систем: Проблемы народнохозяйственного и отраслевого развития: Учеб. пособие. М.: МАДИ, 1987.- 56 с.

8. Богомолов A.M. Алгебраические основы дискретных систем. М.: Наука: Физматлит, 1997.-397 с.

9. Бурков В.Н., Ланда Б.Д., Левецкий С.Е. Сетевые модели и задачи управления. М.: Советское радио, 1967 - 144 с.

10. Вишнякова О.М. Комплексная практическая задача по сетевому планированию и управлению: Учеб. пособие. Челябинск: ЧГТУ, Златоустовский фил каф. экономики, 1997 - 14 с.

11. Гилл, Филип и др. Практическая оптимизация М.: Мир, 1985.

12. Глесневич Г.С., Сапаров М.С. Алгоритмы в теории графов. Ашхабад: Ылым, 1981.

13. Гришин А.П. Исследование операций, ч. 1. -М.: МАИ, 1975.

14. Губин Н.М., Добронравов А.С., Дорохов Б.С. Экономико-математические методы и модели в планировании и управлении в отрасли связи. М.: Радио и связь, 1993.

15. Дыхнов А.Е. Оптимальное сетевое планирование методом сечений. В сб. Ученые записки Ур СЭИ АТиСО. Вып. II . Челябинск, 1999. - С. 125— 129.

16. Дыхнов А.Е., Постовалова И.П. Формирование сетевой модели с минимумом фиктивных операций // Электронные публикации докладов конференции Вычислительные технологии 2000. - Новосибирск, ИВТ СО РАН, 2000 - http://www.ict.nsc.ru/ws/ct-2000.

17. Дыхнов А.Е., Постовалова И.П. Минимальное сечение непланарной сети дерево двойственного графа // Электронные публикации докладов конференции Вычислительные технологии - 2000. - Новосибирск, ИВТ СО РАН, 2000 - http://www.ict.nsc.ru/ws/ct-2000.

18. Дыхнов А.Е., Постовалова И.П. Эффективный алгоритм формирования стрелочных сетевых графов с минимумом фиктивных операций // Материалы межвузовской научно-методической конференции, посвященной 70-летию МГУК. Челябинск: Челяб. ин-т МГУК, 2000. -С. 87-89.

19. Дыхнов А.Е., Постовалова И.П. Метод сечений при оптимизации не-планарных сетевых графов // Обозрение прикладной и промышленной математики: Тез. докл. Первого Всерос. Симпозиума в Сочи. Москва, Научное изд-во ТВП, 2000, том 7, вып. 2. - С. 340-341.

20. Дыхнов А.Е., Постовалова И.П. Сечение непланарной сети при оптимизации проекта // Экономика и социум на рубеже XX-XXI веков: Тезисы участников научной конференции, посвященной 40-летию ЧИ (ф) МГУК. Челябинск: ЧИ (филиал) МГУК, 2001. - С. 122-123.

21. Дыхнов А.Е., Постовалова И.П. Декомпозиция при оптимизации стоимости проекта // Экономика и социум на рубеже XX-XXI веков: Материалы научной конференции, посвященной 40-летию ЧИ (ф) МГУК. Челябинск: ЧИ(ф)МГУК, 2001.-С. 123-124.

22. Дыхнов А.Е., Постовалова И.П. Минимальное сечение сети проекта // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. -Екатеринбург: Изд-во Урал, ун-та, 2001. С. 210-211.

23. Дыхнов А.Е., Постовалова И.П. Расчет резервов работ при оптимизации проекта // Научный вестник. Челябинск, ЧИ МГУК, 2001, № 1. - С. 77-78.

24. Дыхнов А.Е., Постовалова И.П. Антипараллельная декомпозиция проекта при коллапсировании дуг-операций // Экономика и социум на рубеже веков: сборник тезисов участников межвузовской научной конференции. — Челябинск: ЧИ (ф) .МГУК, 2002. С. 129-131.

25. Дыхнов А.Е. , Постовалова И.П. Подграф некритических операций проекта // Экономика и сопиум на рубеже веков: сборник тезисов участников межвузовской научной конференции. Челябинск: ЧИ (филиал) МГУК, 2002. — С.127-129.

26. Дыхнов А.Е., Постовалова И.П. Генерация событий проекта исключением пересечений списков предшественников // Экономика и социум на рубеже веков: Материалы научной конференции ЧИ (ф) РГТЭУ. Челябинск: ЧИ (ф) РГТЭУ, 2003. - С. 220-222.

27. Дыхнов А.Е., Постовалова И.П. Обратная суперпозиция модулей // Экономика и социум на рубеже веков: Материалы научной конференции ЧИ (ф) РГТЭУ. Челябинск: ЧИ (ф) РГТЭУ, 2003. - С. 222-224.

28. Дыхнов А.Е., Постовалова И.П. Декомпозиция проекта при удалении или стягивании дуг-операций // Научный вестник. Челябинск, ЧИ (ф) РГТЭУ, 2003, №3.-С. 81-85.

29. Дыхнов А.Е., Постовалова И.П. Сечение резервной подсети проекта // Научный вестник. Челябинск, ЧИ (ф) РГТЭУ, 2003, № 3. - С. 79-81.

30. Дыхнов А.Е., Постовалова И.П. Эффективный синтез сетевой модели «Работы-Дуги» // Свидетельство об отраслевой регистрации разработки № 2687, 17.06.2003. Москва, МОРФ, ГКЦИТ, ОФАП, 2003.

31. Дыхнов А.Е., Постовалова И.П. Эффективный синтез сетевой модели «Работы-Дуги» // Государственная регистрация в Информационно-библиотечном фонде РФ: № 50200300521, 24.06.2003. Москва, МОРФ, ГКЦИТ, 2003.

32. Дыхнов А.Е., Постовалова И.П. Структурная оптимизация сетевых моделей // Моделирование финансово-экономической деятельности предприятия в современных условиях: Материалы научной конференции ЧИ (ф) РГТЭУ. Челябинск: ЧИ (ф) РГТЭУ, 2004.- С. 219-220.

33. Дыхнов А. Е., Постовалова И. П. Десуперпозиция ациклических двухполюсных сетей // Электронный журнал: Известия Челябинского научного центра. Челябинск, 2005, вып. 1(27). - С. 13-18.

34. Дитхели, Герд. Управление проектами в 2 томах. М.:Бизнес-пресс, 2003. - 688 с.

35. Евстигнеев В.А. , Касьянов В.Н. Базисные алгоритмы обработки без-контурных графов. Новосибирск: ИСИ СО РАН, 1995.

36. Ермольев Ю.Н. Математические методы исследования операций-Киев, 1979.

37. Замбицкий Д.К., Лозовану Д.Д. Алгоритмы оптимизационных задач на сетях. Кишинёв: Штиинца, 1983.

38. Зыков А.А. Основы теории графов. М.: Наука, 1987. - 380 с.

39. Иваненко И.Н. Машинная обработка экономической информации: Учеб. пособие. Л.: ЛФЭИ, 1988. - 50 с.

40. Исследование операций / Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981, том 2.-677 с.

41. Исследование операций в экономике: Учебн. пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера.- М.: Банки и биржи, ЮНИТИ, 1997. 407 с.

42. Исследования по дискретной оптимизации / Под ред. Фридман М.Н. -М.: Наука, 1976.

43. Йенсен П.А., Барнес Д.В. Потоковое программирование. М.: Радио и связь, 1984.-391 с.

44. Карзанов А.В. Нахождение максимального потока в сети методом предпотоков. ДАН СССР, 1974, том 215, № 1. - С. 49-53.

45. Кнут Д.Е. Искусство программирования для ЭВМ. М.: Мир, 1976.

46. Князев А.В. Верхние оценки экспонентов псевдосимметрических графов // Дискретная математика. -М.: Наука, 1990, том 2, вып. 4. С. 63-71.

47. Конюховский П.В. Математические методы исследования операций в экономике. Спб.: Питер, 2000. - 208 с.

48. Кормен Т., Лайзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 с.

49. Кочетков А.И., Никешин СМ., Рудаков Ю. П. и др. Управление проектами (зарубежный опыт). Санкт-Петербург: ДваТрИ, 1993. - 446 с.

50. Кофман А.Г. Методы и модели исследования операций. М.: Мир,1975.

51. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

52. Крон Г. Исследование сложных систем по частям (диакоптика): Пе-рев. с англ. Москва, Наука, 1972. - 544 с.

53. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. — М.: Радио и связь, 1984.

54. Куперштейн В.И. Современные информационные технологии в делопроизводстве и управлении: Изучаем вместе с BHV. СПб.: БХВ- Санкт-Петербург, 2000. - 256 с.

55. Липский В. Комбинаторика для программистов. М.: Мир, 1988.213 с.

56. Лисогор С. М. Управление, планирование и организация строительством с помощью ЭВ техники и средств автоматизации (обзор). М., 1972.

57. Магрупов Т.М. Графы, сети, алгоритмы и их приложения. Ташкент: Фан., 1990. - 120 с.

58. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир,1981.

59. Маклаков С.В. Моделирование бизнес-процессов с Allfusion Process Modeler (BPwin 4.1). M.: Диалог-МИФИ, 2003.

60. Моделирование управленческого решения / Гаврилин Ю.Ф., Зонов В. Л. Челябинск: ЮурГУ, 1999. - 81 с.

61. Модер Дж., Филипс С. Метод сетевого планирования и организация работ. Москва-Ленинград: Энергия, 1966.

62. Нефёдов В.Н. Алгоритмический подход к решению задач теории графов и сетей. М.: Изд-во МАИ, 1990. - 63 с.

63. Нефёдов В.Н. Дискретные задачи оптимизации: Учеб. пособие. М.: Изд-во МАИ, 1993. - 59 с.

64. Новицкий Н.И. Сетевое планирование и управление производством: Учеб.-практ. пособие. М.: Новое знание, 2004. - 159 с.

65. Онуфриев И.А., Сашенков М.С. Опыт применения сетевых графиков в промышленном строительстве. -М.: Стройиздат, 1968.

66. Опыт применения экономико-математических методов в управлении строительным производством / Вьюгин Ю.Н., Науменко И.Х., Путяков К.П. — М.: Стройиздат, 1972. 119 с.

67. Организация и планирование предприятий чёрной металлургии / Мете А.Ф., Штец К.А., Бельгольский Б.П. , Щепилов Ф.И. М.: Металлургия, 1986. -560 с.

68. Оре, Ойстин. Теория графов. М.: Мир, 1980.

69. Основные положения по разработке и применению систем сетевого планирования и управления, 3 изд. -М.: Экономика, 1965, (1974). 216 с.

70. Пападимитриу, Христос X. Комбинаторная оптимизация. М.: Мир,1985.

71. Постовалова И.П. Последовательно-параллельная декомпозиция проекта // Научный вестник. Челябинск, ЧИ (ф) МГУК, 2001, № 1. - С. 79-80.

72. Построение и анализ вычислительных алгоритмов / Ахо А. и др. М.: Мир, 1979.

73. Практикум по организации и планированию машиностроительного производства / Грачёва К.А., Некрасова Л.А., Ипатов М.И. и др.; Под ред. Скворцова Ю.В. и Некрасова Л.А. М.: Высш. шк., 1990. - 224 с.

74. Прикладные задачи оптимального управления: модели, методы, алгоритмы / Отв. ред. Кротов В.Ф., Пятницкий Е.С. М.: ИПУ, 1990.

75. Применение сетевых графиков в строительстве (с использованием ЭВМ) / Розаев Ю.Е., Сосков В.И. М.: Изд-во Всесоюзн. заочн. Политехи, инта, 1990. - 133 с.

76. Пучнина Т.С. Управление проектами на основе новых информационных технологий: Уч. пос. Хабаровск: ДВГУПС, 1999. - 108 с.

77. Разу M.JI. и др. Модульная программа для менеджеров. Управление программами и проектами. М.: Инфра-М, 2000.

78. Руководство к решению задач по математическому программированию: Учеб. пособие / А.В. Кузнецов, Н.И. Холод, JI.C. Костевич; Под общ. ред. А.В. Кузнецова 2-е изд., перераб. и доп. -Мн.: Выш. шк., 2001. - 448 с.

79. Сетевые графики в планировании: Учеб. пособие / Разумов И.М., Белова Л.Д., Ипатов М.И., Проскуряков А В.- 3-е изд., перераб. и доп. М.: Высш. школа, 1981. - 168 с.

80. Сетевые модели для анализа учебного процесса с использованием АОС. М.: НИИВШ, 1988. - 44 с.

81. Сетевое планирование в строительстве. / Сост. Балберова Л.А., Зава-лишина К.С.: Библиографический указатель лит-ры за 1969-1972. М., Госстрой СССР. ЦНИПИАСС, 1972. - 80 с.

82. Сетевое планирование и управление: Сб. статей / Под ред. Голен-ко Д.И. и Кириллова В.В. М.: Экономика, 1967. - 397с.

83. Сетевое планирование и управление в строительстве / Сашенков М.С., Иванов В.Г., Стальной И.Ф. и др. М.: Стройиздат, 1971. - 184 с.

84. Свами Т., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

85. Соломахин И.С. Сетевое планирование и управление на метал, заводах. М.: Металлург, 1968.

86. Справочник проектировщика АСУП. / Под ред. Федоренко Н. П., Карибского В. В.-М.: Экономика, 1974.

87. Справочник по математике для экономистов / Под ред. В.И. Ермакова- 2-е изд., перераб. и доп. М.: Высш. шк., 1997. - 384 с.

88. Татт, Уильям. Теория графов. М.: Мир, 1988. - 424 с.

89. Таха X. Введение в исследование операций, 6-е изд-е: Пер. с англ. -М.: Изд. дом Вильяме, 2001.

90. Терехов JI.JI., Куценко В.А., Сиднев С.П. Экономико-математические методы и модели в планировании и управлении. — Киев: Вища школа, 1984. — 232 с.

91. Толковый словарь по теории графов в информатике и программировании / В.А. Евстигнеев, В.Н. Касьянов. Новосибирск: Наука. Сиб. Предприятие РАН, 1999.-291 с.

92. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

93. Федосеев В.В., Гармаш А.Н. Экономико-математические методы и прикладные модели. М.: ЮНИТИ, 2000.

94. Филимонов А.Б. Сетевое планирование и управление при разработке сложных электротехнических комплексов. М.: Мир, 1968.

95. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: пер. с англ. -М.: Мир, 1984.

96. Форд Л.Р., Фалкерсон. Д.Р. Потоки в сетях. М.: Мир, 1966. - 276 с.

97. Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978.

98. Харари Ф. Теория графов. -М.: Мир, 1973.

99. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

100. Холод Н.И., Кузнецов А.В. Экономико-математические методы и модели. Мн.: Выш. шк., 1999.

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

102. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Мир, 1985.

103. Эддоус М, Стэнсфилд Р. Методы принятия решений / Пер. с англ. Под ред. член-корр. РАН И.И. Елисеевой. М.: Аудит, ЮНИТИ, 1997. - 590 с.

104. Экономико-математические методы в планировании / Ларионов А. И., Новосёлов А.Л., Юрченко Т.И. М.: Высш. шк., 1991. -239 с.

105. Экономико-математическое моделирование: Учебник для студентов вузов / Под общ. ред. И. Н. Дрогобыцкого. М.: Изд-во Экзамен, 2004. - 800с.

106. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов / Под ред. В.А. Садовничего 3-е изд., стер. - М.: Высш. шк., 2002. -384 с.

107. Ahuja R.K., Magnanti Т.К., Orlin J.B. Networks Flows: theory, algorithms and applications // Prentice- Hall. Englewood Cliffs, N.J. - 1993.

108. Akkan C., Drexl A., Kimms A. Network decomposition-based benchmark results for the discrete time-cost trade-off problem // European Journal of Operational Research. 2005. - Vol. 165. - P. 339-358.

109. Bianco L., Speranza M.G. Resource management in project scheduling // Proceedings of the Second International Workshop on Project Management and Scheduling. Compiegne, 1990.

110. Billstein N., Radermacher F.J. Time-cost optimization // Methods of Operations Research. 1977. - Vol. 27. - P. 274-294.

111. Crowston W. Network reduction and solution // Operations Research Quarterly. 1970. - Vol. 21. - P. 435-450.

112. Crowston W., Thompson G.L. Decision CPM: a method for simultaneous planning, scheduling and control of projects // Operations Research. 1967. -Vol. 15.-P. 407-426.

113. De P., Dunne E.J., Ghosh J.B., Wells C.E. The discrete time/cost trade-off problem revisited // European Journal of Operational Research. 1995. - Vol. 81. -P. 225-238.

114. De P., Dunne E.J., Ghosh J.B., Wells C.E. Complexity of the discrete time/cost trade-off problem for project networks // Operations Research. 1997. -Vol. 45.-P. 302-306.

115. Demeulemeester E., De Reyck В., Foubert В., Herroelen W., Van-houcke M. New computational results for the discrete time/cost trade-off problem in project networks // Journal of the Operational Research Society. 1998. - Vol. 49. -P. 1153-1163.

116. Demeulemeester E., Elmaghraby S.E., Herroelen W. Optimal procedures for the discrete time/cost trade-off problem in project networks // European Journal of Operational Research. 1996. - Vol. 88. - P. 50-68.

117. De Reyck В., Herroelen W. On the use of the complexity index as a measure of complexity in activity networks // European Journal of Operational Research. 1996. - Vol. 91. - P. 347-366.

118. De Reyck В., Herroelen W. An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations // Computers and Operations Research. 1998. - Vol. 25. -P. 1-17.

119. Elmaghraby S.E., Herroelen W. On the measurement of complexity in activity networks // European Journal of Operational Research. 1980. - Vol. 5, -P. 223-234.

120. Elmaghraby S.E., Kamburowski J. The analysis of activity networks under generalized precedence relations // Management Science. 1992. - Vol. 38, 1245-1263.

121. Elmaghraby S.E., Salem A. Optimal project compression under convex cost functions I: Quadratic cost with continuous derivative // OR Technical Report 158, North Carolina State University at Raleigh. 1980.

122. Elmaghraby S.E., Salem A. Optimal project compression under convex cost functions II // OR Technical Report 157, North Carolina State University at Raleigh. 1980.

123. Elmaghraby S.E., Salem A. Optimal linear approximation in project compression // OR Technical Report 171, North Carolina State University at Raleigh. -1981.

124. Falk J.E., Horowitz J.L. Critical path problems with concave cost-time curves // Management Science. 1972. - Vol. 19. - P. 446-455.

125. Ford L.R., Fulkerson D.R. Flows in networks. Princeton University Press: New Jersey, 1962.

126. Fulkerson D.R. A network flow computation for project cost curves // Management Science. 1961. - Vol. 7. - P. 167-178.

127. Goyal S.K. A note on the paper: A simple CPM time/cost trade-off algorithm // Management Science. 1975. - Vol. 21. - P. 718-722.

128. Hendricksonand B.N., Janson A. Common Network Flow Formulation for Several Civil Engineering Problems // Civil Engineering Systems. 1984. - Vol. 1. -№.4.-P. 195-203.

129. Herroelen W., De Reyck B. Phase transitions in project scheduling // Journal of Operational Research Society. 1999. - Vol. 50. - P. 148-156.

130. Herroelen W., Demeulemeester E., De Reyck B. A classification scheme for project scheduling problems // In: Weglarz J. (Ed.). Handbook on Recent Advances in Project Scheduling, Kluwer Academic Publishers. 1999. - Chapter 1. -P. 1-26.

131. Hindelang T.J., Muth J.F. A dynamic programming algorithm for decision CPM networks Operations Research. 1979. - Vol. 27. - P. 225-241.

132. Kamburowski J., Michael D.J., Stallmann M.F. Optimal construction of project activity networks // Proceedings of the 1992 Annual Meeting of the Decision Sciences Institute. San Francisco. - 1992. - P. 1424-1426.

133. Kamburowski J. Project crashing in CPM networks I I Proceedings of the 1993 Annual Meeting of Decision Science Institute. Washington, D.C., 1993. -P. 1099-1101.

134. Kamburowski J. On the Minimum Cost Project Schedule // Omega Int. J. Mgmt. Sci. 1995. - Vol. 23. - №. 4. - P. 463-465.

135. Kapur K.C. An algorithm for the project cost/duration analysis problem with quadratic and convex cost functions // HE Transactions. 1973. - Vol. 5. -P. 314-322.

136. Kelley J.E. Critical path planning and scheduling: Mathematical basis // Operations Research. 1961. - Vol. 9. - P. 296-320.

137. Kelley J.E., Walker M.R. Critical path planning and scheduling: an introduction // Mauchly Associates. Ambler, PA. - 1959.

138. Kelley J.E., Walker M.R. Scheduling Activities to Satisfy Resource Constraints // In: Industrial Scheduling, by J. Muth, G. Thompson, Prentice-Hall, Inc. -Englewood Cliffs, N. J. 1963.

139. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems // Management Science. 1995.-Vol. 41.-P. 1693-1703.

140. Lamberson L.R., Hocking R.R. Optimum time compression in project scheduling // Management Science. 1970. - Vol. 16. - P. 597-606.

141. Moder J.J., Phillips C.R., Davis E.W. Project Management with CPM, PERT and precedence diagramming // Van Nostrand Reinhold Company, Third Edition.- 1983.

142. Patterson J.H., Harvey R.T. An implicit enumeration algorithm for the time/cost trade-off problem in project network analysis // Foundations of Control Engineering. 1979. - Vol. 6. - P. 107-117.

143. Phillips Jr.S, Dessouki M.I. Solving the project lime/cost tradeoff problem using the minimal cut concept // Mgmt. Sci. 1977. - Vol. 24. - P. 393-400.

144. Robinson D.R. A dynamic programming solution to cost/time trade-off for CPM // Management Science. 1975. - Vol. 22. - P. 158-166.

145. Siemens N. A simple CPM time/cost trade-off algorithm 11 Management Science. 1971. - Vol. 17. - P. 354-363.

146. Siemens N., Gooding C. Reducing project duration at minimum cost: a time/cost tradeoff algorithm // OMEGA. 1975. - Vol. 3. - P. 569-581.

147. Skutella M. Approximation algorithms for the discrete time-cost tradeoff problem // Mathematics of Operations Research. 1998. - Vol. 23. - P. 909-929.

148. Tufekci S. A flow preserving algorithm for time-cost tradeoff problem // HE Trans.- 1982.-Vol. 14.-P. 109-113.

149. Vanhoucke M., Demeulemeester E., Herroelen W. Discrete time/cost trade-offs in project scheduling with time-switch constraints // Journal of the Operational Research Society. 2002. - Vol. 53, - P. 1-11.

150. Vanhoucke M., Demeulemeester E., Herroelen W. A random network generator for activity-on-the-node networks // Journal of Scheduling. 2002.

151. Vercellis C. Multi-project scheduling with time-resource-cost trade-offs: a tactical model // Proceedings of the Second International Workshop on Project Management and Scheduling. Compiegne, 1990.

152. Wiest J.D., Levy F.K. A management guide to PERT/CPM: with GERT/PDM/DCPM and other networks // Prentice-Hall, Inc. 1977.

153. Wu Y., Li C. Minimal cost networks: the cut set parallel difference method // Omega. 1994. - Vol.22. - P. 401-407.

154. Yang H.H., Chen Y.L. Finding the critical path in an activity network with time-switch constraints // European Journal of Operational Research. 2000. -Vol. 120.-P. 603-613.