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

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

Program Evaluation and Review Technique - техника оценки и анализа программ, которая используется при управлении проектами. Была разработана в 1958 году консалтинговой фирмой «Буз, Ален и Гамильтон» совместно с корпорацией «Локхид» по заказу Подразделения специальных проектов ВМС США в составе Министерства Обороны США для проекта создания ракетной системы «Поларис» (Polaris). Проект «Поларис» был ответом на кризис, наступивший после запуска Советским Союзом первого космического спутника.

Program Evaluation and Review Technique - это способ анализа задач, необходимых для выполнения проекта. В особенности, анализа времени, которое требуется для выполнения каждой отдельной задачи, а также определение минимального необходимого времени для выполнения всего проекта.

Program Evaluation and Review Technique был разработан в 50-ые годы главным образом для упрощения планирования и составления графиков больших и сложных проектов. Метод подразумевал наличие неопределённости, давая возможность разработать рабочий график проекта без точного знания деталей и необходимого времени для всех его составляющих.

Самая известная часть Program Evaluation and Review Technique - это «Сети PERT» - графики соединённых между собой временных линий. PERT предназначен для очень масштабных, единовременных, сложных, нерутинных проектов.

Диаграмма представляет собой множество точек-вершин вместе с соединяющими их ориентированными дугами. Каждая из них как направленный отрезок имеет начало и конец, причем модель содержит только одну из пары симметричных дуг (от вершины 1 к вершине 2 и от вершины 2 к вершине 1). Всякой дуге, рассматриваемой в качестве какой-то работы из числа нужных для осуществления проекта, приписываются определенные количественные характеристики. Это - объемы выделяемых на нее ресурсов и, соответственно, ее ожидаемая продолжительность (длина дуги). Любая вершина интерпретируется как событие завершения работ, представленных дугами, которые входят в нее, и одновременно начала работ, отображаемых дугами, исходящими оттуда. Таким образом, фиксируется что ни к одной из работ нельзя приступить прежде чем будут выполнены все предшествующие ей согласно технологии реализации проекта. Факт начала этого процесса - вершина без входящих, а окончание - без исходящих дуг. Остальные вершины должны иметь и те, и другие. Последовательность дуг, в которой конец каждой предшествующей совпадает с началом последующей, трактуется как путь от отправной вершины к завершающей, а сумма длин таких дуг - как его продолжительность. Обычно начало и конец реализации проекта связаны множеством путей, длины которых различаются. Наибольшая определяет длительность всего этого проекта, минимально возможную при зафиксированных характеристиках дуг графа. Соответствующий путь - критический и в каждый момент времени контролировать нужно состояние именно тех работ, которые «лежат» на нем.

Метод графической оценки и анализа (GERT, англ. Graphical Evaluation and Review Technique) - альтернативный вероятностный метод сетевого планирования, применяется в случаях организации работ, когда последующие задачи могут начинаться после завершения только некоторого числа из предшествующих задач, причём не все задачи, представленные на сетевой модели, должны быть выполнены для завершения проекта. Основу применения метода GERT составляет использование альтернативных сетей, называемых GERT-cетями. Они позволяют более адекватно задавать сложные процессы строительного производства в тех случаях, когда затруднительно или невозможно (по объективным причинам) однозначно определить, какие именно работы и в какой последовательности должны быть выполнены для достижения цели проекта (то есть существует многовариантность реализации проекта). Расчёт GERT-сетей, моделирующих реальные процессы, чрезвычайно сложен, однако программное обеспечение для вычисления сетевых моделей такого типа в настоящее время, к сожалению, не распространено.

Сетью называется конечный граф G(X,Y) , без циклов и петель, ориентированный в одном общем направлении от вершин V, являющимися входами графа, к вершинам W, являющимися выходами.

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

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

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

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

Полный перебор (или метод «грубой силы» от англ. brute force) - метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Перебор по всевозможным сочетаниям из k элементов по N, т.е. сначала алгоритм пытается представить V как один из элементов массива S, затем перебираются все возможные пары, затем все возможные тройки и т.д.

Полный перебор практически применим только в задачах малого размера. Напомним, что СПУ с n событиями требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! путей в несимметричной, а факториал, метод заключается в нахождении наикратчайшего расстояния путём выбора самого короткого (оптимального решения, т.е. min).

Чтобы проводить полный перебор в СПУ, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. предложенных для переборных алгоритмов решения других задач) – это перебор в лексикографическом порядке. При лексикографической форме записи последовательность перестановок P представляется в виде отдельных блоков по (n-1)! элементов в каждом. Если пронумеровать эти блоки от 0 до (n-1), то все перестановки блока j (j = 0, 1, …, n-1) будут начинаться с цифры (j+1).

Предложим перестановку из пяти элементов, обозначенных цифрами 1..5. Лексикографически первой перестановкой является 1-2-3-4-5, второй – 1-2-3-5-4, …, последней – 5-4-3-2-1. Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую.

Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее. Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1< Pi . Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj,j>i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию.

Оптимизация сетевого графика методом «время – стоимость». Оптимизация сетевого графика в зависимости от полноты решаемых задач может быть условно разделена на частную и комплексную. Видами частной оптимизации сетевого графика являются: минимизация времени выполнения комплекса работ при заданной его стоимости; минимизация стоимости комплекса работ при заданном времени выполнения проекта.

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

При использовании метода «время – стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа (i , j) характеризуется продолжительностью t (i , j), которая может находиться в пределах (1.1):

a (I , j) ≤ t (I , j) ≤ b (I , j),    (1.1)

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

b (i , j) - нормальная продолжительность выполнения работы (i , j).

При этом стоимость с (i , j) работы (i , j) заключена в границах от cmin (i , j) (при нормальной продолжительности работы) до cmax (i , j) (при экстренной продолжительности работы).

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

Δc (i , j) = .     (1.2)

Величина h (i , j), равная тангенсу угла а наклона аппроксимирующей прямой (рисунок 1.1), показывает затраты на ускорение.

Рисунок 1.1 – График

 

Работы (i , j) (по сравнению с нормальной продолжительностью) на единицу времени (1.3)

h (i , j) = tg α= .      (1.3)

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

C = ,               (1.4)

уменьшится на величину (1.5):

С = =    (1.5)

Для проведения частной оптимизации сетевого графика кроме продолжительности работ t (i , j), необходимо знать их граничные значения a (i , j) и b (i , j), а также показатели затрат на ускорение работ h (i , j), вычисляемые по формуле (3). Продолжительность каждой работы t(i , j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени Rc (i , j).

 

1.3 Применение сетевого планирования и управления в экономике

 

При анализе возможностей применения СПУ на современном этапе развития экономики целесообразно отметить особенности применения сетевых моделей в централизованной и рыночной экономиках. При централизованных методах планирования и управления (до 90-х годов прошлого столетия) СПУ находит широкое применение в нашей стране. В значительной степени активное применение СПУ в централизованной экономике было обусловлено тем, что планирование и прогнозирование осуществлялось на государственном уровне. Естественно, что оно являлось широко масштабным и требовало системного подхода, базирующегося на теории сложных систем. Для решения народно-хозяйственных задач СПУ являлось адекватным подходом к анализу задач, связанных с планированием и управлением сложными объектами. Однако при этом недостаточно учитывались интересы хозяйствующих субъектов. Соответственно, ограниченное применение указанные подходы СПУ имели на промышленных предприятиях. Наибольшую популярность методы сетевого планирования и управления приобрели в 60-е, 70-е годы прошлого века. В дальнейшем интерес к этим методам существенно снизился. В экономической литературе отмечается, что последние годы волна массового интереса к применению сетевых моделей при планировании и управлении производством прошла. Это относиться в целом к проблеме планирования и управления промышленными предприятиями при переходе к рыночным методам хозяйствования.

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

 

 

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

 

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

 

Для постановки задач необходимы такие условия:

1. должно существовать точно определяемое количество операций;
2. наличие точно определяемого множества операций, которые надо выполнить для завершения всего комплекса, включающего эти операции как свои составляющие;
3. множество операций комплекса (проекта) упорядочено так, что для каждой из них известно, какие операции непосредственно ей предшествуют, а которые непосредственно следуют за ней;
4. в пределах заданного отношения упорядочения операции можно начинать и заканчивать независимо одну от другой;

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

Разберём нахождение оптимизации сетевой модели на примере.

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

 

Таблица 2.1 – Игрушки, которые должна производить каждая фабрика

Фабрика	Тип игрушки
1	1, 2, 3
2	2, 3
3	1, 4
4	3, 4

 

 

Ежедневные производственные возможности фабрик составляют 250, 180, 300 и 100 штук игрушек соответственно. Ежедневный спрос на игрушки четырех типов составляет 200, 150, 350 и 100 штук. Разработайте производственный план, максимально удовлетворяющий спрос на игрушки.

Решение. Чтобы найти оптимальное решение задачи, нужно составить задачу, как сетевую.