Мережевий граф та його графік

Сучасна теорія управління виробництвом, спеціалізація окремих галузей виробництва, багатопрофільність звязків виробництва широко використовують один з математичних апаратів – метод планування і управління мережами (ПУМ).

Основою методу ПУМ є теорія графів, яка дає можливість створити мережевий граф (МГ).

Означення 1. Довільний спланований комплекс робіт, необхідних для досягнення певної мети, називають проектом.

Можна говорити про комплекс робіт (або справ), запланованих на день, на тиждень, на місяць, на рік.

Проект (або комплекс робіт) розчленовується на окремі роботи.

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

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

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

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

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

В МГ виділяють дві вершини: V₁, яка є початком, і V _n, що є з авершенням усього проекту, всі інші вершини називають проміжними.

В основі побудови мережевого графіка лежать три основні поняття: робота, подія і шлях.

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

Термін «робота» в мережевому плануванні використовується в широкому сенсі. Під роботою тут розуміється:

1. Дійсна робота – будь-який трудовий процес, що вимагає витрат праці, часу і матеріальних ресурсів

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

3. Фіктивна робота – суто умовна залежність між подіями, що вводиться тільки для зручності зображення мережі. Фіктивна робота не пов'язана з витратою праці, часу і ресурсів.

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

Під «подією» в мережевому плануванні розуміють:

1. Початкова подія – початок виконання проекту. Початкова подія не має попередніх робіт.

2. Завершальна подія – досягнення кінцевої мети проекту (або однієї з кінцевих цілей). Завершальна подія не має наступних за нею робіт.

3. Проміжна подія (підсумок якоїсь діяльності) – результат виконання однієї або кількох робіт, що дозволяє приступити до виконання наступних робіт.

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

Операція – це сама робота або дія.

Будь-яка стрілка на мережевому графіку з'єднує тільки дві вершини і відображає процес переходу від однієї події до іншої. Тому будь-яка робота може бути зашифрована парою чисел < i; j >, які відповідають попередній і подальшій подіям.

Означення 4. Час, необхідний для виконання роботи <i; j> називають

тривалістю роботи і позначають t_ij. Позначення проставляють над відповідною стрілкою.

Тривалість виконання роботи вимірюється в одиницях часу: годинах, днях, тижнях і т.д.

На рис. 1.21 наведений мережевий графік деякого комплексу робіт. Над стрілками проставлено час виконання кожної з робіт.

Поиск по сайту: