Побудова календарного графіка і розподіл ресурсів

Наступним результатом виконуваних на мережевій моделі розрахун­ків є календарний графік (план). Цей графік легко перетвориться в реальну шкалу часу, зручну для реалізації процесу виконання програми.

При побудові календарного графіка необхідно враховувати наявність ресурсів, тому що одночасне (паралельне) виконання деяких операцій через обмеження, пов’язані з робочою силою, устаткуванням і іншими видами ре­сурсів, може виявитися неможливим. Саме в цьому відношенні становлять цінність повні резерви часу некритичних операцій. Зрушуючи некритичну операцію в тому або іншому напрямку, але в межах її повного резерву часу, можна домогтися зниження максимальної потреби в ресурсах. Однак навіть при відсутності обмежень на ресурси повні резерви часу зазвичай використо­вуються для вирівнювання потреби в ресурсах протягом усього терміну реалізації програми. Власне кажучи, це означає, що програму вдається вико­нати більш-менш постійним складом робочої сили в порівнянні з випадком, коли потреби в робочій силі (та інших ресурсах) різко змінюються при пере­ході від одного інтервалу часу до іншого.

Календарний графік має вигляд діаграми. Спочатку на неї наносяться критичні операції. Як правило, вони зображуються суцільною лінією у верх­ній частині графіка.

Нижче пунктирними лініями зображуються некритичні операції. Причому початок лінії відповідає ранньому терміну початку роботи, а кінець – пізньому терміну завершення. Це означає, що календарні терміни цих опера­цій можна вибрати в зазначених межах за умови збереження відносин сліду­вання. Зверху над кожною лінією, що відповідає некритичній операції, вказу­ють її термін виконання (рис. 1.9).

Час

Некритичніоперації

Критичні операції

Рис. 1.9

Роль повних і вільних резервів часу при виборі календарних термінів виконання некритичних операцій пояснюється двома загальними правилами.

1. Якщо повний резерв дорівнює вільному, то календарні терміни не­критичної операції можна вибрати в будь-якій точці між її раннім початком і пізнім закінченням (пунктирні відрізки на рис. 1.9).

2. Якщо вільний резерв менший повного, то термін початку некри­тичної операції можна перенести відносно її раннього терміну початку не більше, ніж на величину вільного резерву, не впливаючи при цьому на вибір календарних термінів безпосередньо наступних операцій.

Некритичніоперації

Час

Час

Пізній календарний план для некритичних операцій

Ранній календарний план для некритичних операцій

Критичні операції

Рис. 1.10

Таким чином, якщо вільний резерв часу операції є меншим повного, це служить ознакою того, що остаточні календарні терміни такої операції не можна фіксувати, не перевіривши спочатку, як це вплине на терміни початку безпосередньо наступних операцій.

Настільки цінну інформацію можна одержати тільки на основі розра­хунків мережевої моделі.

Виконання операцій потребує використання різноманітних ресурсів: трудових, матеріальних тощо. Як правило, обсяги ресурсів обмежені. На­приклад, для виконання всього комплексу робіт є бригада робітників фіксо­ваного складу.

Далі припустимо, що під ресурсами будемо розуміти саме трудові ресурси. На основі календарного графіка тепер можна побудувати кален­дарний план виконання робіт з урахуванням потрібних ресурсів.

Розрізняють ранній та пізній календарні плани. Перший будується за умови, що всі роботи розпочинаються в свої ранні терміни. Другий – за умо­ви початку всіх робіт в пізні терміни. Пунктирною лінією на плані відобра­жається потреба в ресурсах для критичних операцій, що має бути обов’язково задоволена, якщо потрібно виконати програму в мінімально можливий термін. Приклад раннього та пізнього календарних планів наведений на рис. 1.10.

Аналіз обох планів дозволяє зробити такі висновки. При ранньому календарному плані некритичних операцій максимальна потреба в ресурсах складає 10 осіб, а при пізньому – 12. Отже, максимальна потреба в ресурсах залежать від використання резервів часу некритичної операції. Однак, як видно з останнього рисунка, незалежно від розподілу цих резервів макси­мальна потреба в робочій силі для розглянутої програми не може бути мен­шою десяти осіб, тому що інтервал часу, у межах якого можна виконувати операцію (2, 4), збігається з інтервалом критичної операції (2, 3). Графік потреби в робочій силі при ранньому календарному плані можна поліпшити, вибравши пізні календарні терміни для операції (3, 5) і призначивши вико­нання операції (3, 6) безпосередньо після завершення операції (4, 6).

Новий графік потреби в робочій силі, наведений на рис. 1.11 забез­печує більш рівномірний розподіл ресурсів. Схематично у верхній частині рисунка представлений перерозподіл ресурсів.

При реалізації деяких програм може ставитися мета не просто забез­печення рівномірного використання, ресурсів, а й обмеження максимальної потреби в них до певної межі. Якщо цієї мети не вдається досягти шляхом перепланування календарних термінів некритичних операцій, то для того, щоб знизити потребу в ресурсах, приходиться збільшувати тривалість деяких критичних операцій.

Через математичні труднощі поки що не розроблено метод, який забезпечував би оптимальне вирішення задачі рівномірного використання ресурсів, тобто задачі мінімізації максимальної потреби в ресурсах у будь-який

Час

Час

Рис. 1.11

момент процесу виконання програми. Тому приходиться користуватися евристичними алгоритмами, подібними наведеному вище. Усі ці алгоритми побудовані на правилах використання резервів часу некритичних операцій.