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

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

Приведём алгоритм оптимизации сетевого графика по стоимости и рассмотрим его на примере.

Пусть комплекс операций представлен сетевым графиком G (E, з). Оперирующая сторона для выполнения комплекса операций располагает m видами ресурсов в количествах R_s (s = 1, m). Каждая операция комплекса характеризуется продолжительностью выполнения t_ij и интенсивностью r (s)ij. Под интенсивностью операции (i, j) будем понимать требуемое количество ресурсов для ее выполнения в течение времени t_ij, например, требуемое количество рабочих или механизмов. Топологически сетевой график удовлетворяет технологическим ограничениям (ресурсные ограничения при составлении сетевого графика не принимались во внимание). Поэтому, прежде чем приступить к выполнению операций сетевого графика, необходимо определить потребное количество ресурсов по календарным срокам и сравнить его с наличными ресурсами. Если окажется, что в отдельные промежутки времени наличного количества ресурсов недостаточно для удовлетворения потребности в них, то ставится задача: найти такие календарные сроки начала и окончания операций сетевого трафика, при которых в любой момент планируемого периода было бы достаточно ресурсов для выполнения операций и время завершения комплекса было бы минимальным. Для простоты изложения алгоритма решения задачи рассмотрим случай, когда интенсивности постоянные и используется один вид ресурсов. Отметим, что приведенный ниже алгоритм не всегда позволяет найти оптимальное решение задачи, однако часто дает хорошее приближение к нему.

Алгоритм решения задачи.

Предварительный шаг.

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

Первый шаг

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

Определяем полные резервы времени Rⁿ_ij операций, расположенных над промежутком (ф₀, ф₁). Нумеруем эти операции в порядке возрастания их полных резервов. Операции с одинаковыми полными резервами времени нумеруем в порядке убывания интенсивностей.

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

Результатом выполнения этого действия является новая линейная диаграмма, момент ф₁ которой считаем началом оставшейся части комплекса операций. Операции (i, j), расположенные над промежутком (ф₀, ф_кр), изображаем так, чтобы их начала совпали с новыми ожидаемыми сроками свершения событий.

Общий шаг

Предположим, что выполнено k шагов алгоритма и получена линейная диаграмма, момент ф_кр которой является началом оставшейся части комплекса операций.

Проецируем на ось времени начало и конец каждой операции, расположенной над промежутком (ф_k, ф_кр), и обозначаем проекцию, ближайшую к ф_k, через ф_k+1. Таким образом, выделен новый промежуток ⁽ф_k^, ф_k+1⁾.

Определяем полные резервы времени Rⁿ_ij операций, расположенных над промежутком ⁽ф_k^, ф_k+1⁾, и нумеруем их. При этом в зависимости от постановки задачи возможны два случая: 1) операции не допускают перерыва в выполнении; 2) операции допускают перерывы в их выполнении. В первом случае сначала нумеруем операции (i, j), начатые левее момента ф_k, согласно возрастанию разностей между полными резервами этих операций и длительностями от начала момента до момента ф_k+1 (длительности операций обозначим через l_ij). Операции с одинаковыми разностями нумеруем в порядке убывания интенсивностей. Все остальные операции нумеруем в порядке возрастания их полных резервов, а с одинаковыми резервами — в порядке убывания интенсивностей. Во втором случае все операции нумеруются согласно предписаниям пункта 2 первого шага.

Выполняем то же, что и в пункте 3 первого шага. Однако следует иметь в виду, что если сдвигу подлежит операция (i, j) начатая левее ф_k, то в первом случае сдвигаем всю операцию, т. е. начало этой операции устанавливаем в момент ф_k+1, а во втором случае операцию делим на части и первую часть операции — отрезок продолжительностью от начала до ф_k — оставляем на месте, а вторую часть — от ф_k до конца сдвигаем вправо на величину промежутка (ф_k, ф_k+1). Части разделенной операции в дальнейшем рассматриваем как самостоятельные операции и присваиваем им соответствующие номера событий.

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

Рассмотрим приведённый алгоритм на примере.

Для выполнения комплекса операций, представленного сетевым графиком (рисунок 1), выделено 10 единиц возобновляемых ресурсов (R = 10). Каждой дуге графика приписаны два числа: первое — время выполнения операции в днях; второе — требуемое количество ресурсов. Необходимо определить сроки выполнения операций таким образом, чтобы завершить весь комплекс за минимальное время. Операции не допускают перерыва в выполнении.

Рисунок 3.1 — Оптимизация комплекса операций по стоимости.

Предварительный шаг. Составляем линейную диаграмму (график Ганта) комплекса операций (рисунок 2, а). Построим эпюру потребления ресурса без учета его ограниченности (рисунок 2, б). Из эпюры видно, что в первые четыре дня потребность ресурсов превышает наличное количество на 2 единицы, в 5-й и 6-й день имеется в избытке 3 единицы ресурса, в 7-й и 8-й день снова превышается потребность на 2 единицы, в 9-й день спрос равен 10 единицам, а в последующее время имеется в избытке 8 единиц ресурса.

Найдем на диаграмме критический путь: операция (3,5) заканчивается позже всех операций в момент времени t₅ = 12. Следовательно, она критическая и t_кp = 12. Так как операция (3,5) начинается во время t₃ = 8, то найдем операцию с конечным событием (3), которая заканчивается в это же время. Такой операцией является операция (2,3). Следовательно, (2,3) также критическая. Операции (2,3) непосредственно предшествует критическая операция (1,2). Таким образом, м_кр =(1 — 2 — 3 — 5).

Первый шаг

Проецируем на ось времени начала и концы операций комплекса. Ближайшая проекция к началу координат ф₁ = 4. Рассматриваем промежуток (ф₀, ф₁), где ф₀ = 0.

Над промежутком (ф₀, ф₁) расположены операции (1,2), (1,3) и (1,4). Полные резервы этих операций равны: Rⁿ₁₂ = 0, Rⁿ₁₃ = 4, Rⁿ₁₄ = 3. Нумеруем эти операции по возрастанию полных резервов времени. Операция (1, 2) имеет номер 1, (1,4) — номер 2, и операция (1,3) с наибольшим резервом — номер 3.

Суммируем последовательно величины интенсивности операций, расположенных над промежутком (ф₀, ф₁) в порядке возрастания их номеров, и сравниваем полученные суммы с заданной величиной ресурса R. Так как интенсивность r₁₂ = 4 < R = 10, то операцию (1,2) оставляем на месте. Суммируя величины интенсивности операций (1,2) и (1,4), имеем r₁₂ + r₁₄ = 4 + 3 = 7 < 10. Следовательно, операция (1,4) тоже остается на месте. Добавив к сумме величину интенсивности операции (1,3), имеем r₁₂ + r₁₄ + r₁₃ = 4 + 3 + 5 = 12 > 10. Так как для выполнения операции (1,3) на промежутке (ф₀, ф₁) не хватает 2 единиц ресурса, то операцию (1,3) сдвигаем вправо на величину отрезка (ф₀, ф₁), т. е. начало операции (1,3) устанавливаем в момент ф₁ = 4. Результаты сдвига отражены на новой линейной диаграмме (рисунок 2, в).

Так как не все операции комплекса просмотрены, то переходим ко второму шагу.

Второй шаг

Начало нового промежутка совпадает с ф₁ = 4, а конец ф₂ = 6 — с моментом окончания операций (1,2) и (1,4).

Операции (1,2) и (1,4) начинаются левее момента ф₁ поэтому нумеруем их в первую очередь согласно возрастанию разностей Rⁿ₁₂ — l₁₂ = 0 — 6 = - 6 и Rⁿ₁₄ — l ₁₄ = 3 — 6 = - 3. Таким образом, операция (1,2) имеет номер 1, операция (1,4) — номер 2 и операция (1,3) — номер 3.

Суммируя величины интенсивности операций согласно их нумерации и сравнивая с R, получаем, что сдвигу вправо на 2 единицы подлежит операция (1,3). В результате сдвига получаем новую линейную диаграмму (рисунок 2, г). Время выполнения операций по сравнению с исходным вариантом увеличилось на 2 дня: ф₅ = 14.

Решение не закончено, переходим к третьему шагу.

Третий шаг

Новый промежуток (ф₂, ф₃). Момент ф₃ = 8.

Над промежутком (ф₂, ф₃) операций, начатых левее момента ф₂, нет, следовательно, нумеруем операции, лежащие над промежутком по возрастанию полных резервов: (1,3) — номер 1, так как Rⁿ₁₃= 0; (2,3) — номер 2, так как Rⁿ₂₃ = 2; (4,5) — номер 3, (2,5) — номер 4, так как Rⁿ₄₅ = Rⁿ₂₅ = 5, r₄₅ = 5 > r₂₅ = 3. (Нумерация операций (2,5) и (4,5) произведена по убыванию их интенсивностей.).

Так как r₁₃ = 5 < 10 и r₁₃ + r₂₃ = 5 + 4 = 9 < 10, то эти операции не сдвигаются. Операции (4,5) и (2,5) сдвигаем вправо на 2 единицы, потому что добавление величины интенсивности приводит к превышению R = 10. Новая диаграмма приведена на рисунке 2, д.

Переходим к четвертому шагу.

Четвертый шаг

Момент ф ₄ = 10.

Операция (1,3) имеет номер 1, как начатая левее момента ф₃ = 8. Операции (4,5) приписываем номер 2, операции (2,5) — номер 3, так как Rⁿ₄₅ = Rⁿ₂₅ = 3, а r₄₅ = 5 > r₂₅ = 3.

Операции (1,3) и (4,5) не сдвигаются, так как r₁₃ = 5 < 10 и r₁₃ + r₄₅ = 10 = R, а операция (2,5) сдвигается вправо на 2 единицы. Новая диаграмма изображена на рисунке 2, е.

Рисунок 3.2 — Линейная диаграмма (график Ганта).

Пятый шаг

Новый промежуток (ф ₄, ф₅), ф₅ = 11.

Номера операций: (4,5) — номер 1, как начатая левее, (3,5) — номер так как Rⁿ₃₅ = 0; (2,5) — номер 3, так как Rⁿ₂₅ = 1.

Все операции, лежащие над промежутком (ф ₄, ф₅), остаются на месте, потому что r₄₅ + r₃₅ + r₂₅ = 5 + 2 + 3 = 10 = R.

Так как конец рассмотренного промежутка ф₅ = 11 меньше ф₅ = 14, то переходим к следующему шагу.

Шестой и седьмой шаг

Выполнив последовательно все действия этих шагов, убедимся, что количество требуемых ресурсов на промежутках (ф₅, ф₆) и (ф₆, ф₇) не превосходит имеющихся в распоряжении, таким образом, линейная диаграмма (рисунок 2, е) является решением задачи, время окончания выполнения комплекса операций равно 14. Из эпюры потребления ресурса (рисунок 2, ж) видно, что на всем протяжении выполнения комплекса операций количество используемых ресурсов не превосходит имеющихся в распоряжении.

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

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

Рассмотрим более общий случай, когда.

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

(14).

где. Учитывая, что величины известны, раскроем скобки в правой части (14) и обозначим через сумму.

(15).

В результате получим (формула 16).

(16).

Здесь время выполнения операции равно разности между временем ее окончания и временем начала .

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

(17).

На неизвестные величины задачи налагаются следующие ограничения:

— продолжительность выполнения каждой операции должна быть не меньше и не больше (формула 18).

(18).

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

(19).

— выполнение комплекса операций должно быть завершено не позже директивного срока (формула 20):

(20).

где n — номер завершающего события.

— переменные должны быть неотрицательными.

; для всех, при этом, .

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

Исходные данные комплекса операций, представленного сетевым графиком (Рис. 3.3), приведены в таблице 2.

Требуется оптимизировать сетевой график по стоимости при.

Таблица 2 Исходные данные для примера.

Параметры.	Операции.
(1,2).	(1,3).	(2,3).	(2,5).	(3,4).	(3,5).	(4,5).

Запишем, для всех, принадлежащих сетевому графику.

;

;

;

;

;

;

При записи функции принято, что Так как при параметрах меньше, то оптимизация возможна за счет всех операций сетевого графика.

Запишем ограничения по времени выполнения операций.

Ограничения по предшествованию в выполнении операций:

Все неизвестные должны быть неотрицательными, т. е.

для всех операций сети.

В результате решения получим ответ.

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