ВГАСУ
Методика определения последовательности реализации технологически связанных работ проекта, дающей наибольший доход
УДК 65.001.13
А.Я. Аснина, С.А. Баркалов, О.С. Нильга Nilga.OS_vrn@mail.ru
Воронеж, Россия
Рассмотрим проект из n работ. Под работой в рамках данной статьи понимается мероприятие как совокупность действий, нацеленных на выполнение единой задачи, по достижению которой можно получить определенный эффект (здесь финансовый). Время выполнения каждой работы выражено в месяцах. Будем считать, что каждая следующая работа начинается в момент завершения предыду-щей. - время выполнения всех мероприятий проекта. Для осуществления i-й работы необходимы инвестиции в размере . Предполагается, что все они осуществляются в момент запуска проекта. После выполнения каждой i-ой работы прогнозируется ежемесячный доход в размере в течение времени, оставшегося до окончания проекта. - момент получения первого дохода от последнего мероприятия. Работы проекта связаны технологической зависимостью, представленной в виде ориентированного дерева, где работы пронумерованы по правилу, приведенному ниже.
Требуется определить порядок запуска работ проекта с учетом технологической зависимости, дающий наибольший доход.
Условие определения оптимальной последовательности выполнения работ проекта
В [1] показано, что для получения порядка выполнения работ, который дает наибольший доход необходимо для каждой из них найти величину , и упорядочить работы по невозрастанию этих величин, то есть если
, то , (1)
а если , то раньше следует выполнять мероприятия с меньшей продолжительностью (t), так как в этом случае раньше начнется получение дохода [2].
Правило нумерации вершин-работ дерева
Присвоим вершине корню номер ноль. Далее нумеруются вершины первого уровня. Им присваиваются номера с первого по -й с учетом условия (1). Здесь количество вершин первого уровня.
Пусть теперь занумерованы все вершины k-го уровня, и они имеют номера с -го до -го, где - число вершин i-го уровня. Тогда вершинам (k+1)-го уровня присваиваются номера с -го до -го по следующему правилу.
Вначале нумеруются вершины имеющие корнем «первую» вершину предыдущего уровня, затем вершины, корнем которых является «вторая» вершина предыдущего уровня, и так далее. При этом вершины, имеющие один корень, предварительно упорядочиваются по условию (1), и в соответствии с этим порядком им присваиваются номера.
Условие (1) обеспечивает максимальный прогнозируемый доход для независимых работ, но так как между работами проекта имеется технологическая зависимость, то возникает ситуация, когда существуют работы А, В и С, где А строго предшествует В, но или , а , а С не связана ни с А, ни с В. Тогда возможны следующие варианты: доход последовательность технологический
1. если или , а , тогда работы надо выполнять в последовательности (А, В, С);
2. если или , а , тогда последовательность выполнения работ будет следующей (С, А, В);
3. Пусть теперь соотношение между работами имеет следующий вид . В этом случае место работы С в последовательности не очевидно. Здесь возможны две ситуации: (С, А, В) и (А, В, С). Ситуация (А, С, В) очевидно хуже, так как .
В общем случае, если k-я и (k+1)-я работы с учетом технологической зависимость должны стоять в порядке: k, (k+1). А (k+2)-я работа не связана ни с k-й, ни с (k+1)-й, то k-ю и (k+1)-ю работы можно считать одной работой для которой , , и тогда (k+2)-ю работу можно поставить либо перед , либо после с учетом условия (1). Подобные условия можно вывести и для тех случаев, когда необходимо сравнить доходы от последовательностей в которых «неразрывными» (то есть выполняющимися строго друг за другом) являются три и более работ (). Соотношение между доходами от последовательностей и , после преобразований, можно представить как , откуда следует, что работы с 1-й по k-ю можно считать единой работой с , , и тогда (k+1)-ю работу можно ставить с учетом (1) либо перед , либо после .
Перейдем к рассмотрению исходной задачи. Из выше изложенного следует, что для построения оптимальной последовательности работ, связанных технологической зависимостью необходимо те работы, для которых эта зависимость существенна, объединить в группы или списки, в каждом из которых порядок работ учитывает технологическую зависимость и (1), а затем эти группы отсортировать по условию (1).
Представим сказанное выше в виде алгоритма.
Алгоритм 1
Пусть имеем список из n работ, которые записаны в нем по возрастанию их номеров, присвоенных работам по правилу описанному выше. Необходимо определить такой порядок выполнения работ , который дает наибольший доход. Работы будем рассматривать в том порядке, в котором они записаны в и последовательно переносить их в .
Шаг 0. Первое место в списке займет начальная работа, а затем в порядке нумерации в список помещаются все работы, для которых корнем является нулевая работа. Все работы, помещенные в исключаются из .
Шаг 1. Пусть работ из списка перенесено в и упорядочено в соответствии с технологической зависимостью, причем некоторые работы стоят отдельно, а некоторые помещены в группы для которых , (для удобства, в дальнейшем, отдельно стоящие работы списка также будем называть группой) и для всех групп, кроме нулевой работы, выполнено условие
, если , (2)
Шаг 2. Если , то выбирается работа и исключается из . Назовем эту работу группой . Иначе Шаг 7.
Шаг 3. В отыскиваем группу работ , содержащую работу с номером l, которая является работой-корнем для . Если , то переход к Шагу 6. Иначе Шаг 4.
Шаг 4. Если или , а , то ставится после групп в соответствии с условием (2), , переход к шагу 2. Иначе.
Шаг 5. Если или , а , то к группе добавляем . Назовем образованную группу и вычислим ее параметры: , , а . Предшественником является предшественник . Переход к Шагу 3.
Шаг 6. Группа занимает место в списке в соответствии с условием (2). . Переход к Шагу 2.
Шаг 7. Конец. По завершению алгоритма весь список будет состоять из групп , которые могут содержать как один элемент, так и несколько.
Список литературы
1. Акулова И. И., Чернышов Е. М., Аснина А. Я., Гельбанд И. Е. Оптимизация системы организационно-технических мероприятий в антикризисном управлении предприятием строительной индустрии // Известия высших учебных заведений “Строительство”. Научно-теоретический журнал № 10. 2004. С. 44-48.
2. Нильга О.С. Оптимизация последовательности выполнения мероприятий проекта // Материалы Международного конгресса Наука и инновации в строительстве SIB 2008г. Том 5. «Проблемы развития инженерно-строительного образования». - Воронеж. 2008.