Мегаобучалка Главная | О нас | Обратная связь


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



2015-11-11 940 Обсуждений (0)
Оптимизация потребления ресурсов методом «Калибровка» 0.00 из 5.00 0 оценок




Обозначая 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.

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

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

7

3

6 4 5 5

2 5 4 6 3 2

5 5 4

6 3 4

7 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)).

Работы                                            
(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. Вычисляем коэффициенты напряженности для работ, выполняемых в этом интервале: К01=1 –0=1, К02=1 –3/(14 – 0)=0.79, К03=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. Вычисляем К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.

 

Работы                                            
(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), К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), у остальных работ, даже работ бывшего критического пути, появились резервы времени.

 

Работы                                            
(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¢. å tt=1Ак(t) ≥ å tt=1Fк (t), для всех t и k;

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

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



2015-11-11 940 Обсуждений (0)
Оптимизация потребления ресурсов методом «Калибровка» 0.00 из 5.00 0 оценок









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

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...
Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (940)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)