Стоимостная оптимизация сетевого графика при фиксированной величине критического пути

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

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

Зная коэффициенты изменения стоимости h_ij, можно для каждой работы определять стоимость её выполнения за время

t_ij⁽⁰⁾ ≤ у_ij ≤ t_ij⁽¹⁾

по формуле

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

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

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

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

у_ij = t_j – t_i,

где t_j и t_i – сроки наступления событий. Общая стоимость выполнения всего комплекса работ С выполняется как сумма стоимостей работ, т.е.

Составим систему ограничений модели.

Обозначим через К множество событий Р_j, лежащих на критическом пути, а через R множество работ (i, j), не лежащих на критическом пути. Эти работы имеют резервы времени и их продолжительность может быть увеличена в пределах t_ij⁽⁰⁾ ≤ у_ij ≤ t_ij⁽¹⁾.

Следовательно, разница между сроками наступления конечного и начального событий (t_j – t_i) для работ, принадлежащих R, может превышать величину t_ij⁽⁰⁾. Отсюда система ограничений в математической модели оптимизации по стоимости сетевого графика задаётся условиями:

t_j – t_i ≥  t_ij⁽⁰⁾, для любой работы (i, j)  R,

t_j = t_j⁽⁰⁾ =  t_j⁽¹⁾ для любых событий.

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

при условиях

t_j – t_i ≥  t_ij⁽⁰⁾, (i, j)  R,

t_j = t_j⁽⁰⁾ =  t_j⁽¹⁾, Р_j  К.

Эта задача линейного программирования, и решается она симплексным методом.

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

а уменьшение стоимости работы (i, j) – по формуле

где C_ij⁽⁰⁾ и С_ij⁽¹⁾ – величины, в которых заключается стоимость работы (i, j) при её продолжительности в пределах t_ij⁽⁰⁾ ≤ у_ij ≤ t_ij⁽¹⁾.

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

Таким образом, если t_ij⁽¹⁾ – t_ij⁽⁰⁾ > FS_ij, то в формуле для определения ∆C_ij величина t_ij⁽¹⁾ – t_ij⁽⁰⁾ заменяется на FS_ij.

Пусть задан некоторый комплекс работ, связывающий события и время выполнения работы (i j) – t_ij.

Окончательный вид сетевого графика с рассчитанными характеристиками:

– ранними и поздними (в скобках над событиями) сроками свершения событий;

– свободными резервами времени работ (в скобках рядом с продолжительностями работ) представлен на рисунке 6.8 (проверить самостоятельно):

Рисунок 6.8 – Сетевой график с рассчитанными характеристиками

Исходные данные для оптимизации и результаты оптимизации представлены в таблице 6.3.

Таблица 6.3 – Результаты частичной оптимизации сетевого графика

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

Стоимость первоначального варианта плана равна

.

Стоимость нового плана равна

С – ∆С = 1 000,

т.е. уменьшилась на 13,2%.

Продолжительность критического пути равна 58. Новый план имеет вид:

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