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

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

ГоловнаІнформатика, Компютерні науки → Визначення оптимальних змішаних стратегій підприємств на базі теорії ігор - Курсова робота

Визначення оптимальних змішаних стратегій підприємств на базі теорії ігор - Курсова робота

операцій. Очевидно, що резерв часу критичної операції має дорівнювати нулю. Тому вона й називається критичною.
Перш ніж приступити до обчислення резервів часу, потрібно увести визначення ще двох термінів, пов'язаних з кожною операцією. Це термін пізнього початку (LS) і термін раннього закінчення (ЕС), що для будь-якої операції (i, j) задаються співвідношеннями LSij=LCj-Dij, ECij=ESi+Dij.
Розрізняють два основних види резервів часу: повний резерв (TF) і вільний резерв (FF). Повний резерв часу операції (i, j) являє собою різницю між максимальним відрізком часу, протягом якого може бути виконана операція (LCj-ESi), і її тривалістю (Dij), тобто
TFij=LCi-ESi-Dij=LCj-ECij=LSij-ESi.
Вільний резерв часу визначається в припущенні, що всі операції в мережі починаються в ранній термін. При цьому умові величина FFijдля операції (i, j) являє собою перевищення припустимого відрізка часу (ESj-ESi) над тривалістю операції (Dij), тобто FFij=ESj-ESi-Dij.
Зазначимо, що тільки критичні операції повинні мати нульовий повний резерв часу. Коли повний резерв дорівнює нулю, вільний резерв також повинний бути рівним нулю. Однак зворотне невірно, оскільки вільний резерв некритичної операції також може бути нульовим.
2.2.5. Побудова календарного графіка і розподіл ресурсів
Кінцевим результатом виконуваних на мережевій моделі розрахунків є календарний графік (план). Цей графік легко перетвориться в реальну шкалу часу, зручну для реалізації процесу виконання програми.
При побудові календарного графіка необхідно враховувати наявність ресурсів, тому що одночасне (паралельне) виконання деяких операцій через обмеження, пов'язані з робочою силою, устаткуванням і іншими видами ресурсів, може виявитися неможливим. Саме в цьому відношенні становлять цінність повні резерви часу некритичних операцій. Зрушуючи некритичну операцію в тому або іншому напрямку, але в межах її повного резерву часу, можна домогтися зниження максимальної потреби в ресурсах. Однак навіть при відсутності обмежень на ресурси повні резерви часу зазвичай використовуються для вирівнювання потреби в ресурсах протягом усього терміну реалізації програми. Власне кажучи, це означає, що програму вдається виконати більш-менш постійним складом робочої сили в порівнянні з випадком, коли потреби в робочій силі (і інших ресурсах) різко змінюються при переході від одного інтервалу часу до іншого.
Для побудови календарного графіка перш за все визначаються календарні терміни виконання критичних операцій. Далі розглядаються некритичні операція і вказуються їхні ранні терміни початку ES і пізні терміни закінчення LC. Критичні операції зображаються суцільними лініями. Відрізки часу, в межах яких можуть виконуватися некритичні операції, наносяться пунктирними лініями, що показують, що календарні терміни цих операцій можна вибрати у вказаних межах за умови збереження відносин проходження. Фіктивна операція не вимагає витрат часу і тому зображається на графіці вертикальним відрізком. Числа, проставлені над некритичними операціями, відповідають їх тривалості.
Роль повних і вільних резервів часу при виборі календарних термінів виконання некритичних операцій пояснюється двома загальними правилами.
1. Якщо повний резерв дорівнює вільному, то календарні терміни некритичної операції можна вибрати в будь-якій точці між її раннім початком і пізнім закінченням.
2. Якщо вільний резерв менший повного, то термін початку некритичної операції можна перенести відносно її раннього терміну початку не більше, ніж на величину вільного резерву, не впливаючи при цьому на вибір календарних термінів безпосередньо наступних операцій.
3. Якщо вільний резерв часу операції більше повного, то це служить ознакою того, що остаточні календарні терміни такої операції не можна фіксувати, не прослідкувавши спочатку, як це вплине на терміни почала безпосередньо наступних операцій. Таку цінну інформацію можна отримати на основі розрахунків мережевої моделі.
Таким чином, якщо вільний резерв часу операції є меншим повного, це служить ознакою того, що остаточні календарні терміни такої операції не можна фіксувати, не перевіривши спочатку, як це вплине на терміни початку безпосередньо наступних операцій. Настільки цінну інформацію можна одержати тільки на основі розрахунків мережевої моделі.
При реалізації деяких програм може ставитися мета не просто забезпечення рівномірного використання, ресурсів, а обмеження максимальної потреби в них до певної межі. Якщо цієї мети не вдається досягти шляхом перепланування календарних термінів некритичних операцій, то для того, щоб знизити потребу в ресурсах, приходиться збільшувати тривалість деяких критичних операцій.
Через математичні труднощі поки що не розроблено метод, який забезпечував би оптимальне вирішення задачі рівномірного використання ресурсів, тобто задачі мінімізації максимальної потреби в ресурсах у будь-який момент процесу виконання програми.
2.2.6. Імовірнісні фактори, що враховуються при календарному плануванні програм
При календарному плануванні програм невизначеність (імовірнісний характер процесу реалізації програми) враховується за через уведення трьох різних оцінок тривалості кожної операції:
а - оптимістична (мінімальна) оцінка, що відповідає найбільш сприятливим умовам виконання операції;
b - песимістична (максимальна) оцінка, що відповідає найбільш несприятливим умовам виконання операції;
т - найбільш ймовірна (нормальна) оцінка, що характеризує усереднені умови виконання операції.
Передбачається, що в інтервалі між оптимістичною (а) і песимістичною (b) оцінками знаходяться всі можливі значення тривалості операції. Найбільш ймовірна оцінка m не обов'язково збігається із середньою точкою відрізку (а+b)/2 і може лежати праворуч або ліворуч від неї. Завдяки таким властивостям інтуїтивно виправдується припущення про те, що тривалість кожної операції підпорядковується бета-розподілу з модою в точці т і кінцями в точках а і b. На рис. 9 показані три випадки бета-розподілу: симетричний, асиметричний вправо, асиметричний вліво.
Рис. 9.
Вирази для математичного сподівання ?E(Dij) і дисперсії V бета-розподілу виводяться в такий спосіб: робиться припущення, що вага середньої точки (а+b)/2 є вдвічі меншою ваги найбільш імовірної точки m. Таким чином, величина ?D являє собою середнє арифметичне величин (а+b)/2 і 2m, тобто
Розмах (a, b) приймається рівним біля шести середніх квадратичних відхилень розподілу, тому що 90% або більше будь-якої щільності імовірності лежить у межах трьох середніх квадратичних відхилень від математичного сподівання. Таким чином, Var(Dij)
V=[(b-a)/6]2
Розрахунки мережі, наведені в п.3, можна безпосередньо використовувати, замінивши одну оцінку тривалості D величиною ?D.
Тепер можна оцінити імовірністьнастання кожної події мережі. Нехай ?i означає ранній термін події i. Оскільки тривалості операцій, що ведуть до події i, є
Loading...

 
 

Цікаве