Технология построения сетевого графика

ЗАДАНИЕ №3. Оптимизация сетевой модели комплекса производственных работ

1. Потребность в сетевом планировании и управлении (СПУ), возможности СПУ, цель и задачи работы.

2. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА – определение понятия «сетевой график» и технологии его построения, описание построения заданного сетевого графика, анализ адекватности построенного сетевого графика заданным в работе исходным условиям (данным).

3. АНАЛИЗ СЕТЕВОГО ГРАФИКА – определение понятий «полный путь» и «критический путь», описание нахождения полных путей построенного сетевого графика и среди них – критического, анализ возможности доведения критического срока до заданной продолжительности выполнения рассматриваемого комплекса производственных работ.

4. ОПТИМИЗАЦИЯ СЕТЕВОГО ГРАФИКА – определение понятий «оптимизация сетевого графика», «критерий оптимизации», «показатель оптимизации и условия оптимизации», постановка задачи оптимизации сетевого графика, выбор способов оптимизации, описание процедур оптимизации выбранными способами, сравнение результатов оптимизации разными способами, вывод об оптимальном результате для построенного сетевого графика.

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

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

Впервые сетевое планирование и управление было применено в США в конце 50-х годов и получило свое первоначальное название как метод критического пути (СРМ — Critical Path Method). С тех пор появилось много модификаций сетевого планирования и управления: PERT, PEANNET, COMET, RAMPS и т.д.

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

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

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

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

Предметом исследования данной части курсовой работы является сетевое планирование и управление, а объектом сетевая модель. Целью работы является оптимизация сетевой модели.

Основными задачами на данном этапе выполнения курсовой работы является:

1. Теоретическое изучение сетевого планирования и управление, определение его сущности изучение основных элементов сетевой модели построения сетевого графика, анализ адекватности построенного сетевого графика заданный в работе исходными данными.

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

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

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

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

Основы теории графов

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

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

Рисунок 4- Граф.

Петля – это дуга, начальная и конечная вершина которой совпадают.

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

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.

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

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

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

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

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

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

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

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

Анализ сетевого графика

Основные понятия оптимизации сетевого графика

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

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

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

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

Чаще всего сетевые графики сначала оптимизируются по параметру «время», без учета ограничений, а по достижении заданного срока приступают к корректированию распределения ресурсов.

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

• Время – трудовые ресурсы;

• Время – материальные ресурсы;

• Время – денежные затраты.

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

Существует несколько путей оптимизации сетевых графиков по времени:

• Увеличение численности персонала при выполнении работ критического пути за счет использования ресурсов работ некритической зоны, располагающих резервами времени;

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

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

• Разработка мер по разделению некоторых работ на более мелкие процессы, по которым возможно параллельное выполнение;

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

ЗАДАНИЕ №3. Оптимизация сетевой модели комплекса производственных работ

1. Потребность в сетевом планировании и управлении (СПУ), возможности СПУ, цель и задачи работы.

2. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА – определение понятия «сетевой график» и технологии его построения, описание построения заданного сетевого графика, анализ адекватности построенного сетевого графика заданным в работе исходным условиям (данным).

3. АНАЛИЗ СЕТЕВОГО ГРАФИКА – определение понятий «полный путь» и «критический путь», описание нахождения полных путей построенного сетевого графика и среди них – критического, анализ возможности доведения критического срока до заданной продолжительности выполнения рассматриваемого комплекса производственных работ.

4. ОПТИМИЗАЦИЯ СЕТЕВОГО ГРАФИКА – определение понятий «оптимизация сетевого графика», «критерий оптимизации», «показатель оптимизации и условия оптимизации», постановка задачи оптимизации сетевого графика, выбор способов оптимизации, описание процедур оптимизации выбранными способами, сравнение результатов оптимизации разными способами, вывод об оптимальном результате для построенного сетевого графика.

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

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

Впервые сетевое планирование и управление было применено в США в конце 50-х годов и получило свое первоначальное название как метод критического пути (СРМ — Critical Path Method). С тех пор появилось много модификаций сетевого планирования и управления: PERT, PEANNET, COMET, RAMPS и т.д.

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

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

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

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

Предметом исследования данной части курсовой работы является сетевое планирование и управление, а объектом сетевая модель. Целью работы является оптимизация сетевой модели.

Основными задачами на данном этапе выполнения курсовой работы является:

1. Теоретическое изучение сетевого планирования и управление, определение его сущности изучение основных элементов сетевой модели построения сетевого графика, анализ адекватности построенного сетевого графика заданный в работе исходными данными.

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

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

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

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

Основы теории графов

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

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

Рисунок 4- Граф.

Петля – это дуга, начальная и конечная вершина которой совпадают.

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

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.

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

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

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

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

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

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

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

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

Технология построения сетевого графика

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

При построении сетевого графика необходимо следовать следующим правилам:

1. график должен иметь только одно начальное событие (исток) и только одно конечное событие (сток);

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

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

4. график должен быть упорядоченным.

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

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