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

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

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

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

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

3. Tn* ®min.

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

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

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

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

(для упрощения примем 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.

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Пример 1. Имеется сетевой график

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

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

6 4 5 5

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 2 5 4 6 3 2

5 Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 5 4

6 3 4

7 Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 4 7

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

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

Т ≥ maxí Tn0, 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)).

Работы                                            
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (4,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (2,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,2)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,1)                                          

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 20 19

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 14 А=12

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 10 8 9

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 6 5

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

Рис 11.

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

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

Работы                                            
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (4,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (2,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,2)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,1)                                          

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 20 19

14 А=12

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 12 11 12

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 10 9

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 8 7

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 6 5

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

Рис 12.

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

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

Работы                                            
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (4,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (2,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,2)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,1)                                          

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

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

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 20 19

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 14 14 А=12

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 12 11 12 12

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 10 9

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 6 5

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 2 Рис 13.

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

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

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

Процедура 3. Самый меньший коэффициент напряженности опять у работы (1,4), К14=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), у остальных работ, даже работ бывшего критического пути, появились резервы времени.

Работы                                            
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (4,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (3,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (2,5)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,4)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (1,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,3)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,2)                                          
Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru (0,1)                                          

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T

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

14 А=12

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 12 11 12 12 11

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 10 9

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 8 7 7

Оптимизация потребления ресурсов методом «Калибровка» - student2.ru Оптимизация потребления ресурсов методом «Калибровка» - student2.ru 6 5

2 Т=17 Рис14.

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

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

2¢. å tt=1Ак(t) ≥ å tt=1Fк (t), для всех t и k;

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

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

Наши рекомендации