Содержание

1.Условия  задачи и исходные  данные

• количество  работы n;
• минимально возможное время выполнения k-ой работы t_mink.

• наиболее  вероятное время выполнения k - ой работы t_0k;
• максимально возможное время выполнения k - ой работы t_{max k};
• заданное время наступления конечного события (n) t_доп.

     Исходные  данные

2. Способы определения продолжительности работы

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

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

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

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

     а) четко отразить структуру комплекса работ;

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

     г) использовать для обработки большого количества информации современные средства вычислительной техники;

     д) оперативно выдавать данные о фактическом состоянии дел проведения комплекса работ;

     е) проводить корректировку календарного плана.

     Структура систем СПУ обусловлена необходимостью выполнения основных процессов управления:

     а) получения информации о состоянии и ходе выполнения комплекса работ;

     б) преобразования информации;

     в) принятия решений;

     г) формирования и передачи команд управления

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

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

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

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

     Рис. 1

     Информационная  система СПУ предназначена для  получения информации о состоянии комплекса работ, отображения этой информации на плане, отображения плана проведения комплекса работ, для формирования команд управления и передачи этих команд.

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

     Таким образом, системы СПУ – сложные командно-информационные системы, предназначенные для планирования, контроля и управления такими видами деятельности, как:

     а) проведение научно-исследовательских и опытно-конструкторских работ;

     б) подготовка и освоение производства новых видов промышленной продукции;

     в) строительство и монтаж промышленных и гражданских объектов;

     г) организация эксплуатационных мероприятий и т.д.

3. Основные положения методов сетевого планировании

     Сетевой график есть графическое представление комплекса проводимых работ.

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

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

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

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

     Различают два вида сетей: детерминированные  и стохастические. В детерминированной  сети конечное событие (окончание работ) наступает после свершения всех входящих в нее событий (завершения всех видов работ). В стохастической сети время всех или некоторых работ является случайной величиной.

     Детерминированная сеть есть частный случай стохастической сети. В ней вероятности необходимости  работ равны единице.

     Сетевые графики составляются в следующей последовательности:

• формулируется конечная цель;
• определяется конечное событие;
• составляется логическая последовательность простых работ;
• составляется последовательность событий.

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

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

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

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

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

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

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

4. Определение продолжительности работ

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

     1. Для часто повторяющихся работ,  по которым имеются определенные нормативы времени, продолжительность работ проставляется в соответствии с этими нормативами с учетом конкретных условий. Эти нормативы могут быть оговорены в эксплуатационной документации (инструкции по эксплуатации, инструкции по ТО и др.).

     2. По статистическим данным, накопленным  в процессе эксплуатации

             (1)

где t_i,j – средняя продолжительность i,j-й работы;

     t_i,j,k – продолжительность i,j-й работы в k-м опыте или на k-й РТС;

     n – количество опытов (РТС).

     Этой  формулой следует пользоваться при  достаточно большом объеме статистических данных.

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

     Опытные эксперты дают три возможные оценки времени:

• оптимистическая оценка – наименьшая из возможных продолжительность работ t_min соответствующая наиболее благоприятным условиям ее выполнения. Вероятность выполнения работы за это время в большинстве случаев равна 0,01;
• пессимистическая оценка – наибольшая из возможных продолжительность работ t_max, соответствующая времени выполнения работы в наиболее неблагоприятных условиях. Вероятность выполнения работы за такое время также составляет 0,01;
• наиболее вероятная оценка t₀, соответствующая набольшей вероятности выполнения работ за такое же время.

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

     При анализе сетевых графиков необходимо для каждой работы определить среднее время её выполнения и дисперсию этого времени σ_i,j².

     Для β - распределения времени выполнения работы эти значения определяются по выражениям:

     На  практике возникают трудности при  определении t_н.в. поэтому при определении t_i,j можно ограничиться только использованием двух оценок времени t_max и t_min.

     В этом случае:

     Разница в результате расчёта t_i,j по формуле (3) по сравнению с расчётом по формуле (2) не превышает 1%.

5. Методы анализа сетевых моделей

5.1 Методы расчёта временных параметров детерминированных сетей

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

     L_d – полный путь; %

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

L_сi, – любой путь следующий за i-ым событием, т.е. путь от i-го события до конечного;

L_ij – путь от i-го события;

T(Ln) – продолжение критического пути;

Т(Ln) – продолжительность полного пути Ln;

ΔТ(Ln) – резерв времени относительно полного пути Ln, т.е.

     ΔТ(Ln) = Ткр – Т(Ln)

Тр(i) – наиболее ранний срок наступления i-го события, т.е.

     Тp(i) = max T(Lni);

Тn(i) – наиболее поздний срок наступления i-го события, т.е.;

     Тn(i) = T_p – maxT(Li,j)

ΔТi – резерв времени i-го события, т.е.

     ΔТ(i) = Тn(i) –Тр(i).

     Величина  ΔТ(i) показывает, на какое время можно задержать наступление i-го события, не вызывая общего срока выполнения комплекса работ;

T_РН(i,j) – cрок раннего начала работы (i,j), т.е.

     T_РН(i,j) = Тр(i)

Т_РO (i,j) –срок раннего окончания работы (i,j),т.е.

     Т_PO (i,j) = Тp(i) + (i,j);

Т_ПН (i,j) – срок позднего начала работы (i,j), т.е.

     Т_ПН (i,j) = Tn(j) – (i,j);

Т_ПО (i,j) – срок позднего окончания работы (i,j) т.е.

     Т_ПО (i,j) = T_n(j)

ΔТ_n(i,j) – полный резерв времени работы (i,j), т.е.

     ΔТ_n(i,j) = Tпн (i,j) – Т_ПН (i,j) или

     ΔТ_n(i,j) = Т_по (i,j) – Т_PO (i,j)

     ΔТ_n(i,j) = Т_по (i,j) – Т_ПН (i,j) – (i,j) 

     Полным  резервом времени работы ΔТ_n(i,j) называют величину, показывающую, на какое время может увеличиться её продолжительность. Для любой работы, лежащей на критическом пути, полный резерв времени равен нулю;

     ΔТ¹_ч – частный резерв времени первого вида для работы (i,j), т.е.

     ΔТ¹_ч  = Тn(j) – Tn(i) –

где ΔТ¹_ч (i,j) – часть полного резерва времен, которая может быть использована для увеличения продолжительности данной и последующих работ без затрат времени предшествующих;

     ΔТ²_ч(i,j) –частный резерв времени второго вида для работы (i,j), т.е.

     ΔТ²_ч(i,j) = Тр(j) – Tp(i) –

где ΔТ²_ч(i,j) – часть полного резерва времени работы, которая может быть использована для увеличения продолжительности данной и предшествующих работ без нарушения резерва времени последующих работ без нарушения резерва времени последующих работ;

ΔТ_c(i,j) – свободный резерв времени работы (i,j) сетевого графика, т.е.

     ΔТ_c(i,j) = Tp (i,j) – T_П (i,j) –

где ΔТ_c(i,j) – резерв времени, который может быть использован для увеличения продолжительности только работы (i,j).

5.2. Методы расчета временных параметров стохастических сетей

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

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

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

     Зная  плотности вероятностей распределения  продолжительности всех путей сети ω(t) можно по всем путям вычислить вероятность выполнения планируемого комплекса работ за заданное время t. Например, для s-го пути:

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

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

     СТАТИСТИЧЕСКОЕ  МОДЕЛИРОВАНИЕ является наиболее универсальным методом и достаточно точным средством получения характеристик стохастических сетей. Суть его состоит в следующем:

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

     в определении временных параметров сети на основании данных, полученных при одной реализации статистических испытаний;

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

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

     МЕТОД УСРЕДНЕНИЯ находит наиболее широкое  применение в анализе стохастических сетей. Суть этого метода состоит  в использовании для вычисления вероятностных характеристик сети оценки математического ожидания и дисперсии работ

     Исходными данными для метода усреднения вероятностные  оценки продолжительности каждой работы (см.3).

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

     1. Для каждой работы по приведенным  выше формулам оцениваются величины  t_ож(i,j) и σ²(i,j). Эти величины являются основными и обычно наносятся на сетевой график.

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

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

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

     Если  таких путей несколько, то оценка дисперсии принимается равной максимальному значению оценки дисперсии этих путей.

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

     Согласно  принятому допущению, среднее значение наступления конечного события Т_oж и его дисперсия σ²_Tож определяются по формулам:

где S, г – события, лежащие на критическом пути.

     Вероятность наступления конечного события  за директивное время Т_д определяется в соответствии с формулой: