Оптимизация потребления ресурсов методом «Калибровка»

Обозначая F^к(t)=å_(i,j)Îε^k_tr^k_ij – потребность в ресурсе k в момент времени t, получаем математическую модель задачи «Калибровка» в виде:

Найти такие сроки начала и окончания работ (i, j) Т_i* и Т_j*, что

1. Т_j* – Т_i* – t_ij ≥ 0, для всех работ (i, j);

2. А^к(t) ≥ F^к(t), для всех t и k;

3. T_n^* ®min.

Первое ограничение отображает требование соблюдения технологической последовательности работ.

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

T_n^* – срок свершения завершающего события.

Алгоритм решения сформулированной выше задачи носит эвристический характер, и основная его идея заключается в следующем:

(для упрощения примем k =1 и А^к(t)=А, т.е ресурс один и его наличие постоянно во времени).

Процедура 1.

Производится расчет временных параметров сетевого графика и составляется линейный календарный график, при этом начала работ (i,j) ставятся в ранние сроки свершения событий i (см. 1.5).

Процедура 2.

Последовательно (начиная с t=0) проверяем ограничение 2 модели. Если оно выполняется (ресурса хватает на все работы, попавшие в данный интервал), то переходим к следующему интервалу времени и так до конца, в противном случае – к процедуре 3.

Процедура 3.

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

Проиллюстрируем применение алгоритма на примере.

Пример 1. Имеется сетевой график

7

3

6 4 5 5

2 5 4 6 3 2

5 5 4

6 3 4

7 4 7

Цифра под стрелкой означает временную оценку (t_ij), цифра над стрелкой задает объем необходимого ресурса (r_ij). Рассмотрим людской ресурс и пусть имеется всего 12 исполнителей (т.е. А^к(t)=А=12).

Найдем суммарную трудоемкость всех работ W=åw_ij = år_ijt_ij= =6*2+5*5+3*4+7*4+4*4+5*6+5*2+3*4+4*7=173, откуда получаем оценку для Т:

Т ≥ maxí T_n⁰, W/A ý= maxí 14, 173/12ý=15.

Процедура 1. В табл. 3 приведены результаты расчетов временных параметров работ.

Таблица 3

(i,j)	tij	Тi0	Тj1	Rпij	Rсij
(0,1)
(0,2)
(0,3)
(1,3)
(2,5)
(1,4)
(3,4)
(4,5)
(3,5)

На рис.11 приведен календарный график при отсутствии ограничений на ресурсы. В этой линейной диаграмме начала всех работ приурочены к ранним срокам их свершения. Над каждой работой проставлена необходимая для ее выполнения потребность в ресурсе. Для наглядности под линейной диаграммой поместим эпюру потребности в ресурсах (график функции F(t)).

Работы
(4,5)
(3,5)
(3,4)
(2,5)
(1,4)
(1,3)
(0,3)
(0,2)
(0,1)

0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

20 19

14 А=12

12 12

10 8 9

8

6 5

Рис 11.

Процедура 2. Рассматриваем начальный интервал (от 0 до 2). Здесь потребность в ресурсе превышает его наличие на 2. Значит, переходим к процедуре 3.

Процедура 3. Вычисляем коэффициенты напряженности для работ, выполняемых в этом интервале: К₀₁=1 –0=1, К₀₂=1 –3/(14 – 0)=0.79, К₀₃=1 –1/(14 – 8)=0.83. Сдвигаем работу (0,2) с меньшим коэффициентом на два дня; т.к. она не имеет свободного резерва, то соответственно сдвигается на два дня и работа (2,5) в пределах свободного резерва. Результаты этого шага отобразим на рис.12.

Работы
(4,5)
(3,5)
(3,4)
(2,5)
(1,4)
(1,3)
(0,3)
(0,2)
(0,1)

0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

20 19

14 А=12

12 11 12

10 9

8 7

6 5

Рис 12.

Процедура 2. Рассматриваем теперь интервал от 2 до 5. Здесь 4 работы имеют общую потребность 19, значит, опять переходим к процедуре 3.

Процедура 3. Вычисляем К₀₃=1 –1/(14 – 8)=0.83, К₀₂=1 –1/(14 –0)= =0.93, К₁₃=1 –0=1, К₁₄=1 –7/(14 – 2)=0.42. Сдвигаем работу (1,4) на три дня в пределах ее свободного резерва. Результаты на рис.13.

Работы
(4,5)
(3,5)
(3,4)
(2,5)
(1,4)
(1,3)
(0,3)
(0,2)
(0,1)

0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

20 19

14 14 А=12

12 11 12 12

10 9

6 5

2 Рис 13.

Процедура 2. Рассматриваем интервал от 5 до 6. Имеем превышение потребности ресурса над его наличием на 2.

Процедура 3. Самый меньший коэффициент напряженности у работы (1,4), К₁₄=1 –4/(14 – 2)=0.67, поэтому ее сдвигаем на 1. Остаются в расписании на этот интервал работы (0,2) и (1,3) с общей потребностью 7 человек.

Процедура 2. Рассматриваем интервал от 6 до 9. Суммарная потребность составляет 19.

Процедура 3. Самый меньший коэффициент напряженности опять у работы (1,4), К₁₄=1 –3/(14 – 2)=0.75, поэтому ее сдвигаем на 3. Остаются в расписании на этот интервал работы (2,5), (3,4) и (3,5) с общей потребностью 12 человек.

Процедура 2. Рассматриваем интервал от 9 до 10. Суммарная потребность составляет 19.

Процедура 3. Сейчас меньший коэффициент напряженности у работы (3,5), но ее сдвиг не уменьшит потребность в ресурсе на необходимое число (7), поэтому вынуждены двигать опять работу (1,4) на 1. Остаются в расписании на этот интервал те же работы (2,5), (3,4) и (3,5) с общей потребностью 12 человек. Т.к. у работы (1,4) резерва уже не было, то соответственно подвинулась работа (4,5) также на 1.

Процедура 2. Рассматриваем интервал от 10 до 12. Суммарная потребность составляет 16.

Процедура 3. Сейчас резервы времени исчерпаны, коэффициенты напряженности у всех работ равны 1, поэтому вынуждены двигать опять еще не начатую работу (1,4) на 2. Остаются в расписании на этот интервал работы (2,5) и (3,4) с общей потребностью 9 человек. Т.к. у работы (1,4) резерва уже не было, то соответственно подвинулась работа (4,5) еще на 2.

Процедура 2. Рассматриваем интервал от 12 до 13. Суммарная потребность составляет 11. На интервале от 13 до 15 потребность составляет 7 и от 15 до 17 потребность 5 человек.

Алгоритм закончен, время выполнения проекта Т=17. Окончательный результат представлен на рис.14. Как мы видим, совсем без резервов остались работы (1,4) и (4,5), у остальных работ, даже работ бывшего критического пути, появились резервы времени.

Работы
(4,5)
(3,5)
(3,4)
(2,5)
(1,4)
(1,3)
(0,3)
(0,2)
(0,1)

0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

14 А=12

12 11 12 12 11

10 9

8 7 7

6 5

2 Т=17 Рис14.

Аналогичная постановка задачи для накапливаемых ресурсов отличается от предыдущей только видом ограничения 2, которое принимает вид:

2¢. å _t^t₌₁А^к(t) ≥ å _t^t₌₁F^к (t), для всех t и k;

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

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