Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Резерви часу робіт
|
|
Практично необхідно знати резерви часу для виконання кожної роботи. Аналіз цих резервів допомагає ефективно розподілити ресурси між роботами. При цьому розрізняють наступні види резервів часу для роботи i-j:
· повний;
· незалежний;
· частковий I роду;
· частковий II роду.
Повним резервом часу роботи i-j, що позначається Rn(i, j), називається величина:
. (10)
Легко бачити, що повний резерв часу визначається як резерв часу того максимального шляху 
який веде від початку графіка до його кінця через дану роботу i-j. Він показує допустиме збільшення тривалості роботи (або запізнювання її початку), при якому довжина максимального зі шляхів, що проходять через цю роботу, не перевищить тривалості критичного шляху.
Дійсно, максимальний шлях полягає, очевидно, з трьох ділянок:
а) ділянки 
;
б) роботи i-j;
в) ділянки 
, тому
Отже, повний резерв часу роботи i-j можна перетворити як
Звідси витікає, що повний резерв часу для будь-якої роботи завжди ненегативний: Rn(i, j)≥ 0. Причому він рівний нулю тоді й тільки тоді, коли робота i-j лежить на критичному шляху: Rn(i, j)= 0 для 
. При використанні цього резерву максимальний шлях, що проходить через роботу i-j, стає критичним, і всі роботи, які складають цей шлях, втрачають резерви часу.
Надалі називатимемо роботу критичною, якщо повний резерв часу для неї рівний 0; якщо ж повний резерв часу для роботи – позитивний, то називатимемо її некритичною. Тобто критична робота – це робота, яка лежить на одному з критичних шляхів, а некритична – це робота, яка не лежить ні на одному з критичних шляхів.
Розглядаючи некритичну роботу i-j, можна за її повним резервом Rn(i, j) судити про те, який найбільший відрізок часу ми маємо в своєму розпорядженні для збільшення тривалості й, відповідно, зменшення продуктивності її виконання (або з яким найбільшим запізненням проти мінімально можливого терміну 
можна почати цю роботу), не збільшуючи критичного часу, тобто не зриваючи термін завершення всього комплексу робіт. Проте, слід мати на увазі, що якщо на якій-небудь некритичній роботі i-j, вичерпати час її повного резерву Rn(i, j), то максимальний шлях , який проходить через цю роботу, перетворитися на критичний шлях, і некритичні роботи стануть критичними.
Відзначимо, нарешті, що повним резервом часу роботи дійсно можна розпоряджатися тільки в тому випадку, якщо всі роботи, що входять в початкову подію 
цієї роботи, закінчуються в найбільш ранній з можливих термінів і за умовою, що всі роботи, що виходять з кінцевої події 
, будуть початі в найбільш пізній з допустимих термінів 
.
Можна поставити перед собою зворотне завдання: всі роботи, що входять в початкову подію 
, закінчити до найбільш пізнього з допустимих термінів 
і в той же час почати всі роботи, які витікають з кінцевої події 
, у найбільш ранній з можливих термінів 
. Проте, це завдання не завжди здійсниме. Дійсно, для здійснення такої ситуації потрібно, щоб тривалість 
роботи i-j укладалася в наданий умовою завдання проміжок часу 
, тобто, щоб виконувалася нерівність 
або
(11)
що, як видно, не завжди має місце. Якщо для роботи нерівність (11) виконується, то говорять, що ця робота має незалежний резерв часу, що виражається числом 
. Якщо ця величина 
то незалежний резерв часу роботи, який позначатимемо 
, вважається рівним 0.
Отже, незалежний резерв часу роботи - це величина
, (12)
яка утворюється лише у деяких робіт і показує максимальний час, на який можна збільшити тривалість роботи (або відстрочити її початок) між крайніми термінами звершення її початкової та кінцевої подій. Використання незалежного резерву у будь-якому випадку не зачіпає резервів часу інших робіт.
Як ми вже знаємо, для всіх критичних робіт повний резерв завжди рівний 0; незалежний же резерв для критичних робіт тим більше завжди рівний 0, оскільки завжди 
. Для некритичних робіт повний резерв часу завжди позитивний, а незалежний резерв часу може бути рівний нулю.
Щоб визначити сенс понять часткових резервів часу (I і II роду), що вводяться далі, відзначимо знову такі властивості повного і незалежного резервів часу:
· використання повного резерву часу якої-небудь роботи позбавляє резервів часу як всі роботи, що входять в дану, так і всі роботи, які витікають з неї;
· використання незалежного резерву часу якої-небудь роботи не позбавляє резервів часу як роботи, що входять в дану, так і роботи, які витікають з неї.
Тепер визначимо такий резерв, який позбавляє резервів часу роботи, які витікають з даної, але не позбавляє резервів часу роботи, що входять в дану роботу, а також такий резерв, який позбавляє резервів часу роботи, що входять в дану, але не позбавляє резервів часу роботи, які з неї витікають. Для цього введемо поняття часткових резервів I і II роду.
Частковий резервом часу I роду називається величина
. (13)
Частковий резервом часу II роду називається величина
. (14)
Розглядаючи вираз для часткового резерву часу I роду, переконуємося, що його використання дійсно не впливає на резерви попередніх (що входять) робіт, оскільки дозволяє здійснити кінцеву для них подію 
у найбільш пізній термін 
, але впливає на резерви подальших (які витікають) робіт, оскільки припускає, що вони почнуться в найбільш пізній для них термін . Точно також вираз для часткового резерву часу II роду показує, що його використання не впливає на резерви подальших (які витікають) робіт, оскільки дозволяє здійснити початкову для них подію 
у найбільш ранній термін 
. Ми бачили, що вираз для незалежного резерву може іноді бути негативним, і в цьому випадку незалежний резерв вважається рівним 0.
Покажемо, що вирази, що визначають часткові резерви, завжди ненегативні. Дійсно, з формули (7), що визначає обчислювальний процес для пізніх термінів , маємо:
і далі
.
Точно також з формули (5), яка визначає обчислювальний процес для ранніх термінів отримаємо
,
отже
.
Таким чином, всі чотири резерви часу для робіт визначено так, що вони завжди ненегативні:
.
Перейдемо тепер до встановлення умови критичності будь-якого шляху.
Цю умову можна формулювати за допомогою понять резервів часу. Можна, наприклад, сказати, що для критичності деякого шляху μ необхідно й достатньо, щоб резерв часу цього шляху був рівний нулю. Це твердження є просто іншою формою визначення критичного шляху (шлях μ – критичний, якщо 
, тобто 
).
Далі, ми знаємо, що для подій будь-якого критичного шляху найбільш ранні й найбільш пізні терміни їх звершення рівні: = , тобто для подій, які лежать на критичних шляхах (і лише для них), резерви часу рівні 0:
.
Але це умова, як ми знаємо, не виділяє критичного шляху, якщо він не єдиний. В цьому випадку всі події деякого шляху можуть мати резерв, рівний 0, а шлях може бути некритичним.
Умову критичності деякого шляху найзручніше формулювати за допомогою резервів часу робіт, які складають даний шлях.
Теорема. Для того, щоб шлях μ був критичним, необхідно й достатньо, щоб для всіх робіт, які лежать на цьому шляху, повний резерв часу був рівний 0.
Необхідність цієї умови вже була показана вище. Залишається тільки довести достатність. Хай для всіх робіт деякого шляху 
повний резерв часу 
. Тоді для всіх цих робіт і інші резерви часу будуть рівні 0. Запишемо, наприклад, що всі часткові резерви I роду рівні 0:
;
;
...
.
Звідси отримуємо, що довжина шляху μ рівна 
, оскільки
отже, шлях μ – критичний.
Ще раз підкреслимо, що роботи, які лежать на критичному шляху, не мають ніяких резервів часу. Таким чином, знаючи ранні й пізні терміни звершення подій та тривалості робіт, можна визначити всі параметри мережевого графіка.