Информационные системы и технологии в экономике

 

1. Сетевое планирование и управление проектами

 

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

В 1956 году специалисту в области  вычислительной техники из фирмы  «Дюпон» М. Уолкеру, совместно с Д. Келли, работавшим в группе планирования капитального строительства фирмы «Ремингтон Рэд», удалось разработать простой и эффективный метод планирования работ по модернизации заводов фирмы «Дюпон». Метод был основан на построении так называемых сетевых графиков и получил название «метод критического пути», сокращенно МКП (англоязычный вариант — Critical Path Method — СРМ).

Практически в то же время  в военно-морских силах США  был создан метод анализа и  оценки программ (как ни странно, русская  аббревиатура для его обозначения так и не появилась, и продолжает использоваться англоязычный вариант — PERT, ( Programme Evaluation and Review Technique). Метод был разработан в процессе проектирования корпорацией «Локхид» ракетной системы «Поларис», предназначенной для оснащения подводных лодок ВМС США. В работах по созданию ракетной системы участвовало около 4 тысяч основных подрядчиков, а технологическая цепочка насчитывала около 60 тысяч операций. Благодаря внедрению метода PERT проект удалось завершить на два года раньше намеченного срока.

Основное различие между  методами СРМ и PERT заключалось в том, что в первом из них длительности входящих в проект работ полагались детерминированными, а во втором рассчитывалась вероятностная оценка длительности работ. Впоследствии оба метода были объединены под общим названием PERT-CPM (наиболее распространенный русскоязычный вариант — метод сетевого планирования и управления).

 

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

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

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

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

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

 

 

Рис. 1 Пример сетевого графика

 

Изображенные на рисунке  дуги соответствуют следующим видам работ:

А_{12 -}  разработка алгоритма первого модуля;

А₁₃ - разработка алгоритма второго модуля

А₂₄ - программирование первого модуля;

А₃₄ - программирование второго модуля;

А₄₅ - комплексная отладка модулей;

А₅₆ - разработка программной документации.

 

Сформулируем основные правила  построения сетевого графика.

• Каждая работа представляется одной и только одной дугой, то есть ни одна работа не должна появляться в графике дважды. При этом любая работа в случае необходимости может быть разбита на две или более частей, каждой из которых будет соответствовать своя дуга. Например, программирование модуля можно представить как две работы: ввод текста программы и ее отладку.
• Ни одна пара работ не должна определяться одинаковыми начальным и конечным событиями (в противном случае две различные работы будут идентифицированы одинаково). Возможность такого неоднозначного задания работ существует в тех случаях, когда две (или более) работы могут выполняться одновременно.
• Ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы. Например, комплексная отладка модулей не может быть начата до завершения программирования каждого из них, то есть событие 4 на рис. 1 не произойдет до завершения работ А₂₄ и А₃₄.
• Ни одна работа, выходящая из данного события, не может начинаться до тех пор, пока не произойдет данное событие; например, программирование первого модуля (работа А₂₄) не может начаться, если не закончена разработка его алгоритма (то есть пока не произошло событие 3). Чтобы исключить неоднозначность, вводят фиктивную работу» и фиктивное промежуточное событие. Затраты времени и ресурсов на выполнение фиктивной работы принимаются равными нулю.

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

Работа считается критической, если задержка ее начала приводит к  задержке срока окончания проекта в целом.

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

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

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

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

Расчет резервов времени для  работ проекта включает в себя два этапа.

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

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

1. Наиболее раннее возможное  время наступления j-го события Tp(j) определяется из следующего соотношения:

где i, j - номера предшествующего и последующего событий соответственно;

t _I,J - фактическая продолжительность работы А_ij;

Tp(i) - наиболее раннее возможное время наступления события i. Приведенное соотношение можно проиллюстрировать фрагментом сетевого графика, приведенным на рис. 2.

С содержательной точки  зрения величина Tp(j) представляет собой момент времени, когда будет завершена наиболее «поздняя» из работ, влияющих на j-e событие сети.

2. Наиболее позднее  допустимое время наступления  1-го события Tn(i) определяется из следующего соотношения:

где i, j - номера предшествующего и последующего событий соответственно;

t _I,J - фактическая продолжительность работы А_ij ;

Tn(i) - наиболее позднее допустимое время наступления события i. Приведенное соотношение можно проиллюстрировать фрагментом сетевого графика, приведенным на рис.3.

С содержательной точки  зрения величина Tn(i) представляет собой момент времени, когда должна быть начата наиболее продолжительная (и/или поздно начинающаяся) из работ, выходящих из i-ro события, чтобы не вызвать задержку связанного с ней последующего события сети.

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

 

1. Резерв времени 1-го  события:

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

 

2. Полный резерв времени работы А_ij:

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

 

3. Свободный резерв времени работы А_ij

 

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

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

 

 

При вычислении характеристик сетевого графика длительность проекта определяется без привязки к реальным календарным датам, поэтому при выполнении прямого прохода момент наступления исходного события сети принимается равным нулю, и этот момент считается наиболее ранним возможным моментом наступления исходного события, то есть Тр(1) = 0.

Соответственно, наиболее ранний возможным  момент наступления второго события (для рассматриваемого примера) определяется так:

Расчетные соотношения и результаты вычислений для остальных событий приведены ниже:

 

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

Расчетные соотношения и результаты вычислений для остальных событий  подведены ниже:

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

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

 

 

Рис. 4. Критический путь проекта

 

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

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

 

2. Функциональные подсистемы. Функциональный признак

Любое предприятие состоит  из подразделений, т.е. имеет некоторую  организационную структуру.