Метод сетевого планирования

Введение

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

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

­    строительство и реконструкция каких-либо объектов;

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

­    подготовка производства к выпуску продукции;

­    перевооружение армии;

­    развертывание системы медицинских или профилактических мероприятий.

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

СПУ состоит из трех основных этапов.

. Структурное планирование.

. Календарное планирование.

. Оперативное управление.

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

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

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

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

Для достижения цели необходимо решить задачи:

·          построить сетевой график, согласно необходимому списку работ;

·          определить все пути от начального события до конечного;

·          выполнить оптимизацию сетевого графика.

1. Постановка задачи

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

Таблица 2.1

2. Порядок выполнения

По данным таблицы строим сетевой график (Рис. 2.1). Изобразим в виде графа последовательность работ.

Рис. 2.1

Составим таблицу (Таблица 2.1).

Таблица 2.1

Определим ранние и поздние сроки свершения работ. Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика (Рис. 2.2).

Рис. 2.2. Отображение временных параметров событий на сетевом графике

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

для исходного события И Т_р (И) = 0:

для всех остальных событий i:

где максимум берется по всем работам (k, i), входящим в событие i: t (k.i) - длительность работы (k, i) (Рис. 2.3).

Рис. 2.3. Расчет раннего срока T_p(i) свершения события i

Поздние сроки свершения событий T_п(i) рассчитываются от завершающего к исходному событию:

для завершающего события 3: Т_п(3) = Т_р(3);

для всех остальных событий:

где минимум берется по всем работам (i, j), выходящим из события i; t (k, i) - длительность работы (k, i) (Рис. 2.4).

Рис. 2.4. Расчет позднего срока Tn(i) свершения события i

Временные параметры работ определяются на основе ранних и поздних сроков событии:

Т_рн(i, j) = T_p(i) - ранний срок начала работы:_pо(i, j) =T_p(i) + t (i, j) - ранний срок окончания работы;_пo(i, j) = T_п(j) - поздний срок окончания работы;

Т_пн(i, j) = Т_п(j) - t (i, j) - поздний срок начала работы:_п(i, j) =T_п(j) - T_p(i) - t (i, j) - полный резерв работы показывает максимальное время, на которое можно увеличить длительность работы (i, j) или отсрочить ее начало, чтобы не нарушился срок завершения проекта в целом;_c(i, j) = T_p(j) - T_p(i) - t (i, j) - свободный резерв работы показывает максимальное время, на которое можно увеличить продолжительность работы (i, j) или отсрочить ее начало, не меняя ранних сроков начала последующих работ.

Сетевой график согласно принятым обозначениям представлен на рисунке (Рис. 2.5).

Определим резервы времени по формулам и заполним таблицу (Таблица 2.2).

Таблица 2.2

Найдем критический путь. Критический путь - путь максимальной длины. Двигаясь в обратном направлении от конечной вершины 8 в начальную 0, и, выбирая на каждом шагу событие i с максимальным временем T_p(i)+t (i, j) (Рис. 2.6), получим два критических пути:

-1-3-5-2-7-8 длиной 30 и включающий работы -----;

-1-3-5-6-7-8 длиной 30 и включающий работы -----;

Выпишем все пути и определим их длительность:

,

,

,

,

Проведем оптимизацию по критерию времени.

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

Расположим длительности всех путей в порядке увеличения: .

Выберем ближайший по длительности путь к критическому - это будет путь , . На этом пути работа  (4-6) имеет свободный резерв равный 3. Условие допустимости решения:

.

Перенесем часть средств на работу критического пути  (0-1):

Следовательно, новые длительности работ:

.

Длительность нового критического пути:

.

Далее, рассмотрим путь ,  с работой  (0-2), имеющей свободный резерв равный 9. Условие допустимости решения:

Перенесем часть средств на работы критического пути  и :

Разделим второе уравнение на 3,4, а третье на -2,8, а затем сложим:

Новые длительности работ:

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

Экономия составила: 30-28=2.

Заключение

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

сетевой модель критический путь

Список литературы

1.   Теория массового обслуживания. Методические указания, учебная программа и задания для контрольных работ №1, 2 для студентов заочной формы обучения специальности 071900 «Информационные системы в технике и технологиях». - Самара: СамГАПС, 2002. - 38 с.

2.      Экономико-математические модели и методы: Учеб. пособие для студ. экон. спец. БГУИР всех форм обуч. / С.А. Поттосина, В.А. Журавлев. - Мн.: БГУИР, 2003. - 94 с.

.        Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2005. - 616 с.