85. Види логічних зв’язків у сітьових графіках. Система pert.

Елементи сітьового графіку

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

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

Головними елементами сітьового графіку є роботи таподії.

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

У сітьовому графіку можуть бути декілька різновидностей робіт: дійсна робота; очікування; фіктивна робота. Дійсною є робота, яка вимагає витрат часу і ресурсів (наприклад, виготовлення вузла машини, складання програми для ПК тощо). Фіктивна робота відображує логічний зв'язок між роботами і не вимагає витрат часу і ресурсів (наприклад, передача креслень від конструкторського бюро до цеху для виготовлення деталі, передача програми для ПК оператору з метою вводу її в оперативну пам'ять та наступного коректування і т.ін.). Очікуванням називається робота, яка потребує витрат часу, але не потребує витрат ресурсів (наприклад, процес затвердіння бетону, дозрівання вражаю тощо).

Дійсні роботи та очікування зображаються на графіку безперервними лініями; фіктивні роботи - пунктирними лініями; кількісні показники робіт (час) проставляються цифрами над стрілками (рис. 4.1).

П одії являють собою момент звершення роботи; вони позначаються на сітьовому графіку кружками, усередені кружка - номер події (див. рис.4.1).

Розрізняють попередні події для даної роботи і та послідовні події /. Робота між подіями і та і позначається як (і,і).

Подія у графіку, яка відображує начало комплексу робіт, називається восхідною І (подія 1 на рис. 4.1). Подія, яка відображує кінцеву мету комплексу робіт, називається завершувальною С (подія 7 на рис.4.1).

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

85. Методологія обчислення параметрів сітьового графіка.

Правила побудови сітьового графіка  1. Сітьовий графік повинен чітко відображати логічний взаємозв’язок і поступовість усіх подій.  2. Графік має бути по можливості симетричним, не заплутаним.  3. Бажано, щоб стрілки робіт на графіку не перехрещувалися й мали переважно напрям зліва направо.  4. Кожна подія й робота повинні зустрічатися на сітьовому графіку лише один раз.  5. Номери подій біля засади стрілок робіт мусять бути меншими, ніж біля вістря.  6. Якщо між двома подіями необхідно показати дві (чи більше) паралельно виконані роботи, треба ввести додаткову подію й фіктивну роботу.  7. На сітьовому графіку не повинно бути подій (за винятком початкової), в які не входила б одна чи кілька робіт.  8. На сітьовому графіку не повинно бути замкнених контурів.  3). Правила упорядкування нумерації подій  Після побудови й перевірки сітьового графіка упорядковують нумерацію подій. Цього можна досягти, використовуючи метод викреслення дуг, який дає змогу розподілити усі події сітьового графіка за рангами.  Події нумерують у такому порядку:  - початковій події сітьового графіка дають порядковий номер 0 (чи 1);  - викреслюють дугою усі роботи, які виходять з початкової події, наступний порядковий номер вказують згори вниз за годинниковою стрілкою тієї події, з якої роботи тільки виходять, а всі, які входять, викреслені;  - викреслюють дугою всі роботи, які виходять з наступного порядкового номера події, а номери вказують у тій самій послідовності, як з початкової події. Так продовжують до надання номера завершальній події сітьового графіка.  4). Розрахунок головних параметрів сітьового графіка  До головних параметрів сітьового графіка належать ранні й пізні строки здійснення подій, резерви часу подій і робіт, довжина критичного шляху.  Для розрахунку параметрів сітьового графіка зручно користуватися чотирьохсекторним способом, при якому розрахунок раннього і пізнього термінів завершення подій, а також резерву часу подій виконуються безпосередньо на графіку. При цьому кожне коло-подію розбивають на чотири сектори.  У верхньому секторі записують порядковий номер події, у лівому – ранній строк настання події, у правому – пізній строк, у нижньому – резерв часу події.  Ранній строк настання події Tp(i) являє собою час, необхідний для виконання усіх робіт, які передують даній події.  Для визначення величини Tp(i) треба до даного строку кожної з подій Tp(к), які безпосередньо передують даній, додати тривалість відповідної роботи й залишити максимальне з одержаних значень (рис.1). 

Tp(i)= [Tp(k) + t(к,і)]маx (1.1)  t(k,i) t(i,j)  Рис.1. Умовні зображення подій і робіт  При розрахунку треба рухатись від події до події за напрямом стрілок робіт. Розрахунок ранніх термінів здійснення подій слід починати з початкової події.  Пізній термін Tn(i) являє собою такий час завершення події, перевищення якого викличе затримку настання завершальної події. Для визначення величини Tn(i) необхідно з пізнього терміну кожної з подій Tn(j), що йдуть безпосередньо за даною подією, відняти тривалість відповідної роботи t(і,j) й залишити мінімальне із заданих значень:  Tn(i) = min [Tn(j) – t(i,j) ] (1.)  Розрахунок пізніх термінів починають із завершальної події, для якої пізній термін здійснення збігається із значенням раннього терміну. При розрахунку треба лічити від події до події проти стрілок робіт.  Для подій критичного шляху Tp(i)=Tn(i); для всіх інших подій  Tp(i) < Tn(i).  Резерв часу події являє собою різницю між пізнім і раннім строками здійснення події:  R(i) = Tn(i) - Tp(i). (1.)  Знаючи ранні й пізні здійснення усіх подій сітьового графіка, можна для будь якої роботи і, j визначити:  - найбільш ранній з можливих строків початку роботи  Tpп(i,j) = Tp(i) (1.4)  - найбільш ранній з можливих з строків закінчення роботи  Tpз(i,j ) = Tp(i) + t(i,j) (1.5)  - найбільш пізній з допустимих строків початку роботи  Tnn(i,j) = Tn(j) - t(i,j) (1.6)  - найбільш пізній з допустимих строків закінчення роботи  Tпз (i,j) = Tn(j). (1.7)  Повний резерв часу роботи R п(i,j) показує, на скільки може бути збільшена тривалість виконання роботи без збільшення тривалості критичного шляху:  R n(i,j) = Tn(j) – Tp(i) – t (i,j) (1.   Вільний резерв часу роботи Rв(i,j) показує максимальний час, на який можна відкласти початок або збільшити тривалість роботи за умови, що всі попередні й наступні для даної роботи події сітьового графіка настануть у свої ранні строки:  R в(i,j) = Tр(j) – Tр(i) – t (i,j) (1.9)