Модели и эвристические алгоритмы определения оптимальной очередности выполнения строительных проектов

Размещено на http://www.allbest.ru/

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

Специальность 05.13.10 - Управление в социальных и экономических системах

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических наук

МОДЕЛИ И ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ОЧЕРЕДНОСТИ ВЫПОЛНЕНИЯ СТРОИТЕЛЬНЫХ ПРОЕКТОВ

НОВИКОВ А.А.

Воронеж 2007

Работа выполнена в Воронежском высшем военном авиационном инженерном училище (военном институте)

Научный руководитель кандидат технических наук, доцент Коновальчук Евгений Викторович

Официальные оппоненты доктор технических наук, профессор Погодаев Анатолий Кирьянович кандидат технических наук, доцент Белоусов Вадим Евгеньевич

Ведущая организация Ростовский государственный строительный университет

Защита состоится «_1_» ноября 2007 г. в 14-00 часов в аудитории 3220 на заседании диссертационного совета Д 212. 033.03 при Воронежском государственном архитектурно - строительном университете по адресу: 394006, г. Воронеж, ул. ХХ - летия Октября, 84.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного архитектурно - строительного университета.

Автореферат разослан «_30_» сентября 2007 г.

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

1. Общая характеристика работы

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

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

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

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

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

Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:

- федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанные модели используются в практике работы ООО «Агрокс - 2», корпорации ЗАО «Воронеж - Дом».

Модели и алгоритмы включены в состав учебных курсов, читаемых в Воронежском высшем военном авиационном инженерном училище (военном институте).

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

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

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

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

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

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

Апробация работы.

Основные результаты исследований и научных разработок докладывались и обсуждались на следующих конференциях: Четвертая международная конф. «Системы управления эволюцией организации» (Китайская Народная Республика, г. Санья, 2007 г.), научно-практическая конф. «Образование, наука, производство и управление» (г. Старый Оскол, 2006г.), 60 - 62 научно-технические конференции по проблемам архитектуры и строительных наук (Воронеж, ВГАСУ, 2005 - 2007 гг.).

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

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [1], [2], [3] автору принадлежит модель определения оптимальной очередности выполнения строительных проектов с учетом возможностей субподрядных организаций; в работах [5], [6], [9] автору принадлежит модель определения оптимальной очередности выполнения строительных проектов с учетом времени на перемещение строительных бригад на основе задачи коммивояжера; в работах [4], [3] автору принадлежат модель определения оптимальной очередности выполнения строительных проектов при наличии возможных технологических связей между объектами на основе обобщения задачи о редакторе; в работах [3], [10] автору принадлежит модель определения оптимальной очередности выполнения независимых строительных проектов при фиксированном бюджете; в работах [6], [10] автору принадлежит модель; в работах [7], [8], [10] автору принадлежит модель определения оптимальной очередности выполнения независимых строительных проектов при фиксированном сроке реализации производственной программы предприятия с учетом возможность взятия.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Она содержит 153 страницы основного текста, 14 рисунков, 29 таблиц и 3 приложения. Библиография включает 171 наименования.

2. Содержание работы

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

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

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

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

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

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

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

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

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

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

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

1. Сформировать матрицу парных сравнений, в которую заносятся сведения о продолжительности выполнения работ в том случае, если будут строиться только два объекта. Причем размерность матрицы равна числу строящихся объектов. Произвольный элемент матрицы бij характеризует продолжительность строительства пары объектов i и j, элемент матрицы бji - продолжительность строительства пары объектов j и i.

2. На основе матрицы парных сравнений сформировать сигнальную матрицу, состоящую из нулей и единиц. Произвольный элемент матрицы вij равен единице если продолжительность строительства пары объектов i и j будет меньше чем продолжительность строительства той же пары объектов, но в другой последовательности, то есть j и i, в противном случае элемент матрицы равняется нулю. Если продолжительности будут равны, то оба элемента сигнальной матрицы принимаются равными единице. Главная диагональ сигнальной матрицы не заполняется и в дальнейших расчетах не участвует.

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

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

Рассмотрим применение алгоритма на примере.

Пример 1. На рис. 1 представлены исходные данные о работах подлежащих выполнению на пяти объектах.

Рис. 1. Исходные данные к примеру 1

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

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

Таблица 1. Матричная запись исходных данных к примеру 1

0 4 4	4 12 16	22 3 25
4 5 9	9 13 22	25 2 27
9 8 17	17 17 34	34 4 38
17 2 19	19 16 35	38 3 41
19 3 22	23 16 39	41 4 45

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

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

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



Рис. 2. Фрагмент расчетов для формирования матрицы парных сравнений

На основе парных сравнений формируем матрицу парных сравнений, приведенную в табл. 2.

На основе матрицы парных сравнений формируется сигнальная матрица, приведенная в табл. 3.

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

Таблица 2. Матрица парных сравнений к примеру 1

Таблица 3. Сигнальная матрица к примеру 1

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

IV>V>III>I>II; V>IV>III>I>II; IV>V>III>II>I; V>IV>III>II>I. первого на третий или со второго на третий объект приводит к увеличению общей продолжительности строительства (твует. мо получ

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

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

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

Таблица 4. Расчет параметров потока для первой последовательности

0 2 2	2 16 18	22 3 25
2 3 5	5 16 21	25 4 29
5 8 13	13 17 30	30 4 34
13 4 17	17 12 29	34 3 37
17 5 22	22 13 35	37 2 39

работы авторов (второго вида работы, выполняемого субподрядчиками), фi - продолжительность второго редактирования (третьего вида работы). Для этой цели необходимо для каждого объекта определить параметр , и затем все объекты разбить на две группы Ф1 и Ф2. В первую группу Ф1 должны войти объекты для которых параметр qi?0, а во вторую группу Ф2 объекты для которых qi<0. Таким образом, и . Объекты образующие первую группу должны выполняться первыми в порядке возрастания величины pi=ti+li , затем выполняются объекты образующие вторую группу в порядке убывания величины si=фi+li. Это дает две возможных последовательности выполнения работ на объектах:

IV>V>III>I>II; IV>V>III>II>I.

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

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

Утверждение 1. Нижней оценкой задачи о редакторе будет значение продолжительности, определяемое выражением

.

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

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

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

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

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

Преобразуя это выражение, приходим к соотношению вида (2).

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

,

где , - начало и окончание второго вида работы на k-ом объекте.

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

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

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

Рис. 3. Многоступенчатое редактирование

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

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

Рассмотрим применение алгоритма парных сравнений на примере

Пример 2. Структура выполняемых работ и продолжительность выполнения каждой работы приведены на рис. 3.

Составим матрицу исходных данных, которая приведена в табл. 5.

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

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

Таблица 5. Матричная запись исходных данных к примеру 2

0 4 4	4 13 17	17 2 19	19 21 40	40 6 46	I
4 5 9	9 18 27	27 3 30	30 23 53	53 5 58	II
9 3 12	12 17 29	30 4 34	34 24 58	58 4 62	III
12 2 14	14 16 30	34 5 39	39 25 64	64 2 66	IV
14 3 17	17 15 32	39 1 40	40 26 66	66 1 67	V

Таблица 6. Матрица парных сравнений к примеру 2

	I	II	III	IV	V
I		58	56	54	50
II	60		58	56	55
III	58	57		54	53
IV	56	56	54		51
V	52	57	55	53

Таблица 7. Сигнальная матрица к примеру 2

	I	II	III	IV	V	? по строке
I		1	1	1	1	4
II	0		0	1	1	2
III	0	1		1	1	3
IV	0	1	1		1	3
V	0	0	0	0		0

Таким образом, выделяется две последовательности выполнения работ а объектах обеспечивающих сокращение продолжительности

I>III>IV>II>V; I>IV>III>II>V.

При этом общая продолжительность составит 65 дней.

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

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

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

Введем переменную xij, которая принимает значение равное 1 если с объекта i происходит перемещение на объект j и равно 0 в противном случае. «Цена» перехода с объекта i на объект j равна Cij причем Cii=?. Тогда задача запишется в следующем виде

Задача (3) относится к достаточно известной задаче коммивояжера.

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

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

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

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

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

Рассмотрим применение алгоритма парных сравнений на конкретном примере.

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

Таблица 8. Матрица расстояний задачи коммивояжера

i j	1	2	3	4	5
1		25	35	10	1
2	5		13	2	4
3	25	35		6	15
4	26	11	36		6
5	13	12	11	10

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

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

Таблица 9. Матрица расстояний задачи коммивояжера

i j	1	2	3	4	5	? по строке
1		0	0	1	1	2
2	1		1	1	1	4
3	1	0		1	0	2
4	0	0	0		1	1
5	0	0	1	0		1

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

II>I>IV>V>III, T=5+10+6+11=32, II>I>V>III>IV, T=5+1+11+6=23,

II>III>I>IV>V, T=13+25+10+6=54, II>IV>V>III>I, =2+6+11+25=44.

II>V>III>I>IV, T=4+11+25+10=50.

Других полных последовательностей не имеется. Следовательно, оптимальной последовательностью выполнения проектов является

II>I>V>III>IV, T=5+1+11+6=23.

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

Для решения такой задачи фиксируем номер объекта, с которого необходимо начать работу и на который необходимо вернуться. Таким образом, необходимо решить n задач коммивояжера размерностью n-1.

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

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

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

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



где - функция - индикатор.

Здесь допускается, что f(t) может принимать отрицательные значения. Определим график привлечения кредита в зависимости от состояния финансового баланса:

g(t)=| min [f(t),0] | .

Тогда основная цель минимизировать величину .

Формально эта задача записывается так:

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

В этом случае функция g(t) имеет кусочный характер, и задача (6) сводится к более простой:

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

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

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

В рамках данных предположений возникает вопрос: существует ли такое расписание времен начала всех операций (не зависящее от величины Ro и от параметров операций), при котором суммарные процентные выплаты по кредиту минимальны, и время реализации проекта минимально. Ответ на этот вопрос дает

Лемма 1. Пусть - время реализации производственной программы. Очевидно, минимальное время . Тогда существует набор , такой что ti=Tmin-фi, при котором проект выполняется за время , и выплаты по процентам минимальны.

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

Перечислим основные результаты работы:

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

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

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

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

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

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Курочка П.Н., Новиков А.А., Толстикова О.Н. Алгоритм получения робастных расписаний частного порядка. Вестник ВГТУ, Том 3, № 7, 2007 г. - с. 18 - 23.

2. Ерохин А.В., Новиков А.А. Модель принятия решений на основе нечетких отношений. Вестник ВГТУ, Том 3, № 7, 2007 г. - с. 37 - 43.

3. Курочка П.Н., Коновальчук Е.В., Новиков А.А. Модель определения оптимальной очередности выполнения строительных проектов на основе обобщения задачи о редакторе. //Системы управления и информационные технологии. 2007. № 3. - С. 58 -64.

Статьи и материалы конференций

4. Врублевская С.С., Новиков А.А. Определение оптимальной последовательности операций при выполнении проекта. Материалы научно-практической конф. Образование, наука, производство и управление 23-24 ноября 2006г. Том 4. - с. 414-420.

5. Баркалов С.А., Новиков А.А., Шульгин В.В. Модель определения оптимальных вариантов управления производственной системы. ИнВестРегион, №1 Воронеж 2007 / 1 (7) - с. 36 - 40.

6. Буркова И.В., Новиков А.А. Алгоритм дихотомического программирования в задачах выбора вариантов оптовых закупок. «Системы управления эволюцией организации» Четвертая международная конф. (12-19 апреля 2007г. г. Санья, Китайская Народная Республика) - с. 167 - 172.

7. Новиков А.А. Общий случай разработки календарного плана оптимального по стоимости. //В кн.: Модели и методы управления строительными проектами. /Баркалов С.А., Буркова И.В., Курочка П.Н. - М., ООО «Уланов - пресс». 2007. - с. 310 - 315.

8. Новиков А.А. Задачи определения оптимальной очередности выполнения работ. //В кн.: Модели и методы управления проектами в дорожном строительстве. / Баркалов С.А., Курочка П.Н., Половинкина А.И., Ерохин А.В. - М., ООО «Уланов - пресс». 2007. - с. 206 - 227.

9. Новиков А.А. Минимизация средств, привлекаемых для реализации проекта. //В кн. Модели и методы управления проектами при реформировании и реструктуризации предприятий. / Баркалов С.А., Бурков В.Н., Ерохин А.В., Курочка П.Н. - М., ООО «Уланов - пресс». 2007. - С. 398 - 404.

10. Новиков А.А. Определение последовательности реализуемых инвестиционных проектов. // В кн.: Оптимизационные модели и методы в управлении строительным производством. /Семенов П.И., Баркалов С.А., Курочка П.Н. - Воронеж, «Научная книга». 2007. - с. 296 - 317.

Размещено на Allbest.ru