Сглаживание профиля потребности в ресурсах

Вывод о физической реализуемости КР формально может быть сделан, если диаграмма (профиль) потребления ресурсов составленного КП охваты­вается (мажорируется) диаграммой наличия ресурсов, т.е. если r_kp.t . Однако дело осложняется тем, что практически реали­зуется только такой профиль, который имеет постепенно нарастающий (убы­вающий) передний (задний) фронт и не содержит резких переходов по уров­ню потребления ресурсов, поэтому выполнения формального неравенства мало. Предпочтительным профилем является унимодальный с поло­гими передним и задним фронтами. Такой профиль присущ реальным органи­зационным системам, обладающим определенной инерционностью.

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

при условии неизменности t_кр и (т.е. при неизменной общей ресурсоемкости КР) (см. пример на рис. 2.9 ,а).

Для получения криволинейного унимодального профиля с пологими фронтами в качестве критерия сглаженности можно брать минимум суммы квадратов изменений ресурсов в каждый момент времени (предполагается, что t_u,t [0;t_кр] целочисленны). Пусть x_kp.t - ресурсное изменение в момент t [0;t_кр]. Тогда

R=

.

Рис. 2.9. Оптимальные ресурсные профили КР для R=110, t_кр=10 по критериям:

Минимизация дисперсии эквивалентна минимизации суммы квадратов изменений ресурсов. Минимизация этой функции по методу множителей Лаг-ранжа дает следующее решение для r_kp([8] , см. рис. 2.9,6):

Профиль синтезирован при отсутствии ограничений по составу и структуре КР. Пусть в комплексе каждая работа имеет целочисленную длительность t_u, требует фиксированного количества ресурсов r_u и подчинена условиям предшествования. Пусть работы выполняются без прерываний. Стремление получить унимодальный профиль r_kp.t - не должно привести к увеличению t_kp, т.е. профиль можно пытаться улучшить только за счет некритических работ.

Пусть - момент начала u oтносительно t_р.н.и( если t_н.и=t_р.н.и и если t_н.и=t_п.н.и). Задача синтеза ресурсного профиля будет выглядеть следующим образом:

где x_ut - ресурсное изменение для работы u в отрезок времени t ; U^kp и - множество критических и некритических работ соответственно при ограничениях если u>v, то t_р.н.и+t_u t_р.н.v; t_н.и+t_u t_н.v и, следовательно, .

В этой задаче представляет собой сдвиг вправо некритических работ в пределах их .

Решение возможно по следующему алгоритму.

1. Образовать комбинацию значений для вычислить сумму квадратов ресурсных изменений и сравнить ее с минимальной из полученных на предыдущих комбинациях.

2. Запомнить комбинацию, дающую минимальную сумму квадратов изменений, и перейти к п. 1, если есть еще не оцененные комбинации, иначе закончить.

Сглаживание ресурсов при наличии ограничений по составу и структуре КР является комбинаторной задачей большой размерности. Поэтому практи­чески используются эвристические алгоритмы. Один из них выглядит следую­щим образом (шаги 1—5):

1)вводится понятие цепи работ как полной последовательности некритических работ, имеющих одинаковый начальный резерв времени. Цепь рассматривается как единая укрупненная работа L, т.е. задержки между работами це­пи исключаются. Выявляются все цепи КР;

2) определяются ресурсные изменения для критических работ

;

3) при выборе цепи для распределения ресурсов используются правила предпочтения:

1. Чем меньше t_р.н, тем выше приоритет.

2. Чем меньше R^полн, тем выше приоритет.

3. Чем больше длительность цепи, тем выше приоритет.

4. Чем ближе к исходному событию, тем выше приоритет;

4)для каждого t_Н.L [t_P.H.L, t_П.H.L] рассчитывается сумма квадратов ресурсных изменений объединенного ресурсного профиля крити­ческих работ и данной цепи. Значение t_H.L, при котором достигается , запоминается как и величина суммы квадратов ресурсных изнении и суммарный профиль;

5) шаги 3 и 4 повторяются для всех цепей, причем минимизируется сумма квадратов для уже спланированных работ и следующей из оставшихся цепей вплоть до их исчерпания. Алгоритм не гарантирует, что полученный профиль будет унимодален. Тогда необходимо принять дополнительно меры.

Смысл формирования цепей последовательных некритических работ состоит в том, что изъятие задержек между работами существенно уменьшает сумму квадратов ресурсных изменений (рис. 2.10).

Рис. 2.10. Эффект образования цепей работ:

а-цепь отсутствует: ; б)-цепь образована:

Упражнения к главе 3

1. Постройте календарный план для примера из [l] по поздним срокам, полагая, что r_u=1 для всех действительных работ комплекса и для . Сравните ресурсные диаграммы для КП, построенных по ранним и поздним срокам.

2. Постройте КП для предыдущего упражнения

а) последовательным и

б) параллельным методами при r⁰ [1 ; ].

Сравните эффективность полученных вариантов планов по t_kp и числу преры­ваний работ комплекса.

3. Сформулируйте задачу минимизации ~6цр для СМ из предыдущих упражнений как задачу линейного программирования в переменных длительностях логически и ресурсно-допустимых фронтов работ.

4. Постройте матрицу различий для всех ресурсно-допустимых фронтов для задачи из предыдущего упражнения. Выберите какую-нибудь последовательность фронтов и подсчитайте число прерываний работ.

5. Для СМ из "n" несравнимых действительных работ подсчитайте количество различных календарных планов для непрерываемых и прерывае­мых работ в случаях:

а) n=2 ;

б) n=3 .

Сравните полученные числа.

6. Оформите задание на ЕС ЭВМ для решения сформулированной в упражнении 3 задачи линейного программирования, сдайте его на счет и проанализируйте полученный листинг.

Методом локальной оптимизации выберите последовательность фронтов с минимальным числом прерываний работ.

Постройте линейно-ресурсную диаграмму для полученного оптимального плана.

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

8. Обоснуйте алгоритм построения всех логически допустимых фронтов для однозначно индексируемой сети.

9. Какова оценка сверху для числа работ главного фронта КР?

10. Дайте обоснование формулам для числа прерываний работ в календарном плане как функции расстояний между фронтами работ.

11. Для КР, представленного на рис. 2.5:

а) постройте схемы диаграммы потребления ресурсов и линейно-ресуроной диаграммы;

б) постройте схему линейной диаграммы для КП при d= (0-1-2-3-4-5-6-7-0).

12. Оцените и сравните число шагов алгоритмов КП в последователь­ном и параллельном методах.

13. Оцените и сравните число различных КП для случаев непрерыва­емых и прерываемых работ.

Глава 4. УПРАВЛЕНИЕ РЕАЛИЗАЦИЕЙ И АВТОМАТИЗАЦИЯ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ СЕТЕВЫХ МОДЕЛЕЙ КОМПЛЕКСОВ РАБОТ

В гл. 1 неявно предполагалось, что разработка КП ведется до момента фактического начала КР. Эта стадия жизненного цикла КР является стадией формирования. За ней следует стадия реализации КР, в ходе которой работы комплекса должны обеспечиваться ресурсами с таким расчетом, чтобы были выдержаны плановые сроки и качество конечного продукта. СМ КР на этой стадии должны позволять решать следующие задачи (1-5):

1. Различать и измерять степень завершенности КР в любой момент времени периода выполнения (стадии реализации КР)

2. Фиксировать фактические значения временных, ресурсных и стоимостных параметров КР и их отклонения от запланированных.

3. Анализировать причины отклонений достигнутых значений показателей от установленных на этапах исходного планирования (стадии формирования КР) или на предшествующих этапах реализации.

4. Прогнозировать будущие состояние КР и их соответствие плановым.

5. Формировать проекты решений по оперативному (т.е. в ходе выполнения) управлению КР на основе результатов контроля и анализа, касающихся целей, сроков, ресурсов, а также стимулов для исполнителей,

В данной главе изложены модели оперативного планирования и управления КР, базирующиеся на введенных ранее системно-логических и математических моделях отдельной работы и КР в целом. Будут даны сведения о промышленно применяемых пакетах прикладных программ (ГОШ), позволяющих в значительной степени автоматизировать обработку информации о КР на стадиях его формирования и реализации.

Управление реализацией КР

В гл. 2 [1] была дана математическая модель работы - ПФ, которая может быть использована в решении задач 1 - 5.