Расчет основных сетевых данных
Практическое занятие № 2
ПОСТРОЕНИЕ СЕТЕВОЙ МОДЕЛИ УПРАВЛЕНИЯ И РАСЧЕТ ЕЕ ОСНОВНЫХ ХАРАКТЕРИСТИК.
Введение
Сетевое планирование используется при разработке и внедрении различных проектов, например планов запуска изделия в производство для установления оптимальных сроков окончания работ. Это особенно важно при изготовлении большой номенклатуры многодетальных изделий на одном и том же оборудовании, на одних и тех же рабочих местах. Сетевое планирование связано с представлением объекта в виде сетевой модели, основу которой составляет графическое изображение взаимосвязанных работ и событий.
Целью работы является разработка и оптимизация сетевого графика.
Общие положения и терминология
Сетевой график дает возможность графического представления процессов больших технических и организационных систем и позволяют решать задачи, в которых рассматривается перемещение или выполнение работ во времени.
Сетевой график характеризуется структурой и параметрами дуг. Структура сетевого графика или ее топология определяет, какие вершины связаны между собой дугами, какое направление имеют дуги. Каждую вершину обозначают уникальным индексом, например, порядковым номером.
Дугу обычно обозначают двойной индексацией. В индекс входит номер вершины, из которой выходит дуга, и номер вершины, в которую она входит. Кроме того, каждая дуга имеет свою характеристику, обозначающую продолжительность, стоимость, пропускную способность и т.д.
Работа - процесс, происходящий во времени и требующий затрат и времени, и ресурсов или только времени - ожидание.
В частном случае это может быть связь между событиями, при которой не производится затрат времени, труда или иных ресурсов. Это так называемая фиктивная работа.
Событие - момент окончания работы с получением определенного результата. Событие, в отличие от работы, не имеет длительности во времени. На сетевом графике события обозначают обычно кружками (это вершины сетевого графика) с указанием определенного номера.
Действительная работа на сетевом графике изображается сплошными однонаправленными стрелками, а фиктивные работы, означающие логическую связь, - пунктирными. Над стрелкой указывается продолжительность выполнения работы.
События могут быть:
· исходными;
· промежуточными;
· завершающими.
Исходное - это событие, в которое не входит ни одна работа.
Промежуточное - событие, которое является окончанием одной или нескольких работ и которое позволяет начать последующие работы.
Завершающее - событие, из которого не выходит ни одна работа.
Путь - любая непрерывная последовательность работ в сетевом графике. Путь не должен проходить дважды через одно и то же событие, а его направление определяется направлением стрелок.
Различают:
· путь, предшествующий заданному событию, это путь от исходного события до заданного;
· путь, следующий за заданным событием, - это путь от заданного события до завершающего;
· путь между событиями - это путь между двумя событиями, которые не являются ни исходными, ни завершающими;
· полный путь – это путь от исходного события до завершающего;
· критический путь - это путь наибольшей продолжительности. События, которые лежат на критическом пути, называются критическими.
Продолжительность работ, лежащих между критическими событиями, определяет общую продолжительность работ. Поэтому для сокращения срока наступления завершающего события необходимо сокращать продолжительность работ, лежащих между критическими событиями.
При построении сетевых графиков должны соблюдаться определенные условия:
· В сетевом графике должно быть только одно исходное событие, которое располагается в левой части графика, и только одно завершающее.
· Наличие тупика в сетевом графике свидетельствует об ошибке, допущенной при его составлении; все события, кроме завершающего, должны иметь одну или несколько последующих работ.
· В сетевом графике не должно быть событий, кроме исходного, в которые не входят одна или несколько работ.
· В сетевом графике не должно быть циклов - замкнутых контуров, т.е. путей, соединяющих какое-либо событие с самим собой.
Расчет основных сетевых данных
При расчете временных параметров сетевого графика вводятся следующие основные понятия:
· наиболее ранний возможный срок наступления события;
· наиболее поздний допустимый срок наступления события;
· ранний срок начала любой работы;
· ранний срок окончания любой работы;
· поздний срок начала любой работы;
· поздний срок окончания любой работы;
· свободный резерв времени работы;
· общий резерв времени пути;
· полный резерв времени работы.
Наиболее ранний возможный срок наступления события 
(j) рассчитывается по формуле:
В данной формуле событие Аi должно предшествовать событию Аj.
Наиболее поздний допустимый срок наступления события 
(i)
рассчитывается по формуле:
Зная значения величин (j) и (i) для всех событий сети, можно для любой работы определить следующие характеристики:
ранний срок начала любой работы сетевого графика равен суммарной продолжительности работ на максимальном из предшествующих этой работе путей;
ранний срок окончания любой работы сетевого графике равен раннему сроку начала любой работы, сложенному с ее продолжительностью;
поздний срок окончания любой работы сетевого графика равен разности между продолжительностью критического пути и суммарной продолжительностью работ на максимальном из путей, следующих за данной работой к завершающему событию;
поздний срок начала работы равен разности между поздним сроком окончания этой работы и продолжительностью самой работы.
общим резервом времени любого пути называется разность между продолжительностью критического и рассматриваемого пути сетевого графика. Резерв времени - это время, на которое может быть увеличена продолжительность всех работ, принадлежащих данному пути, при условии сохранения общего срока выполнения работы без изменения. Резервом времени обладают все пути, кроме критического.
полным резервом времени работы называется то предельное время, на которое можно увеличить продолжительность данной работы, не изменив продолжительности критического пути, т.е.
Полный резерв времени используется для определения возможности увеличения длительности работ, не лежащих на критическом пути.
Для построения сетевого графика необходимо, исходя из условий задачи, выделить и пронумеровать события в порядке их следования, затем обозначить каждую работу двумя цифрами, которые определяют номера предыдущего и последующего событий, и определить продолжительность каждой работы. Эти данные нужно свести в таблицу (разновидность структурно-временной таблицы) и, используя их, построить сетевой график. Затем рассчитывают основные параметры сетевого графика, заносят их в соответствующую таблицу, из которой уже можно определить, какие работы обладают резервами времени и величину этих резервов. По результатам расчетов можно осуществлять корректировку сетевого графика с целью нахождения оптимального варианта по определенным критериям.
В качестве примера рассматривается сетевой график, представленный на рис. 1. Над стрелками указаны продолжительности соответствующих работ. Рассчитываются параметры данного сетевого графика. В первую очередь определяются количество (m) и продолжительности ( t(i), i = 1, 2, 3, …, m) всех полных путей:
L1: t(1)1,3,6,7=2+4+3=9;
L2: t(2)1,2,3,6,7=1+3+4+3=11;
L3: t(3)1,2,5,6,7=1+5+2+3=11;
L4: t(4)1,2,5,7 =1+5+8=14;
L5: t(5)1,4,5,7=4+1+8=13;
L6: t(6)1,4,5,6,7=4+1+2+3=10.
В рассматриваемом примере критическим является путь t(4)1,2,5,7, на рис. 1 он выделен толстыми дугами и заштрихованными вершинами графа, а
Ткр = t(4) = 1 + 5 + 8 = 14.
Определяются общие резервы времени полных путей Ri, i = 1, 2, 3, …, m; m – количество полных путей:
R1= Ткр - t(1)1,3,6,7 = 14 – 9 = 5;
R2= Ткр - t(2)1,2,3,6,7 = 14 – 11 = 3;
R3= Ткр - t(3)1,2,5,6,7 = 14 – 11 = 3
R4 = Ткр - t(4)1,2,5,7 = 0;
R5= Ткр - t(5)1,4,5,7 = 14 – 13 = 1;
R6= Ткр - t(6)1,4,5,6,7 = 14 – 10 = 4.
Далее определяются следующие параметры сетевого графика:
§ ранний срок начала работ tрн;
§ ранний срок окончания работtро;
§ поздний срок окончания работ tпо;
§ поздний срок начала работ tпн;
§ полные резервы времени каждой работы 
(i,j)).
Найденные значения заносятся в таблицу вида табл. 1.
Рис. 1. Сетевой график.
Таблица 1.
| Работы | Прод-ть работ | tрн | tро | tпн | tпо |  (i,j)
|
| 1-3 | ||||||
| 1-2 | ||||||
| 1-4 | ||||||
| 2-3 | ||||||
| 2-5 | ||||||
| 3-6 | ||||||
| 4-5 | ||||||
| 5-6 | ||||||
| 6-7 | ||||||
| 5-7 |
Оптимизация
В данном практическом занятии мы ограничимся рассмотрением только некоторых возможных направлений оптимизации.
1. Предположим, расчеты показали, что, реализуя первоначальный сетевой график, мы не уложимся в заданный срок - Ткр > 
(см. лекцию). В этом случае для завершения всего комплекса работ в заданный срок длительность критического пути можно изменить за счет привлечения дополнительных ресурсов.
Проанализируем, например, возможность уменьшения длительности отдельных работ. Длительность выполнения работы 5-7 можно уменьшить, если, например, увеличить число станков. Если принимается двукратное увеличение числа станков, то значение длительности работы 5-7 вместо 8 будет 4 единицы, что, в принципе, может привести к изменению критического пути и соответствующему изменению ее характеристик.
Процесс пересчета сетевого графика в этом случае становится итерационным и за определенное количество шагов Ткр приблизится к (вспомните симплекс-метод).
2. Для того, чтобы высвободить ресурсы для их использования на других работах можно воспользоваться полным резервом времени работы. Например, полный резерв 
(1,3) времени работы а1-3, равный (1,3) = 5, может быть использован
Рис. 2. Полный резерв (1,3) времени работы а1-3 равен 5.
для увеличения длительности либо работы а1-3, либо работ а3-6 и
а6-7, лежащих на пути, проходящем через эту работу. Он может быть распределен каким-либо образом между этими работами.
Далее, в результате анализа мы приходим к выводу, что полный резерв (1,4) времени работы а1-4, равный (1,4) = 1, может быть использован
Рис. 3. Полный резерв (1,4) времени работы а1-4 равен 1.
для увеличения длительности работ(см. рис. 3)а1-4, а4-5, а5-6, а6-7, но не для увеличения продолжительности работы а57, так как она лежит на критическом пути.
Процесс анализа полных резервов времени работы нужно продолжить (а2-3, а3-6, а4-5, а5-6, а6-7). Для большей гарантии такие расчеты необходимо провести применительно к полным резервам.
Двойственный график
Возможно принципиально другое визуальное представление сетевых графиков – в форме двойственного графика
 |
Рис. 4. График двойственный графику рис. 3.
Индивидуальные задания
Каждый студент получает индивидуальное задание на исследование. Номер варианта задания совпадает с номером фамилии студента в групповом журнале.
Каждый вариант задания содержит описание работ в виде таблицы.
| Вариант 30 | |||
| 1 | 2-10 | 3-12 | 4-20 |
| 2 | 7-34 | ||
| 3 | 5-17 | 6-18 | 8-40 |
| 4 | 6-10 | ||
| 5 | 7-19 | ||
| 6 | 8-20 | ||
| 7 | 8-7 |
Первый столбец таблицы содержит номера вершин (событий) задаваемой сети.
В последующих столбцах табл. 2 указываются (через дефис) номера вершин, с которыми соединена рассматриваемая вершина, и значение длительности работы. Так, например, вершина 1 (исток, исходная вершина) соединяется с тремя вершинами: с вершиной 2 (значение длительности работы при этом равно 10), с вершиной 3 (работа - 12) и с вершиной 4 (работа - 20). Вершина 2 соединяется лишь с вершиной 7 через работу – 34….
Как видно из таблицы сеть состоит из восьми вершин, причем восьмая вершина является стоком, конечной вершиной сети.
По заданию студент должен:
1.
² построить сеть в виде графа, на котором указать номера всех вершин и характеристики дуг;
² определить количество (m) и продолжительности (t(i), i = 1, 2, 3, …, m) всех полных путей;
² определить критический путь и его характеристики;
² определить резервы времени полных путей Ri, i = 1, 2, 3, …, m; m – количество полных путей;
² определить основные параметры сетевого графика:
§ ранний срок начала работы tрн;
§ ранний срок окончания работtро;
§ поздний срок окончания работ tпо;
§ поздний срок начала работ tпн;
§ полные резервы времени каждой работы 
(i,j).
Найденные значения заносятся в результирующую таблицу и используются для принятия решения по оптимизации сети.
2. Выбрать варианты оптимизации. Варианты оптимизированных сетей с краткими характеристиками представить в виде отчета.
3. Рекомендуется построить двойственный граф: работы в узлах, а события – дуги. На двойственном графе проанализировать варианты перераспределения резервов и возможности смещения ранних и поздних сроков начала и окончания работ