Управление проектами: задача календарного планирования

Лекция УПРАВЛЕНИЕ ПРОЕКТАМИ: задача календарного планирования На практике часто встречаются задачи планирования разнообразных по своему содержанию работ, например, строительство промышленного предприятия, создание сети вычислительных устройств, разработка сложной научно-исследовательской темы и другие проекты, включающие множество работ, которые должны выполняться в определенной последовательности. При разработке планов реализации таких проектов возникают следующие вопросы:  в какие моменты начинать и заканчивать каждую из работ?  как распределить между ними ресурсы?  как изменятся параметры плана выполнения работ в случае непредвиденных обстоятельств? Возможно, что при небольшом количестве работ ответы можно получить из практических соображений, однако, в общем случае возникает необходимость в привлечении специальных методов. Одним из таких методов является метод сетевого планирования. Он базируется на представлении совокупности работ, выполняемых в определенной последовательности, в виде сети – взвешенного бесконтурного графа, а соответствующие алгоритмы обработки сети позволяют составить календарный план проекта и провести его анализ. Временные параметры сетевого графика Временные параметры сетевого графика позволяют составить календарный план реализации проекта и ответить на основной вопрос: сколько времени необходимо для реализации проекта. Введем основные определения. Пусть длина дуги соответствует продолжительности выполнения работы, тогда временем наступления события будем считать время окончания все работ, предшествующих данному событию, при этом предполагается, что работа над проектом начинается в момент времени, равный нулю. Каждому событию i можно поставить в соответствие следующие параметры: 2 te  i   раннее время наступления i -го события  время, раньше которого событие i наступить не может, иначе не будут завершены работы, которые ему предшествуют; tl  i   позднее время наступления i -го события  время, позже которого событие i наступить не должно, иначе увеличится время, необходимое для реализации проекта. Заметим, что te  i   tl i  , при этом величина R i   tl i   te i  называется резервом времени i -го события. Зафиксируем событие i . Очевидно, что для его наступления необходимо, чтобы все работы, которые ему предшествуют, были завершены. Тогда раннее время te  i  можно интерпретировать как длину максимального пути из исходного события в данное событие i . Длина максимального пути из исходного события в завершающее – это время, необходимое для реализации всего проекта, так как время завершения всего комплекса работ не может быть меньше, чем суммарная продолжительность всех работ вдоль самого длинного пути. Это время называется критическим и обозначается Tmax . Сетевой график может иметь несколько критических путей. Все они имеют одинаковую длину Tmax . Позднее время tl  i  наступления i -го события можно интерпретировать как разность между длиной критического пути и длиной критического пути из i -го события в завершающее событие сети. Работы и события, принадлежащие критическому пути, также называются критическими. Особенность критических работ заключается в том, что они не имеют резервов времени, поэтому невыполнение срока окончания любой из критических работ приводит к увеличению критического времени Tmax . В связи с этим именно критические работы требуют бесперебойного обеспечения ресурсами и контроля за выполнением. Все остальные работы располагают определенными резервами времени. Имеет место следующее утверждение: для того, чтобы событие i принадлежало критическому пути необходимо и достаточно, чтобы раннее и позднее времена наступления этого события совпадали, то есть te  i   tl i  . Для определения, является ли событие i критическим, можно использовать его резерв времени R  i  , который показывает, насколько можно задержать наступление этого события, не вызывая при этом увеличения 3 критического времени. Для критических событий данный резерв равен нулю, для некритических  положителен. Пусть i и j  события, соответствующие началу и окончанию некоторой работы, тогда будем обозначать ее  i, j  . В сетевом графике данной работе соответствует дуга с тем же обозначением i, j  и весом tij , равным продолжительности работы. К временным параметрам сетевого графика также относятся резервы времени работ. Полный резерв времени работы  i, j  R full i, j   tl  j   te i   tij есть разность между критическим временем выполнения проекта Tmax и максимальной длиной пути, проходящего через эту работу, поэтому это максимальное время, которым можно располагать для увеличения продолжительности работы  i, j  без увеличения Tmax . Свободный резерв времени работы  i, j  R free i, j   te  j   te i   tij  это максимально допустимое время увеличения продолжительности работы i, j  , при котором все работы  j,k  , предшествующие событию j , начинаются в ранее время te  k  . Независимый резерв времени работы  i, j  Rindep i, j   max 0,te  j   tl i   tij  есть максимально допустимое количество времени для увеличения продолжительности работы  i, j  при условии, что все работы  k ,i  , входящие в i -е событие, заканчиваются в позднее время tl  i  , а все работы  j,m  , выходящие из события j , начинаются в раннее время te  j  . Отрицательное значение независимого резерва означает, что любая задержка в выполнении работы приведет к дополнительным ограничениям на выполнение других работ. Определим взаимосвязи между введенными резервами. Заметим, что R full i, j   R free i, j   tl  j   te i   tij  te  j   te i   tij   tl  j   te  j   R  j  . 4 Увеличение продолжительности работы  i, j  на часть ее свободного резерва R free  i, j  может уменьшить полный резерв R full  k ,i  у работ  k ,i  , предшествующих i -му событию, и не влияет на резервы работ, выходящих из j -го события. Пусть для работы  i, j  имеем te  j   tl i   tij  0 , тогда R full i, j   Rindep i, j   tl  j   te i   tij  te  j   tl i   tij    tl i   te i     tl  j   te  j    R i   R  j  . Если te  j   tl i   tij  0 , то Rindep i, j   0 и R full i, j   Rindep i, j   R full i, j  . Тогда, если работа  i, j  является критической, R full i, j   R free i, j   Rindep i, j   0 , для некритических работ R full i, j   R free i, j  , R full i, j   Rindep i, j  . Найдем R free i, j   Rindep i, j  . Если для работы  i, j  te  j   tl i   tij  0 , то R free i, j   Rindep i, j   te  j   te i   tij  te  j   tl i   tij   tl i   te i   R i  . Если для работы  i, j  te  j   tl i   tij  0 , то Rindep i, j   0 и R free i, j   Rindep i, j   R free i, j  . Увеличение продолжительности работы на величину ее независимого резерва не изменяет резервы других работ. Для каждой работы, выходящей из события, лежащего на критическом пути, независимый резерв времени совпадает со свободным. Таким образом, имеем следующие соотношения между резервами: R free  i, j   R  j  ,  R full  i, j     Rindep  i, j   R  i   R  j  . Имеет место следующее утверждение: для того, чтобы работа  i, j  была критической, необходимо и достаточно, чтобы R full i, j   0 . 5 У критических работ полный резерв равен 0, поэтому полный резерв является как бы мерой «критичности» работы: чем меньше полный резерв, тем ближе к критическому пути максимальный по длине путь, проходящий через данную работу. Некритические работы обладают положительным полным резервом. Увеличение продолжительности некритической работы за счет использование всего полного резерва обязательно влечет появление нового критического пути, в состав которого войдет эта работа. Анализ сетевого графика предполагает определение критических работ и резервов времени некритических работ, разумная задержка которых позволяет улучшить ситуацию с критическими работами. В табл. 1 приведены рекомендации для использования резервов времени некритических работ. Таблица 1. Рекомендации по использованию резервов времени работ Резерв Рекомендация Какое максимальное количество При увеличении продолжительности работы времени можно выделить для  i, j  на величину полного резерва ее начальное выполнения работы  i, j  без событие наступит в самый ранний момент, а увеличения времени выполнения конечное событие  в самый поздний. всего проекта? R full  i, j  Какое максимальное количество времени можно выделить для выполнения работы  i, j  без введения дополнительных временных ограничений на последующие работы? R free  i, j  Резерв используется для предотвращения случайностей,  если планировать выполнение работ по ранним срокам их начала и окончания, то всегда будет возможность при необходимости перейти на поздние сроки начала и окончания работ. Какое максимальное количество времени можно выделить для выполнения работы i, j  без введения дополнительных временных ограничений на все работы проекта? Rindep  i, j  Резерв используется тогда, когда окончание хотя бы одной из предыдущих работ произошло в поздний срок, а последующие работы хотят выполнить в ранние сроки. Топологическая сортировка Под правильной (или монотонной) нумерацией вершин бесконтурного графа подразумевается такая нумерация, согласно которой для каждой дуги i, j  номер начала i меньше номера конца j . В сетевом графике дуге соответствует работа, поэтому вполне естественно, что номер события, которое соответствует началу работу, будет меньше номера события, которое 6 соответствует ее окончанию. В сетевом графике правильная нумерация событий позволяет ввести бинарные отношения предшествования на множестве работ. Известно, что топологическая сортировка всегда реализуема в бесконтурном графе. Поскольку сетевой график является бесконтурным графом, то правильная нумерация в нем всегда существует. Под рангом вершины i понимается длина максимального пути из исходной вершины в данную вершину i . Заметим, что топологическая сортировка позволяет единственным образом распределить все вершины бесконтурного графа по рангам. Алгоритм нумерации вершин, основанный на рангах 1. Положить r  0 . 2. Определить в графе вершины без входящих дуг, присвоить им ранг r , а затем удалить данные вершины из графа вместе с инцидентными дугами. 3. Если граф не пуст, то положить r  r  1 и перейти к шагу 2, иначе получено распределение вершин по рангам. 4. Пронумеровать вершины по возрастанию рангов. Если несколько вершин имеют один и тот же ранг, то они нумеруются в произвольном порядке. Определение временных параметров сетевого графика Рассмотрим алгоритм определения временных параметров сетевого графика и пример расчетов. Шаг 1. Топологическая сортировка сети. Получить правильную нумерацию вершин сетевого графика, при этом исходное событие сети получает номер 0, а завершающее  номер n . Шаг 2. Определение ранних времен наступления событий. Положить te  0   0 . Двигаясь по пронумерованной сети в порядке возрастания вершин, для каждой вершины j определить te  j   max te i   tij , 1 iГ  j где Г 1  j   i : i  j  множество вершин, из которых дуги ведут в вершину j. Шаг 3. Определение критического пути. Положить Tmax  te  n  , где n  завершающее событие сети. Для определения критического пути выполнить следующие действия: из всех дуг, 7 входящих в завершающее событие n , выделить те дуги i, j  , которые удовлетворяют условию te  j   te i   tij . Затем рассматриваются те вершины, из которых выходят выделенные дуги, и снова из входящих в них дуг выделяются те, которые удовлетворяют тому же условию. Процесс продолжается до тех пор, пока не будет достигнуто исходное событие сети. Путь из исходного события в завершающее событие, составленный из выделенных дуг, является критическим. Шаг 4. Определение поздних времен наступления событий. Положить tl  n   te  n   Tmax . Двигаясь по сети от завершающего события в порядке убывания номеров вершин, определить для каждого i -го события tl  i   min tl  j   tij  , jГ  i  где Г i    j : i  j  множество вершин, в которые ведут дуги из i . Шаг 5. Определение резервов времени. Для каждой работы i, j  определить резервы времени R full i, j  ,R free i, j  ,Rindep i, j  . Замечание 1. Алгоритм расчета ранних времен требует одной операции сложения для каждой дуги и одной операции сравнения на максимум для каждого события, кроме исходного. алгоритм расчета поздних времен требует одной операции вычитания для каждой дуги и одной операции сравнения на минимум для каждого события, кроме завершающего. Замечание 2. Определение te  j  можно осуществлять и в том случае, если сеть не пронумерована, при этом производится столько итераций, сколько необходимо для того, чтобы очередная итерация не изменила предыдущего множества te  j  . Можно показать, что число итераций при этом не превысит максимального ранга вершин сети. Замечание 3. При выполнении проекта критический путь может меняться, это связано с возможным изменением длительности некоторых работ, которые могут оказаться критическими. Пример. Рассмотрим сетевой график, представленный на рис. 1, и рассчитаем его временные параметры. 8 По формулам найдем ранние времена наступления событий: te 1  0 , te  2   0  2  2 , te  3  max 2  3,0  4  5 , te  4   max 0  6,5  5  10 , te 5  max 2  7,10  5  15 , te  6  max 2  4,5  4,15  2  17 , te  7   max 15  6,17  5  22 . Рисунок 1  Сетевой график Таким образом, Tmax  20 и поэтому для реализации проекта, сетевой график которого представлен на рисунке, необходимо 20 единиц времени. Найдем поздние времена событий: tl  7   22 , tl  6  22  5  17 , tl 5  min 17  2,22  6  15 , tl  4   15  5  10 , tl  3  min 10  5,17  4  5 , tl  2   min 5  3,15  7,17  4  2 , tl 1  min 2  2,5  4,10  6  0 . Пример: проектирование торгово-развлекательного центра Торгово-развлекательные центры (ТРЦ) (рис. 2) дают возможность приобрести товары различных категорий в одном месте, чередуя шопинг с развлечениями и посещениями кафе. ТРЦ, как правило, имеют несколько этажей и включают не только торговые площади, но и центры досуга – кинозалы, боулинги, квест-комнаты, островки для развлечения детей на время шопинга родителей, фуд-зону. Основная задача владельца ТРЦ  сдать объект в эксплуатацию и привлечь арендаторов, после чего центр начнет приносить доход без существенных затрат. 9 Рисунок 2 – Торгово-развлекательный центр Для строительства торгово-развлекательного центра необходимо особенно тщательно провести расчеты, составить проект и сметную документацию, поскольку стартовые вложения очень велики. В табл. 2 представлены этапы работы по строительству и вводу в эксплуатацию ТРЦ «Рябина». Таблица 2  Перечень этапов, работ и их продолжительностей Работа Содержание A B C Анализ рынка недвижимости города Выбор земельного участка Разработка концепции торгового центра Заключение инвестиционного договора Получение кредита Внесение в госреестр, постановка на учет в налоговых и административных органах Предброкеридж и внесение изменений в концепцию Разработка рабочей проектной документации Заказ и покупка оборудования Подготовка стройплощадки и закладка фундамента Монтаж вертикальных стен, перекрытий и крыши D E F G H I J K Продолжительность (нед.) 2 6 4 Предшествующие работы A B 4 C 8 4 D E 5 C 4 F 6 6 G H 8 J 10 L M N O P Q R S T Монтаж наружных сетей Монтаж систем отопления, вентиляции и кондиционирования Электромонтажные работы Отделочные работы и дизайн интерьера Установка оборудования Наем и обучение персонала Брокеридж торгового центра Проведение маркетинговой компании Подготовка к церемонии открытия 7 8 J L 4 9 L M, N 3 8 2 2 O O P O, P 1 Q, R На рис. 3 представлен сетевой график проекта. Соответствие между работами из табл. 2 и дугами сетевого графика представлено в табл. 3. Таблица 3  Соответствие между дугами и работами в сетевом графике A (1,2) E (6,7) I (5,14) M (11,12) Q (14,16) B (2,3) F (7,8) J (9,10) N (11,13) R (15,17) C (3,4) G (4,5) K (10,12) O (12,14) S (17,18) D (4,6) H (8,9) L (10,11) P (14,15) T (16,18) Рис. 3. Сетевой график проекта Результаты расчетов представлены на рис. 4. 11 Рисунок 4  Результаты расчетов