Меню
Головна
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Правила побудови сіткових моделей

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

1. Події правильно пронумеровані, тобто для кожної роботи (i,j) i<j. При невиконанні цієї вимоги необхідно використовувати алгоритм перенумерації подій, який полягає в наступному:

- нумерація подій починається з вихідного події, яким присвоюється № 1;

- з вихідного події викреслюють всі витікаючі з нього роботи (стрілки) і на решті мережі знаходять подія, в яке не входить жодна робота, йому і привласнюють № 2;

- потім викреслюються роботи, що виходять з події № 2, і знову знаходять подія, в яке не входить жодна робота, і йому присвоюють № 3, і так продовжується до завершального події, номер якого повинен бути дорівнює кількості подій в мережевому графіку;

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

2. Відсутні тупикові події (крім завершального), тобто такі, за якими не слід хоча б одна робота.

3. Відсутні події (за винятком початкового), яким не передує хоча б одна робота.

4. Відсутні цикли, тобто замкнуті шляхи, що з'єднують подія з ним же самим.

Більш докладно ці вимоги описані, наприклад, в [13], [17]. При невиконанні зазначених вимог не має сенсу приступати до обчислень характеристик подій, робіт і критичного шляху.

Розрахунок характеристик мережевих моделей

Для подій розраховують три основні характеристики: ранній і пізній термін здійснення події, а також його резерв.

Ранній термін звершення події tр визначається величиною найбільш тривалого відрізку шляху від початкового до розглянутого події, причому tр(1) = 0, a tp(N) = tкр (Lкр)

(3.46)

Пізній термін звершення події tп характеризує пізній припустимий термін, до якого має відбуватися подія, не викликаючи при цьому зриву терміну звершення кінцевого події:

(3.47)

Цей показник визначається "зворотним ходом", починаючи з завершального події, з урахуванням співвідношення tn(N) = tр(N).

Всі події, за винятком подій, що належать критичному шляху, мають резерв R(i):

(3.48)

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

Для всіх робіт (i,j) на основі ранніх і пізніх термінів звершення подій можна визначити наступні показники (тут і в подальшому, де це доцільно для спрощення записів всі підрядкові символи замінюються малими):

Ранній термін початку - , (3.49)

Ранній термін закінчення - , (3.50)

Пізній термін закінчення - , (3.51)

Пізній термін початку - , (3.52)

Повний резерв часу - , (3.53)

Незалежний резерв часу -

(3.54)

або

(3.55)

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

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

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

Названі вище характеристики СМ можуть бути отримані на основі аналітичних формул (3.46)-(3.55), а процес обчислень відображається на самому графіку СМ, або у матриці розмірності N x N, або в таблиці. Розглянемо алгоритми табличного методу розрахунку мережного графіка на конкретному прикладі розв'язання задачі організації праці при реалізації певного проекту.

Приклад 3.11. Нехай реалізується проект щодо будівництва АЗС, при цьому залучаються робітники можуть виконувати будь-яку з виділених за прийнятою технологією робіт. Менеджер проекту встановив, що в даному проекті від початку до завершення робіт можна виділити 5 подій, і існують 6 різних видів робіт, що пов'язують ці події. При первинному розподілі робочих за видами робіт за наявними нормативами трудомісткості були розраховані тривалості виконання робіт (у днях), таким чином, мережевий графік реалізації даного проекту має вигляд моделі, представленої на рис. 3.7.

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

Розглянемо етапи табличного методу розрахунку даної мережевої моделі; результати розрахунку наведені в табл. 3.17 у графах 1-9.

Етап 1. Перелік робіт та їх тривалість запишемо у другу і третю графи табл. 3.17, при цьому роботи записуються послідовно в гр. 2: спершу починаються з номера 1, потім з кімнати 2 і т. д.

Етап 2. У першій графі поставимо число Допр, що показує кількість робіт, безпосередньо передують події i, з якого починається розглянута робота. Для робіт, що починаються з номера 1, попередніх робіт немає (Допр = 0). Для роботи, що починається на номер kпроглядаються всі верхні рядки другої графи і відшукуються роботи, що закінчуються на цей номер k. Кількість знайдених робіт записується в першу графу у всі рядки, які відповідають роботам, що починаються з номера k. Наприклад, для роботи (4, 5) в графу 1 поставимо цифру 2, так як на номер 4 закінчуються дві роботи: (1,4) і (3,4).

Таблиця 3.17

Kпр

(i, j)

t(i, j)

tpн(i, j) = tp(i, j)

tpo(i, j)

tпн(i, j)

tпо(i, j) = tп(i, j)

Rп

Rн

Дон

1

2

3

4

5 = 4 + 3

6 = 7 - 3

7

8

9

10

0

(1,2)

6

0

6

0

6

0

0

0,71

0

(1,3)

0

0

Е

0

0

0

0

1

0

(1,4)

8

0

8

9

17

9

9

0,47

1

(2,5)

9

6

15

12

21

6

0

0,71

1

(3,4)

12

0

17

0

17

0

0

1

2

(4,5)

4

17

21

17

21

0

0

1

Етап 3. Заповнення таблиці починається з розрахунку раннього терміну робіт tp(i). Для робіт, що мають цифру "нуль" у першій графі, у графі 4 також заносяться нулі і розраховуються відповідні значення графи 5 (ранній термін закінчення як суми відповідних чисел у графі 4 і графі 3 (див. формулу (3.51)). В нашій моделі таких робіт три; у першому рядку графи 5 ставимо 0 + 6 = 6, аналогічно по другій і третій рядку.

Для заповнення таких рядків графи 4 для робіт (i,j) проглядаються заповнені рядки графи 5, містять роботи, що закінчуються на номер i, і максимальне із знайдених значень (якщо їх декілька) переноситься в графу 4 для оброблюваних рядків. Так, у нашому прикладі у четвертому рядку в графі 4 ставимо 6, а в графі 5 - 15 (6 + 9 = 15). Аналогічно в п'ятому рядку в графі 4 і графі 5 ставимо відповідно 5 і 17 (5 + 12 = 17). В останній шостий рядок у графі 4 ставимо 17 (найбільше з чисел 8 і 17-у графі 5) і відповідно у графу 5 ставимо 21 (17 + 4 = 21).

Етап 4. Графи 7 і 6 заповнюються "зворотним ходом", тобто знизу вгору. Для цього проглядаються рядка (роботи), що закінчуються на номер N останнього події, і з графи 5 вибирається максимальна величина; ця величина записується в графу 7 за всіма рядками, що закінчуються на N (див. формулу (3.51)), з урахуванням рівності tп (N) = tp(N). Потім заповнюється графа 6 за цими рядками як різниця між графою 7 та графою 3 (див. формулу (3.52)). У нашому прикладі таких рядків дві (четверта і шоста), для яких в графі 5 стоять числа 15 і 21; вибираємо найбільшу з них (21) і записуємо його в графу 7 по цих рядках, після чого заносимо відповідні числа в графу 6.

Далі проглядаються рядка, що закінчуються на номер події, що передує завершального, тобто на (N - 1). Для цих рядків проглядаються всі рядки графи 6, що лежать нижче і починаються з номера (N - 1); серед них у графі 6 вибирається мінімальна величина, яка переноситься у графу 7 по оброблюваним рядками, після чого заповнюється графа 6. У нашому прикладі таких рядків дві (третя і п'ята); нижче їх з номера 4 починається одна (остання) робота, і в графі 6 коштує 17, отже, у графі 7 за цими рядками ставимо число 17, після чого заповнюється графа 6.

Потім аналогічний процес повторюється для рядків, що закінчуються на (N - 2), (N - 3) і т. д. до тих пір, поки не будуть заповнені всі рядки по графи 7 і 6. У нашому прикладі результати наведені у відповідних графах табл. 3.17.

Етап 5. Показники графи 8 розраховуються як різниці відповідних показників граф 6 і 4 або граф 7 і 5 (див. формули (3.48) або (3.53)). Щоб заповнити графу 9, можна попередньо розрахувати резерви часу кожної події за формулою (3.48), а потім скористатися формулою (3.55). У нашому прикладі резерви часу для кожного з п'яти подій дорівнюють відповідно: R(1) = 0; R(2) = 12 - 6 = 6; R(3) = 5 - 5 = 0; R(4) = 17 - 17 = 0; R(5) = 0. Подальші результати по формулі (3.55) наведені в графі 9 табл. 3.17.

Етап 6. На цьому етапі підводяться основні підсумки розрахунку. Враховуючи, що нульовий резерв часу мають тільки роботи (Rп = 0) і події (R(i) = 0), які належать критичного шляху, отримуємо, що критичним є шлях LKp = (1, 3, 4, 5), тривалість якого (tкр) дорівнює 21 дня. Так як роботи(1, 2), (1, 4) і (2, 5) мають нульові резерви Rп, то очевидно, що шляхом перекладу деякого числа робітників з цих робіт на роботи, що належать критичного шляху, можна скоротити тривалість цього шляху і тим самим скоротити терміни виконання проекту в цілому, тобто здійснити оптимізацію сіткового графіка.