Lab_1_IL
.pdf
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ ІНСТИТУТ КОМПЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ
ТЕХНОЛОГІЙ ПРИ НАЦІОНАЛЬНОМУ УНІВЕРСИТЕТІ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД КРИТИЧНОГО ШЛЯХУ МЕТОДИЧНІ ВКАЗІВКИ
МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи
з курсу “Інформаційна логістика” для студентів базового напрямку “Комп’ютерні науки” спеціальності
“Інтелектуальні системи прийняття рішень”(7.080.404)
Затверджено На засіданні кафедри “Інформаційних систем та мереж” Протокол №14 від 25.10.2008 р.
Львів 2008
Метод критичного шляху методичні вказівки:. Методичні вказівки до виконання лабораторної роботи/ Укл.: Я. П. Кісь.– Львів: Кафедра “Інформаційних систем та мереж” Інститут комп’ютерних наук та інформаційних технологій при Національному університеті “Львівська політехніка”, 2008.-00с.
Укладачі |
Кісь Я. П., канд. техн. наук, доц. |
Відповідальний |
|
за випуск |
Пасічник В. В. докт. техн. наук, проф. |
Рецензенти: Катренко А. В., канд. екон. наук, доц. Якушев В. С., канд. техн. наук, доц.
Хід роботи
1.Отримати завдання в викладача.
2.Порахувати найбільш ранні та найбільш пізні терміни подій.
3.Порахувати резерв часу для кожної роботи.
4.Знайти критичний шлях для свого варіанту завдання (послідовність подій, для яких резерв часу рівний нулю).
Зміст звіту
1.Короткі теоретичні відомості.
2.Записати результати отримані в ході роботи.
3.Намалювати мережевий графік робіт з критичним шляхом.
4.Проінтерпретувати отримані результати.
5.Висновки.
Література
1.Катренко А. В. "Дослідження операцій".
2."Программные методы и средства планирования и управления проектами" Богданов Д. В., Казанцев О. В., Санкт-Петербургское высшее училище радио-електроники ПВО.
3.Schedule Risk Analysis Simplified by David T. Hewlett, Ph. D.
4.PERT, СPМ and GANTТ раssage from "A рprofessional’s Guide to Systems Analysis". Martin E. Model, 2nd. EDITION МсGrаw HILL 1996.
Мета роботи: Мета лабораторної роботи полягає у практичному засвоєнні методу критичного шляху (МКШ).
Теоретичні відомості
В повсякденному житті люди часто зіштовхуються з задачами планування різноманітних по своєму змісту робіт, процес виконання яких не можна відобразити у формальних залежностях. Прикладами тут можуть бути роботи, пов'язані з будівництвом великого промислового підприємства, створенням розгалуженої мережі обчислювальних центрів, розробкою складної науково-дослідної теми і взагалі реалізацією будьяких широкомасштабних проектів.
Характерна особливість кожного такого проекту - взаємна обумовленість робіт, що поводяться, висловлена в вимозі дотримуватися певного порядку і певних «правил» їхнього виробництва. Так. при створенні мережі ВЦ монтаж обчислювальної техніки можна почати лише після того, як будуть підготовані потрібні приміщення, що, в свою чергу, будуть побудовані (або орендовані) в місцях, вибраних в результаті попереднього аналізу варіантів мережевої структури і і. д. Отже, підготовка рішень в розглядуваних умовах повинна проводитися з урахуванням багатьох чинників, що відбивають обмеженість сировинних, грошових, енергетичних ресурсів, а також часу, що відводиться на передбачувані роботи.
При спробах здійснити тон або інший великий проект звичайно виникають різноманітні питання, наприклад, «в які моменти прочитані і закінчувати окремі роботи?», «як розподілити між ними наявні матеріальні ресурси?», «які перешкоди можуть, зустрітися на шляху до досягнення поставленої мети?», «як зміняться параметри плану в випадку не передбачуваних затримок» і т. д. Відповіді на них можна намагатися отримати з міркувань «ЗДОРОВОГО ГЛУЗДУ» (передусім тоді, коли кількість і обсяги робіт, що проводяться є невеликими), однак в загальному випадку такий підхід перетворюється у вгадування рішень і призводить в кінцевому результаті до матеріальних втрат, порушень встановлених термінів, моральних витрат. Виникає необхідність в спеціальних розрахунках, що дозволяють обґрунтовано вибирати стратегію поведінки до обстановки .
Після прийняття рішення про початок робіт над проектом звичайнонеобхідно вирішити задачу завершення проекту (скласти графік виконання) за заданий час з використанням виділених ресурсів. Для рішення цієї задачі в період 1956 - 1958 рр. були розроблені два методи. Один з них - метод китичного шляху, або МКШ {Сcritical Path МеtodСPM), який вперше був використаний компанією Dupont Со. І отримав подальший розвиток в роботах фірми Маuchlу Аssoсіаtеs. Інший засіб - метод оцінки і перегляду проектів, або ПЕРТ (Prоjес Evaluation AND Review Тесhniquе PERT), - був розроблений для міністерства військово-морських
сил США в відповідності з програмою створення підводних човнів, оснащених ракетами «Поляріс». Характерним для цих засобів є зображення проектів у вигляді мережі взаємозв’язаних робіт. В нинішній час створене велике число модифікацій та друга генерація мережевих методів.
Планування дій.
Деякі дії не можуть починатися , доки інші дії не завершені. Наприклад ми не можемо починати будувати новий інтер'єр у Ермітажі, доки старий не буде видалений. Старий інтер'єр не може бути видалений, доки зовнішні стіни, які потрібно зберегти не укріпленими, тощо.
Якщо б всі дії, які складають проект повинні б були виконуватись у певній послідовності, то б час виконання всього проекту можна було б обчислити простим сумуванням тривалості всіх дій, що його складають. Але у реальності все набагато складніше і часто деякі дії можуть виконуватись одночасно, послідовність цих дій можна зобразити, малюючи мережу зв'язків і вузлів. Приклади постановки задачі за допомогою мережевих графіків.
Пр. № 1
|
|
|
|
2 |
E |
|
|
|
|
|
D |
|
|
||
|
|
|
3 |
|
2 |
|
|
|
|
|
|
|
|
||
S |
A |
1 |
B |
3 |
C |
E |
|
2 |
1 |
1 |
|||||
|
|
|
|
||||
|
|
|
F |
|
G |
|
|
|
|
|
2 |
4 |
1 |
|
|
|
|
|
|
|
|
Цифрами позначаються ключові точки проекту (вузли ). S - початок проекту, E - кінець проекту. Стрілками позначаються дії: латиські букви над стрілками назва дії, цифри під стрілками тривалість дії.
|
2 |
17 |
|
7 |
|
|
|
||
15 |
|
6 |
5 |
|
|
|
4 |
6 |
6 |
|
8 |
|
||
|
|
|
|
|
1 |
|
|
4 |
|
|
|
|
|
2 |
10 |
3 |
|
5 |
|
|
4 |
|
||
|
|
|
|
В даному випадку вузли позначаються цифрами, при чому, як видно з малюнку вузол №1 - вихідна точка, а вузол № 2 кінцева точка проекту. Події в даному випадку позначаються номерами вузлів. Наприклад подія, що починається у вузлі № 1 і закінчується у вузлі № 2 має назву подія 1-2. Тривалість подій пишеться над стрілками.
2. Формальна постановка задачі:
Нехай ми маємо заданий мережевий графік проекту у вигляді
графа G(N, A) . Де: |
N |
- множина вузлів, множина подій. |
|
A |
- множина дуг, множина робіт, що з'єднують події. |
||
di |
- місце на вісі часу події i . |
||
ij |
- довжина роботи (i, j) . Вона обчислюється за формулою: |
||
|
|
|
ij d j di |
N {X1 , X 2 , X 3 ,..., X k }
X 1 - початкова (вихідна) подія. X k - кінцева подія.
Тоді ми повинні знайти таку підмножину робіт B C , для якої справедливо відношення:
B {(i, j) |
( ij |
0)^ (i, j) A} |
де ij - резерв часу роботи (i, j) . Він обчислюється за формулою:
ij t j ti ij
Також можна казати, що критичний шлях проходить через події, для яких резерв часу (Rj ,0)
|
|
|
Rj t j ti |
|
|
|
Де |
t j - найбільш ранній з можливих термінів запланованої |
|||
події X визначається максимумом довжини шляхів, |
що зв'язують це |
||||
X j |
, з початком X 1 : |
|
|
|
|
|
|
|
t j MAX(ti ij ), (i, j) A |
|
|
найбільш ранні терміни подій прораховуються від початкової події X 1 . |
|||||
|
|
|
ti 0 |
|
|
ti |
- найбільш |
пізній з |
допустимих |
термінів події |
X i .: Визначається |
різницею між |
довжиною |
T 0 критичного шляху і мінімумом довжини |
|||
шляхів, що зв’язують X i |
з кінцевим X k |
: |
|
||
|
|
|
t1 MIN(t j |
ij ) |
|
найбільш ранні терміни подій прораховуються в напрямку від кінцевої події X k до початкової X 1 .
При чому:
tкінцев е tкінцев е
Ця множина робіт В буде множиною робіт, що складають критичний шлях проекту.
Отже, підсумуємо все вищесказане.
Критичний шлях в мережі проекту проходить через події, резерв часу для яких рівний 0. Ніяка робота з числа з числа тих, що знаходиться на критичному шляху не може бути подовжена, тому що проведе до
відповідного зростання тривалості виконання проекту загалом. Скорочення критичною шляху приводить до термінів виконання проекту, але при цьому може з'явитися інший критичний шлях і надалі буде необхідно скорочувати всі критичні шляхи.
Контрольний приклад.
Нехай ми маємо такий мережений графік:
|
|
|
2 |
3 |
5 |
|
4 |
|
|
|
|
|
|||
|
|
|
|
|
7 |
|
|
|
3 |
|
0 |
|
|
7 |
|
|
|
|
|
|
|
||
|
|
|
|
|
0 |
|
5 |
|
|
|
|
|
|
|
|
1 |
|
6 |
3 |
12 |
|
4 |
|
|
|
|
|
||||
|
|
|
6 |
10 |
|||
|
|
|
|
|
|
||
|
|
2 |
|
|
0 |
|
1 |
|
|
|
|
|
|
||
|
|
|
|
8 |
15 |
9 |
|
|
|
|
4 |
8 |
|
|
|
|
|
|
|
|
|
1. Підраховуємо найбільш ранні з можливих термінів здійснення подій. Як ми знаємо для початкової події t1 0 . Отже
t2 |
MAX{0 3} 3, t3 MAX{0 6} 6, |
t4 MAX{0 2} 2 . |
|
t5 |
MAX{t2 |
3, t3 0} MAX{3 3,6 0} 6, |
|
t8 |
MAX{t4 |
8} MAX{2 8} 10, |
|
t6 |
MAX{t3 |
12, t4 8} 18, |
|
t7 |
MAX{t5 |
7, t6 0} MAX{6 7,18 0} 18, |
|
t9 |
MAX{t8 |
15} MAX{10 15} 25, |
|
t10 MAX{t9 1, t6 4, t5 4,.t7 5} MAX{25 1,18 4,6 4,18 5} 26
2. |
Підраховуємо найбільш пізні з допустимих термінів |
|||
|
подій: |
|
|
|
Як ми знаємо |
|
|||
t10 t10 26 |
|
|||
t9 |
MIN{t10 |
1} 25, |
||
t7 |
MIN{t10 |
5} 21, |
||
t6 |
MIN{t10 |
4, t7 |
0} 21, |
|
t5 |
MIN{t10 |
4, t7 |
7} 14, |
|
t8 |
MIN{t9 |
15, t6 |
0} 10, |
|
t3 |
MIN{t5 |
0, t6 0} 12, |
||
t4 |
MIN{t8 |
|
8} 2, |
|
t2 |
MIN{t5 |
|
3} 11, |
|
t1 |
MIN{t2 |
3, t3 5, t4 2} 0 |
||
3. Підраховуємо |
резерви часу для кожної з подій по |
формулі: Rj t j |
t j |
R1 t1 t1 0, R2 t2 t2 8, R3 t3 t3 3, R4 t4 t4 0, R5 t5 t5 8, R6 t6 t6 3,
R7 t7 t7 3, R8 t8 t8 0, R9 t9 t9 0, R10 t10 t10 0.
4. Ми знайшли критичний шлях він проходить через події для яких резерв часу R,0 {1,4,8,9,10} Критичний шлях на мережевому графіку відображається товстою лінією:
|
2 |
3 |
5 |
|
|
4 |
|
|
|
7 |
|||
|
|
|
|
|
|
|
3 |
|
0 |
|
|
7 |
|
|
|
|
|
|
||
|
|
|
|
0 |
|
5 |
|
|
|
|
|
|
|
6 |
3 |
12 |
|
|
4 |
|
1 |
|
6 |
|
10 |
||
|
|
|
|
|
||
2 |
|
|
0 |
|
|
1 |
|
|
|
15 |
|
||
|
|
8 |
|
|
|
|
|
4 |
8 |
|
9 |
|
|
|
|
|
|
|
Варіанти завдань:
1.
|
|
2 |
0 |
5 |
|
|
9 |
|
|
|
|
6 |
|||
|
|
|
|
|
|
|
|
|
6 |
|
2 |
|
|
7 |
|
|
|
|
|
|
|
||
|
|
|
|
|
0 |
|
4 |
|
|
|
|
|
|
|
|
1 |
6 |
3 |
|
8 |
|
4 |
|
|
|
|
|
||||
|
|
6 |
|
9 |
|||
|
|
|
|
|
|
||
|
2 |
|
|
|
|
|
2 |
|
|
4 |
|
4 |
|
8 |
|
|
|
|
|
|
|
2.
3.
4.
|
|
2 |
|
6 |
|
1 |
2 |
3 |
|
||
|
3 |
|
|
|
4 |
|
|
2 |
|
6 |
|
1 |
7 |
3 |
|
||
|
3 |
|
|
|
4 |
|
|
2 |
|
6 |
|
1 |
1 |
3 |
|
||
|
3 |
|
|
|
4 |
0 |
5 |
|
|
|
|
1 |
|
|
2 |
|
|
4 |
|
7 |
|
|
0 |
|
8 |
|
|
|
|
|
8 |
4 |
|
|
6 |
9 |
|
|
|
||
|
|
|
2 |
6 |
8 |
|
0 |
5 |
|
|
|
5 |
|
|
|
|
||
|
|
|
1 |
|
|
|
|
|
|
|
|
4 |
|
|
|
7 |
|
|
|
0 |
|
|
8 |
|
|
|
|
|
|
|
8 |
|
|
12 |
|
|
6 |
|
|
9 |
|
|
|
|
|
||
|
|
|
|
8 |
|
1 |
8 |
|
2 |
5 |
|
|
|
5 |
|
|
|
|
||
|
|
|
2 |
|
|
|
|
|
|
|
|
2 |
|
|
|
7 |
|
|
|
0 |
|
|
12 |
|
|
|
|
|
|
|
6 |
|
|
12 |
|
|
6 |
|
|
9 |
|
|
|
|
|
||
0 |
|
|
|
8 |
|
|
|
|
|
|
1 |
8 |
|
5.
6.
7.
8.
|
|
2 |
4 |
5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
5 |
|
|
1 |
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
11 |
|
|
|
|
|
|
|
|
1 |
1 |
3 |
|
6 |
|
6 |
|
|
|
|
|
||||
|
|
6 |
|
9 |
|||
|
|
|
|
|
|
||
|
4 |
|
0 |
|
|
|
8 |
|
|
|
|
|
|
||
|
|
4 |
|
3 |
|
8 |
|
|
|
|
|
|
|
|
|
2 |
4 |
5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
5 |
|
|
|
1 |
|
|
8 |
|
8 |
|
|
|
|
|
|
|
||
|
|
|
|
6 |
|
|
|
|
|
1 |
|
|
0 |
|
11 |
|
|
|
|
|
|
|
|
1 |
1 |
3 |
|
6 |
|
|
|
|
|
|
6 |
|
|||
|
|
|
|
7 |
|
10 |
|
|
|
|
|
|
|
||
|
4 |
|
0 |
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
4 |
|
3 |
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
2 |
1 |
5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
|
|
4 |
|
|
4 |
|
8 |
|
|
|
|
|
|
|
||
|
|
|
|
6 |
|
|
|
|
|
1 |
|
|
0 |
|
11 |
|
|
|
|
|
|
|
|
1 |
3 |
3 |
|
6 |
|
|
|
|
|
|
6 |
|
|||
|
|
|
|
7 |
|
10 |
|
|
|
|
|
|
|
||
|
6 |
|
0 |
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
4 |
|
3 |
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
2 |
1 |
5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
|
|
5 |
|
|
7 |
|
8 |
|
|
|
|
|
|
|
||
|
|
|
|
6 |
|
|
|
|
|
1 |
|
|
0 |
|
21 |
|
|
|
|
|
|
|
|
1 |
5 |
3 |
|
6 |
|
|
|
|
|
|
12 |
|
|||
|
|
|
|
7 |
|
10 |
|
|
|
|
|
|
|
||
|
6 |
|
0 |
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
4 |
|
7 |
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|