тематический факультет Кафедра прикладной математики и информатики КУРСОВАЯ РАБОТА Метод

Работа добавлена на сайт samzan.net:

Учреждение образования

«Белорусский государственный педагогический университет

имени Максима Танка»

Математический факультет

Кафедра прикладной математики и информатики

КУРСОВАЯ РАБОТА

Методы сетевой оптимизации комплекса работ

Студентка_______ К.И. Иванова

Научный руководитель

_______________А. Х. Уазиз

Защищена «___»______2013 г.

с отметкой «________»

_________ / _________

________ / __________

Минск,2013

Введение

Тема моей курсовой работы-методы сетевой оптимизации комплекса работ

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

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

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

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

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

Задачи: научиться проводить сетевое планирование комплекса работ и рассчитывать резервы времени на конкретном примере.

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

Глава 1.Сетевое планирование

1.1 Из истории системы сетевого планирования и управления

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

Второй этап. Методики сетевого планирования были разработаны в конце 50-х годов в США. В 1956 г. М. Уолкер из фирмы "Дюпон", исследуя возможности более эффективного использования принадлежащей фирме вычислительной машины Univac, объединил свои усилия с Д. Келли из группы планирования капитального строительства фирмы "Ремингтон Рэнд". Они попытались использовать ЭВМ для составления планов-графиков крупных комплексов работ по модернизации заводов фирмы "Дюпон". В результате был создан рациональный и простой метод описания проекта с использованием ЭВМ. Первоначально он был назван методом Уолкера-Келли, а позже получил название метода критического пути -- МКП (или CPM -- Critical Path Method).

Параллельно и независимо в военно-морских силах США был создан метод анализа и оценки программ PERT (Program Evaluation and Review Technique). Данный метод был разработан корпорацией "Локхид" и консалтинговой фирмой "Буз, Аллен энд Гамильтон" для реализации проекта разработки ракетной системы "Поларис", который объединял около 3800 основных подрядчиков и состоящего из 60 тыс. операций. Использование метода PERT позволило руководству программы точно знать, что требуется делать в каждый момент времени и кто именно должен это делать, а также вероятность своевременного завершения отдельных операций. Проект удалось завершить на два года раньше запланированного срока благодаря успешному руководству программы.

Данный метод управления начал использоваться во всех вооруженных силах США для планирования проектов. Эта методика использовалась при координации работ, выполняемых различными подрядчиками в рамках крупных проектов по разработке новых видов вооружения.

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

Примером успешного применения сетевого планирования проектов можно назвать сооружение гидроэлектростанции на реке Черчилль в Ньюфаундленде (полуостров Лабрадор) с 1967 по 1976 г. В 1974 году ход работ по проекту опережал расписание на 18 месяцев и укладывался в плановую оценку затрат. Заказчиком проекта была корпорация Churchill Falls Labrador Corp., которая для разработки проекта и управления строительством наняла фирму Acress Canadian Betchel. Значительный выигрыш по времени образовался благодаря применению точных математических методов в управлении сложными комплексами работ, что стало возможным благодаря развитию вычислительной техники. Первые ЭВМ были дороги и доступны только крупным организациям. Таким образом, исторически первые проекты представляли собой грандиозные по масштабам работ, количеству исполнителей и капиталовложениям государственные программы.

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

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

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

Разработаны также несколько иные системы планирования и управления, коротко называемые «СПУ». В основе этих систем тоже лежат сетевые графики. Применяются и другие методы организационного управления, но системы «СПУ» получили наибольшее распространение. Системы «СПУ» были успешно применены, например, при сооружении ТЭЦ в Лисичанске, Буштырской тепловой электростанции, Челябинского блюминга-автомата «1300», при ремонте мартеновской печи завода «Серп и молот», при реконструкции доменной печи в «Запорожстали», при строительстве метромоста через Днепр в Киеве, комплекса жилых и общественных зданий на проспекте Калинина в Москве и т. д.

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

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

Конечно, системы «СПУ» не идеальны, они пока не дают возможности вести управление при одновременном учете всех параметров (и времени, и стоимости, и ресурсов, и технико-экономических показателей), тем не менее их методы являются весьма эффективными.

Методы «СПУ» отвечают потребностям тех, кто имеет дело с выполнением проектов или крупных комплексов работ. Это один из методов исследования операций, но он не требует никаких предварительных специальных знаний.

1.2 Сущность сетевого планирования и область его использования

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

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

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта.

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

Сетевое планирование и управление включает три основных этапа: структурное планирование, календарное планирование, оперативное управление.

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

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

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

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

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

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

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

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

1.3. Сетевой график

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

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

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

2. Геодезическая съемка местности.

3. Расчистка площадки для строительства.

4. Разработка проекта здания поликлиники.

5. Монтаж фундамента.

6. Рытье котлована для фундамента.

7. Кладка стен.

8. Внутренняя электропроводка.

9. Доставка на стройплощадку блоков подъемного крана.

10. Принятие решения о строительстве поликлиники.

11. Штукатурка стен.

12. Подвоз земли для прилежащего участка.

13. Окончательная уборка строительной площадки.

14. Подвоз оборудования.

15. Установка оборудования.

16. Окончательная уборка помещения.

17. Окраска стен.

18. Побелка потолков.

19. Прием поликлиники комиссией.

20. Монтирование подъемного крана.

21. Монтаж каркаса здания.

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

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

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

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

Все события на рисунке 3.2 обозначены разными числами.

Расшифровать их можно так: 0 — исходное событие, начало строительства; 1 — котлован подготовлен; 2 — монтаж фундамента закончен; 3 — металлоконструкции завезены; 4 — подъемный кран смонтирован.

Рис.3.1

Рис.3.2

Рис.3.3

Иногда для начала какой-то работы требуется завершение нескольких работ. Например, для начала монтажа требуется, чтобы был заложен фундамент, завезены металлоконструкции для каркаса здания и смонтирован подъемный кран. Эти работы выполняют разные люди, и завершиться они могут в разное время. Для отражения на сетевом графике очередности выполнения работ дополнительно используются штриховые стрелки (рис. 3.3). Штриховые стрелки отражают условную зависимость между событиями.

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

В основе построения сетевого графика лежат 3 основных понятия: работа, событие и путь.

Термин «работа» в сетевом планировании используется в широком смысле.

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

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

По количеству затрачиваемого времени работа может быть:

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

Под «событием» в сетевом планировании понимают:

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

Рис.3.4

Любая стрелка на сетевом графике соединяет только две вершины и отражает процесс перехода от одного события к другому. Поэтому любая работа может быть зашифрована парой чисел, соответствующих предшествующему и последующему событиям. Например, на рисунке 3.3 работу «Монтаж подъемного крана» можно зашифровать упорядоченной парой чисел: <0; 4>.

Время, необходимое для выполнения работы <i;j>, называют продолжительностью работы и обозначают t < i;j>. Обозначение проставляют над соответствующей стрелкой.

На рисунке 3.4 приведен сетевой график некоторого комплекса работ. Нaд стрелками проставлено время выполнения каждой из работ. Здесь t < 0; 1> = 10; t<3; 1> = 7; t<4; 7> = 10.

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

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

Глава 2.Применение на практике сетевого планирования

2.1. Построение сетевого графика

Прежде чем непосредственно приступать к построению сетевого графика, составляют список всех работ, необходимых для выполнения заданного комплекса работ. Далее выясняют технологическую последовательность их выполнения; строят отдельные фрагменты сетевого графика; по возможности их упрощают. После этого из отдельных фрагментов строят общий сетевой график. В таких случаях принято говорить о «сшивании сетевого графика». Т.е. сетевой график сложного проекта обычно составляют несколько групп специалистов, каждая из которых делает сетевой график своего участка. Процесс объединения нескольких сетевых графиков в один общий носит название «сшивание сетевого графика». В последнее время все чаще «сшивание сети» выполняют на ЭВМ по специально разработанным программам.

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

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

2. Для удобства сетевой график строят без лишних пересечений стрелок. (Вместе с тем при составлении чернового варианта не следует увлекаться внешним видом сети.)

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

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

5. Следят за тем, чтобы в сетевом графике не образовывалось циклов.

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

На рисунке 4.1 приведены неправильное и правильное изображения двух работ а и b, начинающихся после события 1; после завершения а и b начинается работа с.

На рисунке 4.2 приведены неправильное и правильное изображения трех работ а, Ь, с, начинающихся после события 1; после их завершения начинается работа d.

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

Рис.4.1

Рис.4.2

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

На рисунке 4.3 изображена часть сетевого графика. Здесь работа а разбита на 3 части a1 а2 и a3, причем после выполнения их начинается работа bl, после а2 — b2, после а3 — b3.

Рис.4.3

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

8. На сетевом графике следует четко отражать последовательность с выполнения отдельных работ и их взаимосвязи. В помощь вводятся штриховые стрелки (условные зависимости) и дополнительные вершины (события).

2.2. Критический путь

Пусть сетевой график некоторого проекта (комплекса работ) построен (рис. 5.1). Время выполнения отдельных работ измерено, например, в неделях. За какое время можно выполнить все работы?

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

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

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

В сетевом графике на рисунке 5.1 от исходного события 0 дособытия 7 ведут 3 пути. Обозначим их L1, L1, L3. Пусть L1 проходит через вершины 0, 1, 5, 7; L2 — через вершины 0, 3, 7; L3 — через вершины 0, 2, 4, 6, 7. Вычислим их продолжительность: t (L1) = 3+4+2 = 9; t (L2) = 5+6=11; t (L3) =1 + 2+2 + 3 = 8.

Рис.5.1

Сравнив t (L) для всех полных путей в сетевом графике на рисунке 8, убеждаемся, что продолжительность самого «неблагоприятного» пути равна 11 неделям. Соответствующий проект не может быть реализован меньше чем за 11 недель.

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

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

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

Рис.5.2

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

Рис.5.3

Рассмотрим сетевой график на рисунке 5.3. Разделим кружки, которыми обозначены события, на 3 сектора. В нижнем секторе будем проставлять номера событий (рис. 5.3). Начнем определять критический путь. Для каждого события i определим наиболее ранний из возможных сроков наступления, который обозначим tp (i). На сетевом графике tp (i) будем проставлять в левом секторе. Договоримся, что наиболее ранний срок наступления событий 0 обозначим нулем, то есть tp (0) = 0. Начнем последовательно рассматривать все вершины: tp (1) = 0 + 1, так как только один путь ведет от исходного события к событию 1; к событию 2 ведут два ребра <1;2>, <0; 2 > и L (2) = = max {(1 + 3); 5} = 5. Это означает, что наступление события 2 нельзя ожидать раньше чем через 5 (недель). К событию 3 тоже ведут два ребра <1; 3>, <2; 3> и tр(3)= -max {(1 + 2); (5 + 6)} =11.

Рис. 5.4

Это означает, что наступления события 3 нельзя ожидать раньше чем через 11 (недель) (рис. 5.4 ). Аналогично подсчитываем, что

tp (4)=max {(5+ 5); 11}= 11;

tp (5)=- max {(11 + 5); (11 + 3)} = 16.

Число 16 представляет собой время выполнения всего проекта (рис. 5.4). Путь, cоответствующий этому времени в 16 недель, получить нетрудно. Шаг за шагом восстановим тот путь, который определил ранний срок наступления завершающего события, равный 16.

От вершины 5 вернемся к той вершине, ребро из которой определило tp (5) = 16. Это ребро <3; 5>. От вершины 3 вернемся к той вершине, из которой выходит ребро, .определившее tp (3) = 11. Это ребро <2; 3>. От вершины 2 вернемся к той вершине, из которой выходит ребро, определившее tp (2) = 5. Это ребро <0; 2>. Все найденные ребра образуют критический путь. На рисунке 5.4 он обозначен жирными стрелками.

Работы <0; 2>, <2; 3>, <3; 5> являются критическими. Именно с этих работ нужно начинать после наступления соответствующих событий. Так, например, после наступления события 2 в первую очередь нужно начать работу <2; 3>. Если ее задержать, то это вызовет запаздывание выполнения всего проекта. запаздывание выполнения всего проекта. Некритические работы имеют некоторые резервы времени.

Выполнение, например, работы <4; 5> можно задержать при необходимости на 2 недели, если все остальные выполнены в срок.

Сформулируем общее правило определения tp (i).

1. tp(0)=0

2. tp (i) равно продолжительности наиболее «неблагоприятного» пути, ведущего от 0 к 1.

Как определить tp(t)? Для этого рассматривают все работы,непосредственно предшествующие событию L Для каждой из этих работ складывают ее продолжительность и ранний срок наступления события, непосредственно предшествующего этой работе; сравнивают эти суммы. Наибольшая из них определяет tp (i).

Заметим, что при этом определяют раннее окончание работ, непосредственно предшествующих событию i сравнивают их и находят наибольшее из них. Если раннее окончание работы <k; i> обозначить tp,0 <k; i>, то получим, что: tp(i) = max [tp,0 <k;i>]. 0<k<n

2.3. О резервах времени

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

Поздний срок наступления события — самый поздний срок наступления события, при котором планируемый срок окончания проекта не меняется.

Поздний срок наступления события i обозначим tn (i) и на сетевом графике будем проставлять в правом секторе. Заметим, что для завершающего события k поздний срок наступления совпадает с ранним сроком наступления, то есть tp (k) =tn(k).

Рис. 6.1

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

Рассмотрим три фрагмента сетевых графиков, предcтавленных на рисунке 6.1, и подсчитаем для каждого из них tn (4). (Заметим, что поздние сроки следующих событий уже известны и поставлены в правых секторах.)

На рисунке 6.1 а) за событием 4 следует работа t<4; 5>, причем t< 4; 5>=6.Это означает, что работа <4; 5> может начаться не позднее чем за 6 недель до события 5. Известно еще, что tn(5) = 15, следовательно, поздний срок свершения 4, события tn (4) = 15 — 6 = 9.

На рисунке 6.1 б) за событием 4 следуют две работы, причем t <4; 6> = 2 и t < 4; 7> = 3, Работа <4; 6> может начаться не позднее чем за 2 недели до события 6, а работа <4; 7> — не позднее чем за 3 недели до события 7. Так как tn (6) = 13, а tn (7) = 15, то поздний срок наступления события 4 равен наименьшей из разностей:

tn (4) = min [(13 — 2); (15 — 3)] = 11.

Если событие 4 наступит позднее, то работа <4; 6> не закончится на 13-й неделе; и это вызовет задержку наступления события 6.

На рисунке 6.1 (в) за событием 4 следуют три работы, причем t < 4; 6> = 10, t <4; 7> = 6 t<4;8> = 7. Работа <4; 6> может начаться не позднее чем за 10 недель до события 6; работа

<4; 7> — не позднее чем за 6 недель до события 7; работа <4;8> — не позднее чем за 7 недель до события 8. Так как tn (6) = 30, tn (7) = 32, a tn (8) = 28, то поздний срок наступления события 4 равен наименьшей из разностей:

tn (4) = min [(30 — 10); (32 — 6); (28 — 7)] = 20.

Следовательно, tn (4) = 20. Если событие 4 наступит позднее чем на 20-й неделе, то работа, <4; 6> не закончится на 30-й неделе, и это увеличит срок завершения всего комплекса.

Теперь нетрудно определить резервы времени для каждого из событий. Например, на рисунке 6.1 (б) событие 4 может произойти на отрезке времени 17; 11]; событие 6 — на отрезке [10; 13], событие 7 — на отрезке [10; 15], Время их наступления в этих интервалах не повлияет на срок выполнения всего комплекса.

Рис. 6.2

Определим поздние сроки наступления событий по сетевому графику на рисунке 6.2. В правый сектор завершающего события 5 поставим tn (5) = tp (5) = 16.

Рассмотрим теперь событие 4; t < 4; 5 > = 3, так что работа <4; 5> может начаться не позднее чем за 3 недели до события 5. Поздний срок наступления события 4 равняется 16 — 3=13. Поставим 13 в правый сектор соответствующей вершины на сетевом графике.

Событие 3 отделено от события 5 работой < 3; 5> и от события 4 работой <3; 4>, причем t<3; 5> = 5, t <3; 4> = 0. Работа <3; 5> может начаться не позднее чем за 5 недель до события 5, а работа <3;4>—фиктивная, но она показывает зависимость событий 3 и 4; а именно поздний срок наступления события 3 не может быть больше чем 13.

Таким образом, поздний срок наступления события 3 определяется наименьшей из разностей: 16 — 5 = 11 и 13 — 0 = 13.

Следовательно, tn(3) = 11. (Ставим 11 в правый сектор.)

Событие 2 отделено от события 4 работой < 2; 4 > и от события 3 работой <2; 3>. Выбираем наименьшую из разностей: tn(3) — t <2; 3>= 11 — 6 = 5; tn(3) — t < 2-, 4>-= 13 — 5 = 8. Следовательно, tn (2) = 5. Событие 2 должно наступить не позднее чем на 5-й неделе, так как иначе задержится общий срок завершения всего комплекса. (Ставим 5 в правый сектор.)

Аналогично определяем поздний срок наступления события 1:

tn(1) = min {[tn(3) — t< 1; 3>]; tn (2) — t< 1; 2>]} = min {[11 — 2]; [5 — 3]} = min {9; 2} = 2.

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

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

Подведем итоги.

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

1. Определить поздний срок наступления завершающего события. Если завершающее событие обозначено j, то tn(j) = tp(j).

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

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

2.4. Примеры использования сетевого графика при строительстве дома

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

Проект строительства дома
№	Операция	Время (дни)	Предшествующие операции	Дуга графа
1.	Расчистка участка	1	нет	1-2
2.	Закладка фундамента	4	Расчистка участка (1)	2-3
3.	Возведение стен	4	Закладка фундамента (2)	3-4
4.	Монтаж электропроводки	3	Возведение стен (3)	4-5
5.	Штукатурные работы	4	Монтаж электропроводки (4)	3-6
6.	Благоустройство территории	6	Возведение стен (3)	5-7
7.	Отделка	4	Штукатурные работы (5)
8.	Настил крыши	5	Возведение стен (3)	3-8

Рис.7.1

Две работы, соответствующие дуге 4-5, - параллельные, их можно либо заменить одной, представляющей совместную операцию (монтаж электропроводки и настил крыши), с новой длительностью 3+5=8, либо ввести на одной дуге фиктивное событие, например, событие ; тогда дуга 4-5 примет вид:

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

Рис. 7.2

Здесь введены два события: 0 - начало строительства дома, 9 - завершение (сдача) дома. Длительности a, b, c работ 7-9, 6-9, 8-9 должны быть определены.

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

Наиболее ранний срок наступления события j определяется как продолжительность самого длинного пути от начального события к конечному. Пусть tij - время, необходимое для выполнения работы (i,j), то есть работы по переходу от события i к событию j. Пусть от начального события (i=1) к j-му событию ведут k путей, которые мы обозначим через П1, П2, … ,Пк.. Продолжительность всех работ на пути Пs состоит из суммы продолжительностей, составляющих этот путь Пs работ:

s= 1,2,..., k, m=1, 2,...,n.

Пусть Tpj- наиболее ранний срок наступления события j, . Он определяется как самый длинный путь от первого узла (i=1) до j-го узла:

j=1,2,...,n. Максимум берется по всем путям Пs, соединяющим узлы 1 и j. Следовательно,

Максимум берется по всем работам, завершающимся в j-ом узле и выходящим из любого предшествующего i-го узла.

Пример2. Рассмотрим сетевой график, изображенный на рис. 7.3.

Рис. 7.3

Для этого сетевого графика получаем:

Пусть - наиболее поздний срок наступления i-го события, не отодвигающий время завершения всего проекта, то есть наиболее поздний срок завершения всех работ, ведущих к i-му узлу. Тогда ясно, что наиболее поздний срок наступления последнего события n (завершения проекта) необходимо положить равным наиболее раннему сроку завершения проекта. Это нужно для того, чтобы гарантировать, что самый длинный путь (критический) не будет требовать времени больше заданного времени завершения проекта. Следовательно, Tjn. Чтобы определить наиболее поздний срок наступления любого события i (i<n), необходимо делать просчет в обратном направлении. Пусть i-му событию предшествует ряд работ. Вычислим наиболее поздние сроки наступления всех событий, предшествующих i-му событию, и вычтем продолжительности работ, ведущих в i-ое событие. Тогда

Минимум берется по всем событиям, соединенным с i-ым событием.

Пример3. Для сетевого графика 7.3 имеем:

Таким образом, чтобы закончить этот проект в момент времени t=16, необходимо его начать в момент времени t=0.

Итак, - длина пути наибольшей длительности от события 1 к событию i, а - длина пути наибольшей длительности от события i к событию n. Эти длины определяются взятием максимума (минимума).

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

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

Наиболее поздний срок начала работы ij:

Полный (суммарный) резерв времени работы ij, которая не вызовет задержки окончания всего проекта:

Работа ij с Rij=0 находится на критическом пути.

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

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

Для примера (рис. 7.3), приведенного выше, получаем таблицу резервов времени.

Событие	Операция
1.	(1,2)	4-0-4=0	4-0-4=0	4-0-4=0
2.	(1,3)	7-0-3=4	5-0-3=2	5-0-3=2
3.	(1,4)	10-0-4=6	4-0-4=0	4-0-4=0
4.	(2,3)	7-4-1=2	5-4-1=0	5-4-1=0
5.	(2,5)	11-4-7=0	11-4-7=0	11-4-7=0
6.	(2,7)	16-4-8=4	16-4-8=4	16-4-8=4
7.	(3,5)	11-5-4=2	11-5-4=2	11-7-4=0
8.	(4,6)	12-4-2=6	12-4-2=6	12-10-2=0
9.	(5,6)	12-11-1=0	12-11-1=0	12-11-1=0
10.	(5,7)	16-11-3=2	16-11-3=2	16-11-3=2
11.	(6,7)	16-12-4=0	16-12-4=0	16-12-4=0

Заключение

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

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

Существуют различные методы сетевого планирования.

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

Итак, сетевая модель позволяет:

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

· составить обоснованный план выполнения комплекса работ, более эффективно по заданному критерию использовать ресурсы;

· проводить многовариантный анализ разных решений с целью улучшения плана;

· использовать для обработки больших массивов информации компьютеры и компьютерные системы.

Библиографический список

1. Андерсон, Джеймс А. «Дискретная математика и комбинаторика»: пер. с англ. - М.: Издательский дом «Вильямс», 2003. - 960с.

2. Березина Л. Ю. «Графы и их применение.» - М.: Просвещение, 1979.

3. Новиков С.А.» Дискретная математика для программистов» - СПб.: Питер, 2001. - 304с.

4. Оре о. « Графы и их применение». - М.: Мир,1973.

5. Уилсон Р. «Введение в теорию графов.» - М.: Мир, 1977.

6. Харари Ф. «Теория графов.» - М.: Мир, 1973.

1. Были описаны способы преобразования схем с помощью которых в ряде случаев удаётся упростить расчёт разветв
2. Как римская республика стала самым развитым государством Средиземноморья Провозглашение Римской респ
3. дейлиАльбурнинаш городок в провинции Салерно регион Кампания
4. а до одежных бельевых и декоративных.html
5. In recent yers one populr theory proposes tht climtic chnges cused the dinosurs to become extinct
6. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата біологічних наук Київ2000
7. Ключевые экономические проблемы российского здравоохранения Переход от бюджетной системы финансировани
8. Различные примеры социальной сферы инноваци
9. лекциях по работе в системе 1С-Предприятие 8
10. Контрольная работа По дисциплине Теория финансового менеджмента Вариант 1
11. Безопасность жизнедеятельности Исследование опасности электромагнитных полей радиочасто
12. терапия для детей Введение В настоящее время все большую популярность приобретают интегративные мето
13. профилактической помощи больным с патологией пародонта разработке и внедрению в практику методов и средств
14. Лизинг его виды
15. экономических показателей
16. Нормативное регулирование учета расчетов с бюджетом по налогам и сборам 4
17. ТЕМА ОЦЕНИВАНИЯ ДИСЦИПЛИНЫ
18. . Характеристика одного из финноугорских народов.
19. Культурные нормы и их соблюдение
20. Методы оценки управленческого персонала.html

Материалы собраны группой SamZan и находятся в свободном доступе

Будь умным!