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

Анализ и оптимизация сетевого графика.

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

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

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

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

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

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

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

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

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

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

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

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

Например, можно увеличить сменность работ на «узких» участках строительства. Это мероприятие наиболее эффективно, поскольку позволяет добиться нужного результата при тех же ведущих машинах (экскаваторе, станке и т.д.), только увеличив численность рабочих.

сокращением трудоёмкости критических работ за счёт передачи части работ на другие пути, имеющие резервы времени;

пересмотром топологии сети, изменением состава работ и структуры сети.

обеспечить проведение параллельных (совмещенных) работ;

разделить широкий фронт работ на более мелкие захватки или участки;

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

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

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

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

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

При использовании метода «время–стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию её стоимости. Возрастание стоимости при уменьшении времени называется затратами на ускорение.

Весьма эффективным является использование метода статистического моделирования, основанного на многократных последовательных изменениях продолжительности работ (в заданных пределах) и «проигрывании» на компьютере различных вариантов сетевого графика с расчётами всех его временных параметров и коэффициентов напряжённости работ.

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

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

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

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

studfiles.net

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

Количество просмотров публикации Оптимизация сетевого графика - 461

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

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

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

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

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

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

Оптимизация сетевого графика включает следующие этапы:

1. Определяется объём ненапряженной работы (чел-дней), с которой предполагается перевести часть исполнителей на работу критического пути по формуле:

, (9.20)

где – продолжительность работы в днях;

– количество исполнителей на данной работе.

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

, (9.21)

где – частный резерв времени работы.

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

. (9.22)

4. Определяется объём работы критического пути, на которую предполагается перевести часть исполнителей, по формуле:

. (9.23)

5. Определяется продолжительность работы критического пути после увеличения численности исполнителей на этой работе, по формуле:

. (9.24)

6. Определяется продолжительность критического пути после оптимизации сетевого графика.

Пример. Разработать и оптимизировать сетевой график по технологической подготовке производства нового изделия, согласно приведенным данным в табл. 9.1.

Таблица 9.1.

№	Наименование работ	Код работы	Продолжительность работы, дни	Количество исполнителей	Специальность

1.	Отработка конструкции на технологичность	1-2			Технолог
2.	Разработка технологии кузнечно-штамповочного производства	2-3			Технолог
3.	Разработка технологии литейного производства	2-4			Технолог
4.	Разработка технологии механической обработки	2-5			Технолог
5.	Разработка технологии сборки	3-4			Технолог
6.	Проектирование кузнечной оснастки	3-6			Конструктор
7.	Проектирование литейной оснастки	4-6			Конструктор
8.	Фиктивная работа	5-6			–
9.	Проектирование оснастки для механической обработки	6-7			Конструктор

По приведенным данным строится сетевой график технологической подготовки производства (рис. 9.3).

Расчет базовых параметров сетевого графика сводим в таблицу 9.2.

Таблица 14.2.

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

Частными резервами времени располагают работы: , , . Работа является фиктивной, в связи с этим для оптимизации сетевого графика не принимается.

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

Коэффициент напряженности для данного пути составит:

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

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

Оптимизацию сетевого графика проводим в следующей последовательности:

1. Определяем объём работы :

2. Определяем оптимальную численность исполнителей на данной работе:

3. Определяем количество исполнителей, которых можно перевести на работу критического пути:

4. Определяем объём работы на критическом пути:

5. Определяем продолжительность работы после увеличения численности исполнителей на ней:

6. Определяем продолжительность критического пути после оптимизации сетевого графика:

Проверяем продолжительность пути после оптимизации:

Коэффициент напряженности работ данного пути после оптимизации составит:

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

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, проведя оптимизацию сетевого графика, продолжительность технологической подготовки производства нового изделия сократилась с 28 до 26,5 дня, т. е. на 1,5 дня.

referatwork.ru

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

Количество просмотров публикации Оптимизация сетевого графика - 179

Задача коммивояжера

Элементы теории графов

Транспортных объектах.

Методы и модели теории графов и сетевого моделирования на

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

Граф– совокупность вершин и ребер – универсальное средство наглядного представления достаточно разнообразных задач.

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

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

Каждую вершину сети нумеруют порядковым номером. Начальную 1 вершину в описании движения потоков называют источником, конечную – стоком. В общем случае дугу обозначают i-j, где i – номер вершины, из которой исходит дуга; j – номер вершины, в которую входит дуга. Каждая дуга имеет свою характеристику: tij – продолжительность движения по дуге i-j; cij – стоимость перемещения; dij – пропускная способность дуги и т.д.

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

Пример. Размещено на реф.рфПусть имеются 5 пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (рис.1). Известно время перевозки из пункта i в пункт j (табл.1).

Рисунок 1.

Таблица 1.

Из пункта i	В пункт j

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

Решение. Для решения этой задачи крайне важно составить математическую модель. Введем обозначения: i и j – номера пунктов выезда и въезда; tij – время переезда из пункта i в пункт j. Из таблицы 1 видно, что tij в общем случае должна быть не равно времени переезда в обратном направлении tijtji (к примеру, когда один пункт на вершине горы, а другой – у ее подножия). Введем булевые переменные:

1, в случае если из пункта i торговец переедет в пункт j

= 0, в случае если не поедет.

Составим модель. Из пункта 1 можно выехать в любой из пунктов 2 или 5, или 3, или 4, или остаться в пункте 1. Но при этом можно выехать только в одном единственном направлении. Это условие можно записать так:

, или ,

или для произвольного i-ого пункта

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

Условие въезда в пункт 1 аналогично условию выезда из пункта 1. Требование минимальной продолжительности маршрута запишется в виде целевой функции:

где tij берутся из исходной таблицы 1, а - искомые переменные.

Тогда всю задачу можно сформулировать:

, (*)

= [0;1] .

В результате решения системы (*) получим (рис.2) следующие значения , остальные ; min L = 10+8+10+20+14=62.

Рисунок 2.

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

, (*)

= [0;1] .

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

Первые методы СПУ: метод оценки и проверки планов (PERT) и метод критического пути (CPM) были разработаны в 1950-х гᴦ. для управления сложными проектами. CPM появился в 1957 ᴦ. для организации строительства и ремонта химических заводов Дюпона. PERT разрабатывался независимо для нужд военно-морского флота и появился в 1958 ᴦ. В дальнейшем сетевые методы стали широко применяться и во всех отраслях экономики.

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

Система СПУ позволяет:

· формировать календарный план реализации некоторого комплекса работ;

· выявлять и мобилизовать резервы времени, трудовых, материальных и финансовых ресурсов;

· осуществлять управление комплексом работ по принципу ʼʼведущего звенаʼʼ с прогнозированием и предупреждением возможных срывов в ходе работ;

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

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

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

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

Сетевая модель и ее основные элементы

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

Главными элементами сетевой модели являются события и работы.

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

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

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

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

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

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

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

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

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

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

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

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

Основные временные параметры сетевых графиков представлены в табл.2.

referatwork.ru