reforef.ru 1

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


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

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

Термин «работа»:

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

  2. Ожидание – протяженный во времени процесс, не требующий затрат труда.

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

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

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

Среди событий сетевой модели выделяют исходное и завершающее события.

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


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

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


Правило построения:


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


Здесь либо работа (2;3) не нужна (ее необходимо онулировать), либо не замечена необходимость определенной работы, следующей за событием 3.


  1. В СГ не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа. Здесь работа, предшествующая работе 3 не предусмотрена, поэтому событие 3 не может свершиться, и не может быть выполнена работа (3;5).


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



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




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


Обычно принято под (I;j) понимать работу, связывающую i–ое событием с j-ым событием. Однако, содержание этих работ, состав привлекаемых исполнителей и количество затрачиваемых на работы ресурсов может существенно отличаться. В этом случае рекомендуется ввести фиктивное событие (событие 2’).

Фиктивная работа (2’;2). При этом одна из параллельных работ (1;2’) замыкается на этом фиктивном событии. Фиктивные работы отражаются на графике пунктирными линиями.




  1. В сети рекомендуется иметь 1 исходное и 1 завершающее событие.


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


Фиктивные работы и события необходимо вводить в случаях:

  1. отражения зависимости событий, не связанных с реальными работами.


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

Это обстоятельство требует введения фиктивной переменной.

  1. н
    Работа «C» требует для своего начала завершение работ «A и B», но работа «D» связана только с работой «B», а от работы «A» не зависит. Тогда требуется введения фиктивной работы «F» и события 3’.
    е полная зависимость работ.


C

3) для отражения реальных отсрочек и ожиданий.


  1. Упорядочение СГ. Понятие о пути.

Предположим, что при составлении некоторого проекта выделено 12 событий: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 и 24 связывающие их работы: (0;1), (0;2), (0;3), (1;2), (1;4), (1;5), (2;3), (2;5), (2;7), (3;6), (3;7), (3;10), (4;8), (5;7), (5;8), (6;10), (7;6), (7;8), (7;9), (7;10), (8;9), (9;11), (10;9), (10;11). Необходимо составить и упорядочить СГ.

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

ак следует из перечня работ исходным событием СГ является событие 0, а завершающим – 11. Полагая на СГ изменение времени слева направо поместим события: «0» в левую часть графика, «11» - в правую, разместив между ними промежуточные события в некотором порядке, соответствующими их номерам. События свяжем работами-стрелками в соответствии с перечнями работ.



Рис .1.


Разобьем условно СГ на несколько вертикальных слоев (обводим их пунктирными линиями и обозначим их римскими цифрами).

П
Продолжая указанную процедуру вычеркивания получим 4-ый слой с событиями 5 и 3, 5 слой с событием 7, 6 слой с событиями 6 и 8, 7 слой с событием 10, 8 слой с событием 9 и 9 слой с событием 11.
оместив в 1 слое начальное событие, мысленно вычеркнем из графика (рис.1.) это событие и все выходящие из него работы-стрелки, тогда без входящих стрелок останется событие 1. Вычеркнув мысленно событие 1 и все выходящие из него работы без входящих стрелок останется 2 и 4 события, которые образуют третий слой.


Рис.2.


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


Рис. 3.


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

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

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

Критическими называются также работы и события, расположенные на этом пути. Для рассматриваемого нами СГ (рис 3) полными путями будут:


0-1-2-7-10-11 продолжительностью 8+9+3+5+13=38 суток;

0-1-3-5-6-10-11 продолжительностью 46 суток;

0-3-5-6-9-10-11 продолжительностью 57 суток.

Последний путь имеет наибольшую продолжительность (57) поэтому он является критическим.

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

Определив критический путь мы тем самым установим критические события сети: 0,3,5,6,9,10,11 и критические работы: (0;3), (3;5), (5;6), (6;9), (9;10), (10;11).

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

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


Так как критическое время комплекса работ равно координате на оси времени самого правого конца всех отрезков диаграммы тогда:

(Суток)

  1. Временные параметры событий СГ-ков (продолжительность пути и критического пути, резерв времени пути).


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

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

,

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

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



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

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



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

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




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



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

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


  1. Временные параметры работ СГ (сроки начала и окончания работ).

Продолжительность работы обозначается .

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

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


Ранний срок оканчания работы определяется по формуле:




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



- начало работы j.

А поздний срок начала работы - определяется соотношением



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

6. Временные параметры работ сетевых графиков (резервы времени).

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

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

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

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


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

(14.11)

  1. Частный резерв времени первого вида R1 работы есть часть полного резерва времени, на которую можно увеличить продолжи­тельность работы, не изменив при этом позднего срока ее начально­го события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаются в свои самые поздние сроки.


(14.12)

(14.13)


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


(14.14)

(14.15)


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

  1. Н
    (14.16)
    (14.17)

    езависимый резерв времени Rн работы (i, J)
    — часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки .




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

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

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

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

Если на критическом пути лежит начальное событие I, то . (14.18)

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


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

(14.20)

Соотношения (14.18)—(14.20) можно использовать при провер­ке правильности расчетов резервов времени отдельных работ.

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

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

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

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

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




Для определения числовых характеристик tср (i, J), и ?^2(i, j) этого распределения для работы (/, у) на основании опроса ответ­ственных исполнителей проекта и экспертов определяют три вре­менные оценки :

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

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

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

Предположение о ?-распределении продолжительности рабо­ты (/, J) позволяет получить следующие оценки ее числовых ха­рактеристик:


(14.21)


(14.22)




Замечание, обычно специалистам сложно оценить наиболее вероятное время выполнения работы tнв(I;j). Поэтому в реальных проектах используется упрощенная (и менее точная) оценка средней продолжительности работы (/', у) на основании лишь двух задаваемых временных оценок to(i, j) и tп(i, j):

(14.23)

Зная tср (i, J), и ?^2(i, j), можно определять временные параметры сетевого графика и оценивать их надежность.

Так, при достаточно большом количестве работ, принадлежа­щих пути L, и выполнении некоторых весьма общих условий можно применить центральную предельную теорему Ляпунова, на основании которой можно утверждать, что общая продолжитель­ность пути L имеет нормальный закон распределения со средним значением tср (L), равным сумме средних значений продолжитель­ности составляющих его работ tср (I;j) и дисперсией ?^2(L), равной сумме соответствующих дисперсий ?^2(i, j):



(14.24)
(14.25)


Предположим, что сетевой график на представляет сеть не с детерминированными (фиксированными), а со случай­ными продолжительностями работ и цифры над работами-стрелками указывают средние значения tср(I;j) продолжительности соответствующих операций, найденные по формулам и известны все дисперсии ?^2(i,j), вычисленные по фор­муле (14.22).

Так, tср Kp=6l будет означать, что длина критического пути лишь в среднем составляет 61 сутки, а в каждом конкретном про­екте возможны заметные отклонения длины критического пути от ее среднего значения (причем, чем больше суммарная дисперсия продолжительности работ критического пути, тем более вероятны значительные по абсолютной величине отклонения).



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

Полагая tKp случайной величиной, имеющей нормальный за­кон распределения, получим

(14.26)


(на рис. 14.11 это площадь заштрихованной фигуры), где Ф(z) — значение интеграла вероятностей Лапласа, где ;

?^2кр—среднее квадратическое отклонение длины критического пути:

(14.27)



а t кр, ?^2 кр определяются по формулам (14.24) и (14.25).

Если мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходи­мо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т.п. — об этом речь пойдет дальше). Если значительна (например, более 0,8), то, очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.

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

(14.28)

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

Анализ сетевого графика начинается с анализа топологии сети, включающего контроль построения сетевого графика, установле­ние целесообразности выбора работ, степени их расчленения.

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


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

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

(14.29)

t(Lmax)— продолжительность максимального пути, прохо­дящего через работу (I;j);

tкр — продолжительность (длина) критического пути;

t'кр — продолжительность отрезка рассматриваемого пути, сов­падающего с критическим путем.

(14.30)

где Rn(i, j) — полный резерв времени работы (/, j).

Коэффициент напряженности Kн(i, j) может изменяться в пре­делах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути).

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

Работы могут обладать одинаковыми полными резервами, но степень напряженности сроков их выполнения, выражаемая ко­эффициентом напряженности Kн(i, j), может быть различна. И наоборот, различным полным резервам могут соответствовать одинаковые коэффициенты напряженности.

Больший полный резерв одной работы (по сравнению с другой) не обязательно свидетельствует о меньшей степени напряженности ее выполнения. Так, в рассмат­риваемой сети, хотя работа (2, 7) обладает большим полным резервом по сравнению с работой (6, 10): Rn(2, 7)= 23 Rп(6, 10) = 14, но имеет вдвое больший коэффициент напряженности: Кн(2, 7) = 0,52 против Кн(6, 10) = 0,26. Это объясняется разным удельным весом полных резервов работ в продолжительности отрезков максимальных путей, не совпадаю­щих с критическим путем.


Вычисленные коэффициенты напряженности позволяют до­полнительно классифицировать работы по зонам. В зависимости от величины Kн(i,J) выделяют три зоны: критическую (KH(i, у)>0,8); подкритическую (0,6<.Kн(i, J)<0,S); резервную (Kн(i, у)<0,6).

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

В первую очередь принимаются меры по сокращению продолжи­тельности работ, находящихся на критическом пути. Это достигается:


  • перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических (например, перевод час­ти исполнителей, оборудования с некритических путей на работы критического пути); при этом перераспределение ресурсов долж­но идти, как правило, из зон, менее напряженных, в зоны, объе­диняющие наиболее напряженные работы;

  • сокращением трудоемкости критических работ за счет пере­дачи части работ на другие пути, имеющие резервы времени;

  • параллельным выполнением работ критического пути;

  • пересмотром топологии сети, изменением состава работ и структуры сети.

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

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


10. Оптимизация сетевого графика методом «время – стоимость».

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


К
в условиях разработки; b(i;j) —нормальная продолжительность выполнения работы (i;j). При этом стоимость с (i;j) работы (/, J) заключена в границах от Cmin (i;j) (при нормальной продолжительности работы) до Cmax(i;j) (при экстренной продолжительности работы).

омплексная оптимизация представляет собой нахождение оп­тимального соотношения величин стоимости и сроков выполне­ния проекта в зависимости от конкретных целей, ставящихся при его реализации. При использовании метода "время — стоимость" предполага­ют, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа (i;j) характеризуется продолжительностью t(i;j), которая может находиться в пределах от a(i;j) до b(i;j), где а (i;j) — минимально возможная (экстренная) продолжитель­ность работы, которую только можно осуществить

Используя аппроксимацию по прямой, можно легко найти изменение стоимости работы ∆C (i;j) при сокращении ее продолжительности на величину

∆C(i;j)=[b(i,j)-t(i;j)]h(i;j).

Величина h(i;j), равная тангенсу угла наклона аппроксими­рующей прямой, показывает затраты на ускорение работы (i;j) (по сравнению с нормальной продолжительностью) на единицу времени:

h(i;j)=tg?= (Cmax(i;j)- Cmin (i;j))/ (b(i;j)-a(i;j))

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


С=?C(i;j)

i;j

уменьшится на величину

С1 =?∆C(i;j)=? [b(i,j)-t(i;j)]h(i;j).

i;j i;j
Для проведения частной оптимизации сетевого графика кроме продолжительности работ t(i;j), необходимо знать их граничные значения а (i;j) и b (i;j). Продолжитель­ность каждой работы t(i;j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного ре­зерва времени Rc (i;j).
11. Основные понятия. Классификация СМО. Понятие Марковского случайного процесса.

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

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

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

В качестве показателя эф-ти СМО используют:

1.среднее число заявок обслуживаемых в ед времени

2.среднее число заявок в очереди

3.среднее время ожидания обслуживания

4.вероятность отказа в обслуживании

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

  • Первая пришла- первая обслужена.

  • Последняя пришла – первая обслужена.

  • Обслуживание с приоритетом.

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