Рассмотрим сначала различные постановки задач распределения ресурсов для однотемной одноцелевой программы . Исходя из двух возможных целевых установок при управлении проектом, описанным сетевой моделью, возможны два основных типа постановки задач. Первый тип ориентирован на жесткое соблюдение ограничений по ресурсам, тогда как второй тип предполагает строгое выполнение сроков завершения проекта. Формулировка первого типа постановки задачи («калибровка»). При заданных ограничениях в потреблении ресурсов найти такое их распределение с учетом технологической последовательности ведения работ, определенной топологией сетевого графика, которое обеспечивает завершение всей программы за минимальное время. Формулировка второго типа постановки задачи («сглаживание»). При соблюдении заданной продолжительности выполнения программы требуется так распределить ресурсы по отдельным работам, чтобы их потребление было оптимальным. Вопрос о выборе критерия оптимальности для этой постановки будет нами рассмотрен специально. В силу разного механизма удовлетворения потребности в ресурсах их принято разделять на две группы: накапливаемые (складируемые) и ненакапливаемые (нескладируемые). Вторую группу ресурсов часто называют «ресурсы типа мощности». К первой группе относятся ресурсы, которые по своему характеру допускают накопление с возможностью их последующего использования, например, денежные средства, различные материалы и конструкции и т.п. Ресурсные ограничения в этом случае могут быть заданы интегральной неубывающей функцией, показывающей в каждый момент времени суммарную величину поставок ресурса за весь предшествующий период. Ко второй группе относятся ресурсы, накопление которых для последующего использования невозможно. Например, ресурсы рабочего и машинного времени. Простой рабочих и механизмов является безвозвратной потерей. Ресурсные ограничения для этой группы задаются функцией наличия ресурса в каждый момент времени. Пусть rkij– интенсивность потребления k-го ресурса на работе (i,j). Тогда величину wkij = rkijtij – назовем объемом работы. Обозначим εk – множество работ, потребляющих ресурс k, а εkt – множество работ, потребляющих ресурс k в момент времени t (εk=U∀tεkt), тогда общая
168 потребность на всю программу в k-м ресурсе равна Wк =∑(i,j)∈εkwkij = =∑(i,j)∈εkrkijtij, причем для ресурсов второго типа этот показатель измеряется в машиносменах, человекоднях и т.п. Пусть наличие ресурсов в каждый момент времени задано функцией Ак(t). Если наличие ресурсов во времени неизменно, т.е. Ак(t)=Ак, то величина max k⎨Wк/Aк⎬ – определяет минимальное время выполнения программы с точки зрения обеспеченности ресурсами. Учитывая, что время выполнения однотемной программы не может быть меньше критического(Tn0), вычисленного без учета ограниченности ресурсов, то получаем оценку нижней границы времени, искомого в задачах «калибровки»: Т ≥ max⎨ Tn0, maxk⎨Wк/Aк⎬ ⎬. Обозначая 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. Процедура 2. Последовательно (начиная с t=0) проверяем соотношение 2 модели. Если оно выполняется (ресурса хватает на все работы, попавшие в данный интервал), то переходим к следующему интервалу времени и так до конца, в противном случае – к процедуре 3.
169 Процедура 3. Все работы, на которые в интервале τ не хватило ресурса, упорядочиваем в соответствии с Кij (корректируя при этом полный резерв в (2.4.1) ранее начатых работ на число дней от их начала до τ). Сдвигаем работы по календарной шкале вправо в порядке возрастания Кij (устанавливаем начало на τ+1 или прерываем работу в интервале τ, если разрыв возможен), пока суммарная потребность в ресурсе оставшихся в данном интервале работ не придет в соответствие с его наличием. После этого производим пересчет временных параметров работ, расположенных в правой от τ части линейной диаграммы, возвращаемся к процедуре 2, и процесс решения продолжается с интервала τ+1. Проиллюстрируем применение алгоритма на примере. Пример 2.4.1. Имеется сетевой график 7 3 6 4 5 5 2 5 4 6 3 2 5 4 3 4 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. В табл. 2.4.3 приведены результаты расчетов временных параметров работ Таблица 2.4.3 (i,j) tij Тi0 Тj1 Rпij Rсij (0,1) 2 0 2 0 0 (0,2) 4 0 7 3 0 (0,3) 5 0 6 1 1 (1,3) 4 2 6 0 0 (2,5) 7 4 14 3 3 (1,4) 3 2 12 7 7 (3,4) 6 6 12 0 0 (4,5) 2 12 14 0 0 (3,5) 4 6 14 4 4 0 1 4 3 2 5
170 На рис.2.4.10 приведен календарный план при отсутствии ограничений на ресурсы. В этой линейной диаграмме начала всех работ приурочены к ранним срокам их свершения. Над каждой работой проставлена необходимая для ее выполнения потребность в ресурсе. Для наглядности под линейной диаграммой поместим эпюру потребности в ресурсах (график функции F(t)). Рабо ты
Процедура 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) в пределах свободного резерва. Результаты этого шага отобразим на рис.2.4.11. Процедура 2. Рассматриваем теперь интервал от 2 до 5. Здесь 4 работы имеют общую потребность 19, значит, опять переходим к процедуре 3.
Рис 2.4.11. Процедура 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) на три дня в пределах ее свободного резерва. Результаты на рис.2.4.12. Процедура 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 человек.
173 Алгоритм закончен, время выполнения проекта Т=17. Окончательный результат представлен на рис.2.4.13. Как мы видим, совсем без резервов остались работы (1,4) и (4,5), у остальных работ, даже работ бывшего критического пути, появились резервы времени. Рабо ты
Аналогичная постановка задачи для накапливаемых ресурсов
отличается от предыдущей только видом ограничения 2, которое принимает вид: 2′. ∑ tτ=1Ак(t) ≥ ∑ tτ=1Fк (t), для всех τ и k; т.е. суммарная потребность в накапливаемом ресурсе от начала планового периода к любому моменту τ не должна превышать суммарного объема поставок этого же вида ресурса за соответствующий период. Алгоритм решения данной задачи в принципе проще предыдущего и здесь не приводится. Оптимальное распределение ресурсов при заданном времени – “сглаживание”, является задачей, в некотором смысле обратной к рассмотренной выше. Прежде всего, необходимо определить критерий оптимальности. В большинстве случаев целесообразно в качестве критерия оптимальности принимать меру неравномерности
174 потребления ресурсов. Если Т – заданное время выполнения программы, то Rkср=Wк/Т – среднее потребное количество ресурса k в единицу времени. В качестве меры неравномерности потребления ресурса могут быть выбраны различные функции, например: φ1=∑∀t⏐Fк(t) – Rkср⏐,
- ξ2 – если (Fк(t) – Ak(t)) < 0, т.е. ξ1 – удельные затраты, связанные с превышением потребности над наличием (для ресурсов типа “мощности” – стоимость сверхурочного времени), ξ2 – удельные затраты, связанные с избыточным наличием ресурса (для ресурсов типа “мощности” – стоимость простоя исполнителей или оборудования). Могут быть и другие критерии. Выбор критерия связан со спецификой конкретной системы управления проектом, например, выбирая φ1, мы предполагаем «равнозначность» как положительных, так и отрицательных отклонений потребности в ресурсе от его средней потребности, а также два отклонения по 1 эквивалентны одному отклонению на 2. Критерий φ2 применим в случае, когда такие отклонения не эквивалентны (одно на 2 равно 4 по 1), φ5 подобен φ2, только отклонения анализируются не от средней потребности, а от наличия ресурса. Критерий φ6 целесообразен при различной оценке превышения (положительной или отрицательной). Критерий φ4 (наибольшее ежедневное потребление) часто используется при составлении проекта организации строительства отдельного объекта или комплекса работ. Таким образом, математическая модель задачи «сглаживания» имеет вид: Найти такие сроки начала и окончания работ (i, j) Тi* и Тj*, что 1. Тj* – Тi* – tij ≥ 0, для всех работ (i, j); 2. Tn* ≤ Т; 3. φi →min. Рассмотрим идею алгоритма минимизации максимального потребления ресурса (критерий φ4). Процедура 1. Расчет временных параметров сетевой модели и составление линейной диаграммы по ранним срокам. Построение эпюры потребности в ресурсе. Вычисление уровня = maxtFк(t).
175 Процедура 2. Понижаем уровень на 1. В интервалах времени, где наблюдается превышение потребности над уровнем, пытаемся сдвинуть работы в пределах их резервов. Работы для сдвига выбираем в порядке возрастания коэффициентов напряженности. Если подобным образом удалось ликвидировать все превышения над уровнем, повторяем процедуру 2 сначала, иначе – стоп, получен оптимальный план. Представленные выше модели предполагали постоянную продолжительность работ. Практически почти каждую работу можно выполнить за различное время в зависимости от количества ресурсов, привлекаемых для выполнения данной работы.
Ви переглядаєте статтю (реферат): «Постановки задач распределения ресурсов» з дисципліни «Математична економіка»
