Сетевое планирование и управление. 5

     Содержание 

Введение…………………………………………………………………………...5

1. Сетевая  модель …………………………………………………………………6

    1.1 Сетевая модель и её основные элементы…………………………………6

    1.2 Порядок и правила построения  сетевых графиков………………………9

2. Модели  сетевого планирования и управления……………………………...11

     2.1 Критическое время, критический  путь, резервы времени всех работ………….…………………………………………………………………...12

     2.1.1 Критический путь через определение параметров событий………...12

     2.1.2 Критический путь через определение параметров работ……………14

     2.2 Сетевое планирование в условиях  неопределенности…………………18

     2.3 Оптимизация сетевого графика  методом «время-стоимость»………...22

3. Моделирование процесса с помощью сетевого графика…………………...25

     3.1 Линейная диаграмма……………………………………………………..25

     3.2 Определение временных параметров событий…………………………26

     3.3 Определение временных параметров  работ…………………………….27

     3.4 Оценка вероятности выполнения  проекта в срок………………………31

     3.5 Частная оптимизация заданного  сетевого графика ……………………31

Заключение……………………………………………………………………….34

Список  литературы………………………………………………………………35 
 
 
 
 
 
 
 
 

     Введение 

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

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

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

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

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

1. Сетевая модель

1.1 Сетевая модель  и её основные  элементы 

     Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных  работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком. Отличительной особенностью сетевой модели является четкое определение всех временных взаимосвязей предстоящих работ. [7, c.315]

     Главными  элементами сетевой модели являются события и работы.

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

     Событие – это момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта. Событие может быть частным результатом отдельной работы или суммарным результатом нескольких работ. Событие может совершиться только тогда, когда закончатся все работы, ему предшествующие. Последующие работы могут начинаться только тогда, когда событие совершится. Отсюда двойственный характер события: для всех непосредственно предшествующих ему работ оно является конечным, а для всех непосредственно следующих за ним – начальным. При этом предполагается, что событие не имеет продолжительности, совершается как бы мгновенно. Поэтому каждое событие, включаемое в сетевую модель должно быть полно, точно и всесторонне определено, его формулировка должна включать в себя результат все непосредственно предшествующих ему работ.[3,c.49]

     Среди событий сетевой модели выделяют исходное и завершающееся события. Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающееся событие не имеет последующих работ и событий. Пример фрагмента сетевого графика сетевого графика представлен на рисунке 1.

Рисунок 1 – Фрагмент сетевого графика.

      На рисунке 2 приведен сетевой график задачи моделирования  и построения оптимального плана  некоторого экономического объекта. Чтобы  решить эту задачу, необходимо провести следующие работы: А – сформулировать проблему исследования; Б – построить математическую модель изучаемого объекта; В – собрать информацию; Г – выбрать метод решения задачи; Д – построить и отгладить программу для ЭВМ; Е – рассчитать оптимальный план; Ж – передать результаты расчета заказчику. Цифрами на графике обозначены номера событий, к которым приводит выполнение соответствующих работ.

     Рисунок 2 – Структурная сеть. 

      Рисунок 3 –  Сеть «работы – связи».

     Рисунок 4 – Сеть «события – работы».

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

     Если  принцип построения сетей иной –  без событий, в такой сети вершины  графа означают определенные работы, а стрелки – зависимости между этими работами, определяющие порядок их выполнения. В качестве примера сетевой график – «события – работы» задачи моделирования и построения оптимального плана некоторого экономического объекта, приведенный на рисунке 2, представлен в виде сети «работы – связи» на рисунке 3. А сетевой график «события – работы» той же задачи, но с неудачно составленным перечнем работ, представлен на рисунке 4.

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

2. Порядок и правила построения сетевых графиков

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

       При построении сетевого графика необходимо соблюдать ряд правил.

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

     2. В сетевом графике не должно  быть «хвостовых» событий (кроме  исходного), которым не предшествует  хотя бы одна работа.

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

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

     5. В сети рекомендуется иметь  одно исходное и одно завершающее  событие. Если в составленной  сети это не так то добиться  желаемого можно путем введения  фиктивных событий и работ. [1, c. 147]

     Фиктивные работы и события необходимо вводить и в ряде других случаев. Один из них – отражение зависимости событий, не связанных с реальными работами. Другой – неполная зависимость работ. Кроме того, фиктивные работы могут вводиться для отражения реальных отсрочек и ожидания. В отличии от предыдущих случаев здесь фиктивная работа характеризуется протяженностью во времени.

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

     Упорядочение  сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. [6, c.253] 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Модели сетевого  планирования и  управления 

     Одно  из важнейших понятий сетевого графика  – понятие пути. Путь – любая  последовательность работ, в которой  конечно событие каждой работы совпадает  с начальным событием следующей  за ней работы. Среди различных  путей сетевого графика наибольший интерес представляет полный путь – любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим. [6, c.326]

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

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

     2.1 Критическое время, критический путь, резервы времени всех работ.

     Основные временные параметры сетевых графиков приведены в таблице 1.

     Таблица 1 - временные параметры сетевых графиков.

     2.1.1 Критический путь через параметры событий 

     Событие не может наступить прежде, чем  совершаться все предыдущие работы. Поэтому ранний срок t_р(i) совершения i-го события определяется продолжительностью максимального пути, предшествующего этому событию:

     t_р(i) = maxt(L_пi),

где L_пi - любой путь, предшествующий i–му событию, то есть путь  от исходного до i-го события в сети.

     Если  событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

     t_р(j) = max [t_р(i)+t(i,j)].

     Задержка  свершения события i по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит, и на сроке выполнения комплекса работ), до тех пор, пока сумма срока свершения этого события и продолжительности (длины) максимального из последующих за ним путей не превысит длины критического пути.[6, c.328]

     Поэтому поздний (или предельный) срок t_п (i) совершения i – го события равен:

     t_п(i) = t_кр – maxt(L_ci),

где L_ci - любой путь, следующий за i-м событием, т.е. путь от i-го до завершающего события сети.

     Если  событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле:

     t_п(i) = min[t_п(j) - t(i, j)].

     Резерв  времени R(i) i–го события определяется как разность между поздним и ранним сроками его свершения:

     R(i) = [t_п(i) – t_р(i)].

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

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

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

     Если  сетевой график имеет единственный критический путь, то этот путь проходит через все критические события, то есть события с нулевыми резервами  времени.  Если критических путей  несколько, то выявление их с помощью критических событий может быть затруднено, так как через часть критических путей могут проходить как критические, так и не критические пути.  В этом случае для определения критических путей рекомендуется использовать критические работы. [6, c. 329] 

     2.1.2 Критический путь через параметры работы

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

     Очевидно, что ранний срок t_рн(i,j)начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i:

     t_рн(i,j) = t_р(i).

     Тогда ранний срок t(i,j) окончания работы (i,j) определяется по формуле:

     t_ро(i,j)= t_р(i)+t(i,j).

     Ни  одна работе не может окончиться позже  допустимого позднего срока своего конечного события. Поэтому поздний  срок t_по(i,j) окончания работы (i,j) определяется соотношением:

       t_по(i,j) =t_н(j),

     а поздний срок t_пн(i,j) начала этой работы – соотношением:

     t_пн(i,j) = t_н(j) - t(i,j).

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

     Все некритические пути имеют резерв времени пути.

     Резерв  времени пути определяется как разность между длиной критического и рассматриваемого пути:

     R(L) = t_кр- t(L).

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

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

     Среди резервов времени работ выделяют 4 разновидности.

     1) Полный резерв времени работы  (i,j) показывает, насколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв R(i, j) определяется по формуле:

     R_п(i,j) = t_п(j) – t_р(i) - t(i,j).

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

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

     Остальные резервы времени работы являются частями её полного резерва.

     Частный резерв времени первого вида R₁ работы (i,j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока её начального события. Этим резервом можно располагать при выполнении данной работы в предположении, что её начальное и конечное события свершаются в свои самые поздние сроки (рис. 5, б). R₁ находится по формуле:

     R₁(i,j) = t_п(j) – t_п(i) – t(i,j),

     R₁(i,j) = R_п (i,j) – R(i).

     Рисунок 5 – Резервы времени работы.

     Частный резерв времени второго вида, иди  свободный резерв времени R_c работы (i,j), представляет часть полного резерва времени, на которую модно увеличить продолжительность работы, не изменив при этом раннего срока её конечного события. Эти резервом можно располагать при выполнении данной работы в предположении, что её начальное и конечное события свершаться в свои самые ранние сроки (рис. 5,в). R_c находится по формуле:

     R_c(i,j) = t_р(j) – t_р(i) – t(i,j),

     R_с(i,j) = R_п (i,j) – R(i).

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

     Независимый резерв времени R_н работы (i,j) – часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки (рис. 5, г),

     R_н(i,j) = t_р(j) – t_п(i) – t(i,j),

     или

     R_н(i,j) = R_п (i,j) – R(i).

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

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

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

     Работы, лежащие на критическом пути, так  же, как и критические события, резервов времени не имеют.

     Если  на критическом пути лежит начальное  событие i, то

     R_п(i,j) =R₁(i,j).

     Если  на критическом пути лежит конечное событие j, то

     R_п(i,j) =R_с(i,j).

     Если  на критическом пути лежат начальное  и конечное события i и j, но сама работа не принадлежит этому пути, то

     R_п(i,j) =R₁(i,j)=R_с(i,j) =R_н(i,j).

     Данное  соотношение можно использовать при проверке правильности расчетов резервов времени отдельных работ. [6, c. 335] 

     2.2 Сетевое планирование в условиях неопределенности

     При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Такое предположение в действительности выполняется редко: система СПУ обычно применяется для планирования сложных разработок, не имевших в прошлом никаких аналогов. Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений. То есть  продолжительность работы t(i,j) является случайной величиной, характеризующей своим законом распределения, а значит, своими числовыми характеристиками  - средним значением, или математическим ожиданием, t(i,j) и дисперсией σ²(i,j).

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

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

     Простейшим  распределением с подобными свойствами является известное в математической статике β-распределение . Анализ большого числа статистических данных показывает, что β-распределение можно использовать в качестве априорного для всех работ.

     Для определения числовых характеристик  t(i,j) и σ²(i,j) этого распределения для работы (i,j) на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки (рис.3):

1) оптимистическую  оценку t₀(i,j), то есть продолжительность работы (i,j) при самых благоприятных условиях;

2) пессимистическую оценку t_п(i,j), то есть продолжительность работы (i,j) при самых неблагоприятных условиях;

3) наиболее вероятную оценку t_нв(i,j), то есть продолжительность работы (i,j) при нормальных условиях.

     Предположение о β-распределении продолжительности работы (i,j) позволяет получить следующие оценки её числовых характеристик:

t(i,j) = [t₀(i,j)+4t_нв(i,j)+t_п(i,j)]/6,