WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дослідження операцій. Задачі упорядкування та координації. Сітьове планування та керування - Реферат

Дослідження операцій. Задачі упорядкування та координації. Сітьове планування та керування - Реферат

сума для довільного шляху від і-ої події до j- ої . Наприклад, для графу рис. 6 завершеними шляхами будуть L1=[2; 6; 7] , L2=[4; 5; 7], L3=[3; 6; 7] і т. д. Їх терміни t(L1)=3+5+16=24; t(L2)=8+7+18=33; t(L3)=4+10+16=30. Критичний шлях слід визначати за алгоритмом, описаним у питанні 1 , використовуючи завантаження дуги не пропускною спроможністю, а терміном виконання роботи, що відповідає дузі. Розглянемо інший спосіб обчислення терміну критичного шляху. Критичний шлях для графу рис.6 Lкp=[l; 2; 4; 5; 7], а його термін t(Lkp)=3+9+7+18=37. На рис.6 він зображений подвійною лінією. Критичними роботами будуть: (1; 2), (2; 4), (4; 5), (5; 7). Рис.6. Критичний шлях має особливе значення для ПУМ, бо роботи, які складають цей шлях, ви-значають загальний термін завершення всіх робіт комплексу, які плануються в даній системі ПУМ. Основні параметри ПУМ за критерієм часу наведені в табл.1. Основні параметри планування й управління мережі Таблиця 1. Елемент мережі, характеризований параметром Назва параметра Умовні позначення параметра Подія і Ранній термін звершення події tp(i) Пізній термін звершення події tn(i) Резерв часу події Rp(i) Робота (i, j) Термін виконання роботи t(i,j) Ранній термін початку робо-ти tpn(i,j) Ранній термін завершення роботи tpз(i,j) Пізній термін початку робо-ти tnn(I,j) Пізній термін завершення роботи tпз(I,j) Повний резерв часу роботи Rn(i,j) Частковий резерв першого виду часу роботи R1(i,j) Частковий резерв другого виду часу роботи R2(i,j) Незалежний резерв часу ро-боти Rн(i,j) Шлях L Термін шляху t(L) Термін критичного шляху tkp Резерв часу шлях Rt(L) Розглянемо формули обчислення параметрів, указаних в табл.1. Використання формул пока-жемо стосовно графу ПУМ, схему запису параметрів часу якого наведено на рис.6. Результати обчислення параметрів записують у таблиці на зразок табл.2. А якщо граф має невелику кількість подій (до двох десятків), то результати можна записувати на графові за схемою, зображеною на рис. 7. t(i,j)[Rn(i,j);R1(i,j);Rн(i,j)] Рис. 7. Розглянемо параметри подій. Певна подія j не може відбуватися раніше ніж завершаться всі роботи, які їй передують. Отже, ранній термін tp(j) можливого звершення j-ої події визнача-ється терміном максимального шляху: (1) (Lbj - будь-який шлях, який передує j -й подій, тобто шлях від вихідної до j -ої події). Якщо подія j має кілька шляхів, які їй передують, отже, кілька попередніх подій і , то ранній термін tp(j) звершення події j зручно обчислювати за формулою: (2) Формула (2) показує, що обчислення параметру tp доцільно починати з вихідної події, для якої tp дорівнює нулю, розглядаючи наступні події в порядку збільшення їх номерів. Затримка зі звершенням i -ої події стосовно свого раннього терміну (строку) не буде вплива-ти на термін звершення завершальної події (отже, і на термін виконання досліджуваного комплексу робіт), поки сума термінів (строку) звершення i -ої події та терміну максимального з усіх шляхів, які ідуть від i -ої події до завершальної, не перевищить терміну критичного шляху. Таким чином, пізній (або граничний) термін (строк) tn(i) звершення і -ої події обчис-люється за формулою: (3) (Liз , - будь-який шлях L від і -ої події до завершальної). Якщо подія "i" має кілька наступних шляхів, пов'язана з кількома наступними подіями "j' , то пізній строк звершення події "i" зручно обчислити за формулою: (4) Резерв часу R(i) i -ої події обчислюється як різниця пізнього та раннього термінів звершення i -ої події: (5) Резерв часу події показує, на який допустимий термін можна затримати звершення події, не гальмуючи (не збільшуючи) при цьому термінвиконання всього комплексу робіт мережі. Критичні події не мають резервів часу, бо будь-яка затримка зі звершенням подій, які роз-ташовані на критичному шляху, викличе таку ж затримку у виконанні завершальної події. Отже, щоб визначити термін критичного шляху, необхідно і достатньо обчислити ранній строк завершальної події, його величина і визначає цей термін. Події з нульовим резервом часу визначають роботи, які складають критичний шлях. Аналіз та оптимізація планування й управління мережею Аналіз графу мережі дозволяє оцінити доцільність обраної структури графу, тобто класифі-кацію робіт та їх послідовність, завантаження виконавців робіт, можливості зміщень в часі виконання робіт некритичних шляхів. Якщо оцінки термінів виконання робіт мають ймовір-ний характер, то аналіз ПУМ дає можливість оцінити ймовірність виконання повного ком-плексу робіт з реалізації плану в заданий термін. На першому етапі аналізу графу досліджується його топологія (взаємне узгодження елеме-нтів графу відповідно до вимог його побудови) та оцінюється доцільність вибору послідов-ності робіт і структури графу. На цьому етапі перевіряються доцільність виконаного рівня деталізації робіт та оцінка наявних виробничих можливостей. На другому етапі виконується класифікація робіт і групуються роботи за величинами резер-вів термінів їх виконання, а також визначається ступінь напруженості своєчасного виконання робіт некритичних шляхів. Ступінь напруженості терміну виконання роботи ( i , j ) прийнято характеризувати коефі-цієнтом напруженості K( i, j ) , величина якого визначається відношенням суми термінів ви-конання неспівпадаючих робіт максимального шляху, якому належить дана робота, та кри-тичного шляху: (6) - термін виконання робіт максимального шляху, який містить роботу (i,j) , - термін виконання робіт критичного шляху; - сума термінів виконання тих робіт максимального шляху, відповідного роботі (і, j) , які співпадають з роботами критичного шляху). Формулу (1) можна записати і в такому ви-гляді: (7) - повний резерв часу роботи (i,j) . Коефіцієнт напруженості К(і, j) приймає значення від 0 до 1 . Чим більше його величина, тим важче своєчасно виконати дану роботу. Третім етапом аналізу ПУМ є розрахунки запитів виробничих ресурсів та їх розподіл у часі. На четвертому етапі визначають ймовірність своєчасного виконання планового комплексу робіт з реалізації проекту. Ці розрахунки вельми складні. Як правило, з певною мірою вірогі-дності вони визначають найменший та найбільший можливі терміни виконання комплексу робіт. Виділяють також роботи, які з високим рівнем надійності можуть попасти на критич-ний шлях. Саме цим роботам приділяється особлива увага при розподілі виробничих ресур-сів і в процесі реалізації робіт. Усі вказані етапи аналізу системи ПУМ передують її оптимізації. Література 1. Карлин С. Математические методы в теории игр, программировании и экономике. -М.: Мир, 1964. 2. Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964. 3. Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі й менеджменті. -К.: Либідь, 1995. 4. Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної економіки. -К.: Інформтехніка, 1995. 5. Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение, 1986.
Loading...

 
 

Цікаве