Виды оптимизации сетевых моделей

3.4. Оптимизация сетевой модели

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

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

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

1) минимизация продолжительности выполнения разработки при заданной стоимости;

2) минимизация стоимости при заданной продолжительности.

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

Краткая характеристика метода оптимизации

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

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

Оптимизацию следует осуществлять путем направленной корректировки последовательными «шагами» (итерациями). Шаги корректировки заключаются в последовательном сокращении сроков выполнения отдельных работ при минимальном увеличении их стоимости.

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

Затем переходят к выполнению первой итерации.

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

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

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

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

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

Источник

Виды и сущность оптимизации сетевых моделей

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

6.1 Оптимизация проекта по времени. Пусть задан срок выполнения проекта t₀, а расчетное t_кр > t₀. В этом случае оптимизация комплекса работ сводится к сокра­щению продолжительности критического пути, которое может быть осуществлено либо за счет перераспределения внутрен­них резервов, либо за счет привлечения дополнительных средств.

Сокращение времени завершения проекта, как правило, связано с привлечением дополнительных средств (количес­тво рабочих, сверхурочное время). Рассмотрим два примера постановки задачи оптимизации проекта по времени с при­влечением дополнительных средств.

Задача 1 заключается в определении величины дополнитель­ных вложений х_ij в отдельные работы проекта с тем, чтобы общий срок его выполнения не превышал заданной величины t₀, а сум­марный расход дополнительных средств В был минимальным.

Задан сетевой график G = (Е, ) выполнения проекта, где Е — множество событий, а — множество работ. Продолжительность каждой работы равна t_ij. Известно, что вложение дополнительных средств х_ij в работу (i, j) сокра­щает время ее выполнения от t_ij до t’_ij, причем , где k_ij – технологические коэффициенты использования дополнительных средств. Но сокращение продолжительности работы не беспредельно, для каждой работы существует минимально возможное время ее выполнения d_ij.

Требуется определить количество дополнительных средств x_ij, которые необходимо вложить в работы (i, j), а также время начала и окончания вы­полнения этих работ, что­бы проект был выполнен в срок t₀, а суммарные дополнительные затраты были минимальными.

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

Ограничение (6.4) определяет время завершения проекта, оно должно быть не больше заданного t_о. Ограничения (6.5) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (6.6) показывают зависимость продол­жительности каждой работы от вложенных в нее дополнитель­ных средств. Ограничения (6.7) обеспечивают выполнение ус­ловий предшествования работ: время начала выполнения каж­дой работы должно быть не меньше времени окончания непос­редственно предшествующих ей работ. Ограничение (6.8) — условие неотрицательности.

Задача 2 заключается в сокращении срока выполнения проекта, насколько это возможно за счет вложения суммы дополнительных средств, не превышающей В. Время выполне­ния каждой работы должно быть не меньше минимально воз­можного времени d_ij. Необходимо определить время начала и окончания каждой работы и величину дополнительных средств х_ij, которые нужно выделить на ускорение выполне­ния работы (i,j).

Математическая модель задачи 2 имеет вид:

Смысл ограничений (6.10) – (6.13) аналогичен соответствующим огра­ничениям постановки задачи 1 (6.4) — (6.8). Если в последнее событие сети n входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю . Тогда целевая функция запи­шется так .

6.2 Оптимизация проекта по стоимости. В общем случае стоимость выполнения работы зависит от ее продолжительности. Продолжительность каждой работы может изменяться между двумя границами d_ij и D_ij, определя­емыми техническими или экономическими соображениями. Если D_ij — нормальная продолжительность, ей соответствует минимальная стоимость с_ij выполнения работы (i, j); если d_ij — минимально возможная (экстренная) продолжитель­ность работы, при этом стоимость работы будет максимальной C_ij. Если при планировании проекта для каждой работы будет взята ее нормальная (наибольшая) длительность D_ij, то стои­мость проекта будет минимальной. Если для каждой работы взять ее ускоренную, минимально возможную продолжитель­ность d_ij, то получим срочный план. Стоимость выполнения проекта в этом случае будет максимальной.

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

Рассмотрим оптимизацию комплекса работ по стоимости при фиксированном сроке выполнения.

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

Увеличение продолжительности работы (i, j) по сравне­нию с минимальным сроком выполнения на () вызовет экономию средств на величину h_ij (), a стоимость выполнения работы станет равна

Если t₀ = t_кp, то оптимизация осуществляется за счет увели­чения продолжительности некритических работ; если t_кр < t₀, — то за счет всех работ комплекса.

Математическая запись задачи:

Здесь 1 — номер исходного события, n — номер заверша­ющего события.

Рассмотрим оптимизацию комплекса работ по стоимости при нефиксированном сроке выполнения.

Пусть задан сетевой график проекта и известны продол­жительность каждой работы и стоимость ее выполнения в нормальном (D_ij, c_ij) и срочном (d_ij, C_ij) режиме работы. Если все работы выполняются в нормальном режиме, то критичес­кий срок будет наибольшим, а стоимость выполнения — наи­меньшей. Время выполнения проекта может быть уменьше­но путем увеличения стоимости. Необходимо сократить кри­тический срок до некоторого минимально возможного значе­ния при наименьшем возрастании стоимости выполнения проекта.

6.3 Оптимизация проекта по ресурсам. Пусть проект задан сетевым графиком. Для выполнения проекта выделено R единиц ресурса. Каждая работа характе­ризуется продолжительностью выполнения t_ij и интенсив­ностью потребления ресурса r_ij. Под интенсивностью потреб­ления будем понимать требуемое количество ресурса для вы­полнения работы (i, j) в единицу времени. Для простоты до­пустим, что интенсивности постоянные.

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник