Лабораторная работа №6
Описание файла
Документ из архива "Лабораторная работа №6", который расположен в категории "". Всё это находится в предмете "математические модели в естествознании и экологии" из 8 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "математические модели в естествознании и экологии" в общих файлах.
Онлайн просмотр документа "Лабораторная работа №6"
Текст из документа "Лабораторная работа №6"
№6.Построение сетевого графика
Лабораторная работа № 6
Тема: Построение сетевого графика. Алгоритм нахождения критического пути. Распределение ресурсов.
Цель работы: 1.Построить сетевой график.
2.Установить все критические пути и время выполнения всего комплекса работ двумя способами.
3.Оптимизировать сетевой график по ресурсам.
При организации работ над различными проектами, планировании комплексов работ широкое распространение получили методы сетевого планирования и управления.
Начальная информация о проекте задаётся перечнем работ, их продолжительностью, последовательностью выполнения (для каждой работы должно быть указано, каким работам она предшествует или за какими следует). Сетевым графиком проекта называют наглядное представление проекта в виде сети. Дуги этой сети представляют собой операции (работы) и являются ориентированными; направление дуг соответствует процессу реализации программы во времени. Отношение упорядочения между операциями задается с помощью событий. Событие определяется как момент времени, когда завершаются одни операции и начинаются другие, и представляется в сети узлом (вершиной).
Критерии, которым должен удовлетворять сетевой график:
-
ни одна работа, представленная дугой, выходящей из некоторой вершины, не может начинаться прежде завершения всех работ, представленных дугами, входящими в данную вершину;
-
каждую пару событий должна соединять не более чем одна работа;
-
в сетевом графике должно быть начальное и конечное событие.
Для выполнения перечисленных требований допустимо введение фиктивных работ (работ нулевой продолжительности, не требующих затраты каких-либо ресурсов).
Пример: Пусть дана таблица комплекса работ, в которой заданы времена выполнения работ и предшествующие работы.
№ работы | Предшествующие работы | Длительность выполнения |
1 | — | 2 |
2 | — | 3 |
3 | — | 5 |
4 | 1 | 1 |
5 | 1 | 4 |
6 | 2 | 2 |
7 | 3,6 | 4 |
8 | 3 | 3 |
9 | 4 | 4 |
10 | 5,9 | 1 |
11 | 6 | 2 |
12 | 7,8,10 | 1 |
Табл.1
Проследим, как строится временной сетевой график на рис. 1.
Начинаем его с узла А0, помещённого в начале координат. Из этого узла исходят три стрелки: а1, а2, а3 (не имеющие предшествующих работ), проекции которых на ось 0t равны временам выполнения соответствующих работ: t1=2, t2=3, t3=5. Работа а4 опирается на работу а1. Проекция стрелки а4 равна t4=1, следовательно, абсцисса узла А4, в которой эта стрелка кончается, должна быть T4=t1+t4=2+1=3. Аналогично строим а5 (T5=t1+t5=2+4=6) и а6 (T6=t2+t6=3+2=5). Работе а7 предшествуют работы 3 и 6. Чтобы показать, что работы а3 и а6 могут выполняться одновременно, введём дополнительный узел А3,6, соединяющийся с узлами А6 и А3 пунктирными линиями (фиктивные работы). Отметим необходимость введения узла А3,6.
На рис.2 представлен вариант сетевого графика без введения узла А3,6, при этом оказывается, что для работы a11 предшествующими являются работы 3 и 6, что не соответствует действительности. Аналогичная ситуация возникает и в случае добавления ребра А6А3.
Работы а3 и а6 кончаются одновременно в t=5, следовательно стрелка а7, начинающаяся в А3,6 и имеющая проекцию на ось Ot равную t7=4, кончается в А7 с абсциссой T7=5+t7=9. Стрелка а8 начинается в А3 и имеет T4=t3+t8=5+3=8. а9 начинается в узле А4 и заканчивается в узле А9 с абсциссой T9=T4+t9=3+4=7. Работа а10 опирается на работы а5 и а9 и, следовательно, не может начинаться раньше, чем закончатся обе эти работы. Поэтому стрелку а10 направим из узла А9, имеющего по сравнению с а5 большую абсциссу. Но при этом, чтобы показать, что а5 предшествует а10, соединим А5 с А9 пунктирной линией. T10=T9+t10=7+1=8.
Стрелка а11 начинается из А6 и заканчивается в А11 с T11=T6+t11=5+2=7. Последней работе а12 предшествуют работы а7, а8, а10. Направим а12 из узла А7, имеющего большую абсциссу. А11 и А7, а также А8 и А7 соединим пунктирными линиями. T12=T7+t12=9+1=10.
Так как работа а12 завершается последней, то узел А12=А означает окончание всего комплекса работ. Отметим этот узел жирным кружком и соединим с ним пунктирной стрелкой узел А11- окончание работы А11, на которую, кроме конца работ, никто не опирается.
Таким образом, временной сетевой график комплекса работ построен, время Т=10 от начального узла А0 до завершающего А=А12 представляет собой минимальное время, за которое может быть завершен комплекс работ.
Обратим внимание на следующее обстоятельство: время исполнения проекта представляет собой сумму времён исполнения не всех работ, а только некоторых из них: T=t3+t7+t12=t2+t6+t12=10.
Работа называется критической, если задержка её начала приводит к увеличению срока окончания всей программы.
Критический путь определяет непрерывную последовательность критических работ, связывающих исходное и завершающее события сети.
На рисунке критические работы показаны жирными стрелками. В нашем примере критическими являются работы: а2, а3, а6, а7, а12. Каждая из “некритических” работ имеет временные резервы и может быть закончена с некоторым опозданием без того, чтобы это отразилось на сроке выполнения комплекса в целом.
Резервы, соответствующие некритическим работам, легко могут быть определены по сетевому графику.
Назовём некритической дугой совокупность некритических работ и узлов, начинающуюся и кончающуюся на критическом пути (принимая во внимание и фиктивные работы).
На рис. 1 имеются четыре не критические дуги:
А0а1А1а4А4а9А9а10А10А7, А0а1А1а5А5А9а10А7, А6а11А11А12, А3а8А8А7.
На первой из дуг лежат 4 некритические работы, на второй - 3, на третьей и четвёртой - по 1.
Каждой некритической дуге соответствует определённый временной резерв, который может быть распределён между некритическими работами, лежащими на дуге.
Например, на первой дуге лежат 4 некритических работы, на замыкающем её отрезке критического пути А0а2А2а6А6А3,6а7А7 - 3 критических работы. Резерв времени, приходящийся на работу а1, а4, а9, а10 равен R1,4,9,10=t2+t6+t7-(t1+t4+t9+t10)=3+2+4-(2+1+4+1)=1.
Аналогично найдём резервы на остальных некритических дугах:
R1,5,10=t2+t6+t7-(t1+t5+t10)=3+2+4-(2+4+1)=2
R11=t7+t12-t11=4+1-2=3
R8=t7-t8=4-3=1.
Критические пути: a3a7a12 и a2a6a7a12.
Выше описан графический способ определения критических работ и путей. В случае , когда число работ в проекте достаточно велико и связи между работами очень сложны, построение сетевого графика и нахождение по нему критического пути вызывают затруднения. Далее представлен аналитический способ определения критических работ.
Пусть t1,...,tn - работы, ti - время выполнения i-й работы.
Обозначим:
ES(i) - самый ранний момент, в который работа ti может быть начата;
ET(i) - время возможного наиболее раннего окончания работы ti;
LS(i) - время возможного наиболее позднего начала работы ti.
LT(i) - время наиболее позднего завершения работы ti.
Алгоритм.
1) Прямой просмотр работ (по таблице от начала до конца) для определения ES(i), ET(i)
2) Обратный просмотр (по таблице от конца до начала)
Определяем - время выполнения всего проекта.
Критические работы i, тогда Резерв(i)=0.
Пример.
Расчет для проекта, представленного в Табл.1:
№ | Пред. работы | Длит. выпол. | ES(i) | ET(i) | LS(i) | LT(i) | Резерв |
1 | — | 2 | 0 | 2 | 1 | 3 | 1 |
2 | — | 3 | 0 | 3 | 0 | 3 | 0 |
3 | — | 5 | 0 | 5 | 0 | 5 | 0 |
4 | 1 | 1 | 2 | 3 | 3 | 4 | 1 |
5 | 1 | 4 | 2 | 6 | 4 | 8 | 2 |
6 | 2 | 2 | 3 | 5 | 3 | 5 | 0 |
7 | 3,6 | 4 | 5 | 9 | 5 | 9 | 0 |
8 | 3 | 3 | 5 | 8 | 6 | 9 | 1 |
9 | 4 | 4 | 3 | 7 | 4 | 8 | 1 |
10 | 5,9 | 1 | 7 | 8 | 8 | 9 | 1 |
11 | 6 | 2 | 5 | 7 | 8 | 10 | 3 |
12 | 7,8,10 | 1 | 9 | 10 | 9 | 10 | 0 |
Табл.2