Продолжительность критического пути характеризует минимально возможное время выполнения всего комплекса работ.
Экономико-математические модели и методы, используемые
при решении комплекса задач сетевого планирования и управления
В отечественной практике логистики задачи согласования, как класс задач исследования операций, имеют специальное название - сетевое планирование и управление (СПУ), определяющее методы представления и решения указанных задач (методы СПУ).
В этих задачах исследуются процессы, состоящие из комплекса взаимосвязанных работ (операций, событий, экспериментов и т.п.), четко разграниченных по продолжительности выполнения, по ресурсам, затрачиваемым на работы, а также по месту выполнения с целью оценки ожидаемого развития процесса во времени и выявления работ, наиболее важных с точки зрения сроков завершения всего процесса в целом. В ряде случаев решаются также задачи учета используемых ресурсов и сокращения стоимости работ.
По способу оценки времени выполнения работ (операций) задачи согласования делятся на детерминированные и вероятностные (стохастические). Если продолжительность работы предполагается точно известной и неизменной, то имеем детерминированную задачу согласования, в противоположном случае – вероятностную. В детерминированных задачах не учитываются случайные изменения продолжительности работы, которые могут оказывать существенное влияние на срок завершения всего процесса в целом.
Отображение процесса разработки, принятия и реализации управленческого решения; процесса перевозки грузов; экономического процесса; строительства большого объекта; процесса разработки сложной научной проблемы, элементов экономической системы, экономического проекта; процесса выполнения задания (проекта) и т.д. в виде сетевых графов - достаточно распространенный прием моделирования систем такого рода.
Сетевое моделирование является одним из наиболее мощных методов графического моделирования организационных и технологических процессов. Сетевая модель изображается в виде графа, которым может быть представлен любой комплекс взаимосвязанных работ: научных, конструкторских, управленческих и т.д.
Модели СПУ разрабатываются как модели параллельно-последовательного принятия решений, в которых в момент принятия очередного решения используются не только плановые данные, но и сведения о фактическом состоянии управляемых процессов (объектов). Это обусловлено необходимостью многократного принятия решений в меняющихся условиях, что является отличительной чертой задач, реализуемых с помощью методов СПУ.
Методы сетевого планирования и управления представляют собой один из разделов теории управления большими системами и предназначены для планирования и управления производственно-экономическими системами. Планирование и реализация функции управления осуществляются с помощью сетевых моделей, которые являются одним из классов экономико-математических моделей.
Методы СПУ позволяют формировать оптимальные по выбранным критериям планы и осуществлять оптимальное управление.
В данном учебнике углубляется теоретико-практический аспект применения аппарата экономико-математического моделирования на сетевых графах.
Данная глава содержит компактное изложение основных вопросов, относящихся к построению и анализу детерминированных сетевых моделей.
Основные понятия сетевых моделей в терминах работ и событий
Поясним основные расчетные процедуры и понятия сетевых графов, графиков и моделей в терминах работ и событий.
Сетевой граф по внешнему виду есть конечный ориентированный граф без контуров, вершины которого отображают события, а дуги - элементарные операции, или работы. Сетевой граф не обладает размерностью, он только отражает технологический процесс достижения промежуточных и конечной целей.
Сетевой график (СГ) - это формальное отображение комплекса взаимосвязанных работ ориентированным конечным связанным сетевым графом (отображающим отношения предшествования), на котором заданы количественные параметры (прежде всего временные параметры).
Сетевой график дает наглядную и понятную картину последовательности выполнения работ по реализации проекта (комплекса работ). Помимо того, что такие графики показывают начало и окончание каждой работы (операции), они четко указывают на очередность выполнения работ (операций), а также показывают резервы времени, которыми обладают работы, не лежащие на критическом пути. На нем наглядно видны последствия запаздывания в выполнении любой работы с точки зрения времени реализации всего комплекса работ (проекта). Таким образом, СГ представляет цепи работ (операций) и событий, отражая их технологическую последовательность и связь в процессе достижения промежуточных и конечной цели. Он позволяет наглядно изобразить логическую и временную структуру сложного комплекса взаимосвязанных работ и предоставляет возможность эффективно планировать, контролировать ход выполнения проекта – управлять проектом.
Сетевая модель - это полная графическая модель комплекса работ, направленных на достижение конечной цели (выполнение единого задания, проекта), в которой определяются логическая взаимосвязь событий (подцелей), последовательность работ (операций) и взаимосвязи между ними во времени, а также вся совокупность количественных параметров.
Сетевые модели позволяют наглядно устанавливать взаимосвязи работ и событий, анализировать состояние процесса в каждый заданный момент времени и оптимизировать комплекс работ, то есть дают возможность получать комплексные оценки отображаемых ими систем (объектов планирования и управления), раскрывая механизм их работы. Анализируя сетевые модели и экспериментируя с ними, обычно удается определить, как влияют изменения в рассматриваемой системе на конечный результат ее функционирования (в том числе с целью прогнозирования, планирования поведения системы и разработки, принятия адекватных эффективных управленческих решений). Последнее особенно важно, поскольку исключает необходимость проведения эксперимента на самой системе, что либо вообще невозможно, либо сопряжено с чрезмерными затратами.
Сетевая модель может быть представлена в виде формализованных зависимостей, в табличном виде или в виде сетевого графика, то есть схемы, на которой в строго определенном порядке отображен весь комплекс процедур (работ, операций), обеспечивающих достижение конечной цели, с соответствующими количественными и качественными характеристиками.
Сетевые модели разделяются (классифицируются) по характеру и количеству поставленных целей на одноцелевые и многоцелевые, по степени определенности тех или иных параметров - на детерминированные и стохастические (вероятностные), по количеству учитываемых критериев оптимальности - на однокритериальные и многокритериальные, по виду управляемых ресурсов - на временные, стоимостные и ресурсные (материальные), по количеству сетей, из которых строятся модели, - на односетевые и многосетевые, по степени огрубления структуры объекта исследования - на детализированные и агрегированные, по характеру функционирования - на модели единичного и постоянного действия, по степени формализации и автоматизации - на неавтоматизированные и автоматизированные, по типу объединения работ - на построенные по схеме “И”, по схеме “ИЛИ” и на комбинированные - по схеме “И-ИЛИ”.
Основными элементами сетевого графика являются работа (изображается стрелкой - квазивектором), событие (изображается кружком) и путь.
Работа - это любой трудовой процесс, характеризующийся затратами времени и ресурсов (например, сборка узла, изготовление детали, проектирование машины, какого-либо из ее узлов, разработка плана производства и т.п.) или только времени - старение, то есть процесс или действие, которое нужно совершить, чтобы перейти от одного события к другому. Работа на графике изображается сплошной линией со стрелкой (®). К этому понятию примыкает понятие “зависимость” или “фиктивная работа”. Оно выражает только связь, зависимость отдельных работ и характеризует тот случай, когда для начала данной работы требуется завершение одной или нескольких работ (непосредственно предшествующих данной), причем эту связь работ нельзя выразить ни через временные, ни через какие-либо другие ресурсные затраты, так как этих затрат нет. На графике эта связь изображается пунктирной линией со стрелкой (- - ®). Фиктивная работа представляет собой логическую связь между событиями и показывает зависимость начала выполнения какой-либо работы или совокупности работ от результатов выполнения другой или других и выполняется мгновенно.
Событие - это промежуточный или окончательный результат выполнения одной или нескольких работ или всего комплекса работ. В первом случае такое событие представляет собой результат, необходимый для начала каких-либо других работ; во втором случае момент наступления события будет характеризовать достижение промежуточной цели; в последнем - момент наступления события будет характеризовать достижение конечной цели. Если событие является результатом выполнения нескольких работ, то оно считается свершившимся только при завершении всех этих работ. События в сети совершаются мгновенно без затрат времени и ресурсов, на графике они отображаются окружностями. Таким образом, событие - это фиксированный момент времени, который представляет собой одновременно окончание предыдущей работы (работ), то есть ее результат (исключение - исходное событие СГ) и начало непосредственно следующей работы или последующих работ (исключение - завершающее событие СГ). События могут быть пронумерованы, номер события проставляется внутри окружности.
Для формирования сетевого графа большое значение имеет определение взаимосвязей работ и событий, в частности, установление их непосредственного предшествования и непосредственного следования. Так, работами, непосредственно предшествующими данной, являются работы, входящие в событие, из которого выходит данная работа. При этом начальное (исходное) событие сетевого графа не имеет входящих в него работ, поэтому работы, выходящие из этого события, не имеют непосредственно предшествующих. Непосредственно следующие за данной или данными работами называются работы, выходящие из события, в которое входят рассматриваемые работы. Для начала непосредственно следующей работы необходимо завершение всех непосредственно предшествующих. Из конечного (завершающего) события сетевого графа не выходит ни одна работа, поэтому у работ, входящих в это событие, не будет ни одной непосредственно следующей работы.
Путь - это набор (последовательность) работ, выполняемых непрерывно в строгой последовательности от начального (исходного) события до любого промежуточного или конечного (завершающего) события (полный путь). Длина пути определяется суммой продолжительностей лежащих на нем работ. В зависимости от того, какое из событий сетевого графа является начальным (исходное или промежуточное) и какое из событий является последним (промежуточное или завершающее) в рассматриваемом пути, различают укороченный или полный путь. Путь от начального (исходного) до конечного (завершающего) события СГ называется полным. Путь от исходного события до данного называется предшествующим данному событию, а от данного события до завершающего называется последующим за данным событием. Наиболее продолжительный из всех полных путей сетевого графа называется критическим, а лежащие на нем работы – критическими. Эти работы определяют потенциально узкие места. Сетевой граф, в зависимости от его топологии, может иметь несколько критических путей.
Продолжительность критического пути характеризует минимально возможное время выполнения всего комплекса работ.
При построении сетевых графиков необходимо соблюдать определенные правила. Основными из них являются: простая, по возможности, форма представления, в частности, исключение или минимизация пересечений работ; необходимость однозначного определения каждой работы одной парой событий - начальным и конечным; сетевой граф может иметь только одно исходное и одно завершающее события; запрещение зацикливания работ и т. д.
Код работы определяется как номер ее начального и номер ее конечного события. Номер начального события работы должен быть меньше номера ее конечного события.
Для правильной нумерации событий сетевого графа и соответственно кодировки его работ можно использовать следующий алгоритм.
1 шаг. Просматривается весь сетевой граф и выбирается событие, в которое не входит ни одна работа. Следовательно, это событие является исходным событием сетевого графа и ему присваивается номер 1.
2 шаг. Исключаются из дальнейшего рассмотрения работы, которые выходят из пронумерованного события.
3 шаг. Просматривается оставшаяся часть сетевого графа и выбирается событие, в которое не входит ни одна из оставшихся работ. Этому событию сетевого графа присваивается следующий по порядку номер из натурального ряда чисел. Если таких событий окажется два или более, то выбирается любое из них, например, расположенное левее (или выше).
4 шаг. Если остались непронумерованные события сетевого графа, то перейти к шагу 2, иначе процедура нумерации закончена.
Сетевое планирование и управление – система, применяемая в управлении крупными комплексами работ (процессами создания (проектирования, строительства) любых систем - управление проектами; научно-техническими разработками и другими комплексами работ), основанная на использовании сетевых графиков и компьютеров (современных телекоммуникационных, компьютерных информационных технологий и систем); графоаналитический метод планирования и управления.
Примерами видов СПУ являются моделирование на основе методов и средств PERT (Program Evolution Review Technique)-сетей и CPM (Critical Path Method) - метода критического пути.
Под системой сетевого планирования и управления следует понимать комплекс экономико-математических моделей и методов, технических и программных средств, организационных мероприятий, предназначенных для повышения эффективности планирования и управления производственно-экономическими и логистическими системами.
Система сетевого планирования и управления – система организационного управления, реализующая функции планирования, контроля и оперативного управления комплексами работ на основе построения, анализа, оптимизации и актуализации особого класса экономико-математических моделей, называемых сетевыми моделями (сетевыми графиками).
Комплекс задач сетевого планирования и управления включает в себя следующие подкомплексы задач:
- построение сетевого графа, нумерация событий и кодировка его работ;
- расчет временных параметров сетевого графика;
- установление возможности выполнения задания (проекта) в определенный срок, то есть оценка реализуемости проекта в течение фиксированного отрезка времени (директивный срок);
- оптимизация сетевого графика по временным параметрам;
- оптимизация сетевого графика по стоимости работ;
- оптимизация сетевого графика по ресурсам;
- привязка сетевого графика к календарю;
- формирование расписаний выполнения работ сетевого графика (рассматриваемого комплекса работ - проекта);
- формирование графиков загрузки ресурсов для рассматриваемого комплекса работ (проекта);
- анализ состояния процесса в каждый заданный момент времени;
- другие задачи.