1402

Календарне планування.

Практическая работа

Информатика, кибернетика и программирование

Календарне планування – використання мережевої моделі для визначення моментів початку і кінця операцій програми. Виявляються критичні операції, які впливають на тривалість програми, і некритичні операції, які мають резерви часу. Резерви часу можна використати для оптимізації потреб в ресурсах.

Украинкский

2013-01-06

673.5 KB

14 чел.

Практична робота № 8

КАЛЕНДАРНЕ ПЛАНУВАННЯ

Мета роботи: засвоїти та навчитись використовувати методи календарного планування.

8.1 Короткі теоретичні відомості

8.1.1. Загальні положення

При плануванні та управлінні великими проектами неоціненну користь керівникові можуть дати мережеві методи календарного планування (МКП). В даному контексті “проект” означає сукупність взаємопов’язаних операцій, які необхідно визначити в визначеному порядку, щоб досягнути поставленої мети.

Операції впорядковуються в тому сенсі, що одні з них не можуть бути виконані раніше, ніж будуть завершені інші. Управління проектами (програмами) складає галузь досліджень, яка має назву мережеве планування і управління. Воно складається з трьох етапів:

1. Структурне планування – розбиття програми на чітко визначені операції, визначення оцінки тривалості операцій та взаємозв’язок між операціями. В результаті структурного планування будується мережевий графік (мережева модель).

2. Календарне планування – використання мережевої моделі для визначення моментів початку і кінця операцій програми. Виявляються критичні операції, які впливають на тривалість програми, і некритичні операції, які мають резерви часу. Резерви часу можна використати для оптимізації  потреб в ресурсах.

3. Оперативне управління – управління виконанням програми на базі календарного плану.

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

Мережева модель будується за наступними правилами:

1. Кожна операція програми зображується в мережі лише однією дугою.

2. Жодна пара операцій не визначається однією і тією ж самою парою подій. Тобто в орграфі відсутні кратні дуги.

3. Події нумеруються таким чином, щоб кожна дуга починалась від події з меншим і закінчувалася в події з більшим номером (див. рис. 8.1.).

Рис. 8.1. Операція програми (i, j).

Потреба у кратних дугах при побудові мережевої діаграми   виникає у випадку, коли операції припустимо виконувати одночасно. Для того, щоб уникнути кратних дуг користуються введенням фіктивної операції  і фіктивної події.

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

ПРИКЛАД 8.1. Нехай маємо наступні умови слідування для операцій А, В, С, D: операція А передує операції В, С; операція В передує операції D. Щоб правильно відобразити ці умови необхідно ввести фіктивну операцію (див. рис.8.2). На малюнку вона зображена пунктирною лінією.

Рис. 8.2. Фрагмент мережі з фіктивною операцією.

При включенні операції в мережеву модель необхідно для забезпечення правильного впорядкування операцій відповісти на наступні запитання:

1. Які операції безпосередньо передують даній операції?

2. Які операції безпосередньо слідують після даної операції?

3. Які операції можуть виконатись одночасно?

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

Для розрахунків параметрів мережі використовують наступні формули, поняття і позначення:

– ранній початок події i:

; ;

– пізнє закінчення події j:

; ;

де nкінцева подія програми;

1 – початкова подія програми;

 тривалість операції ij;

 раннє закінчення операції ij:

;

 пізній початок операції ij:

;

 повний резерв часу операції ij:

;

 вільний резерв часу операції ij:

.

Вільний резерв ніколи не перевищує повного резерву. При використанні повного резерву зміщення операцій в часі на величину, що перевищує вільний резерв, зміщує інші операції програми.

Рис. 8.3. Приклад мережевого графіка

Таблиця 8.1

Параметри мережі, зображеної на рис. 8.3

(i,j)

Ранні характеристики

Пізні характеристики

1,2

2

0

2

0

2

0

0

1,3

3

0

3

2

5

2

0

1,5

2

0

2

3

5

3

3

2,3

0

2

2

5

5

3

1

2,4

1

2

3

4

5

2

0

2,5

3

2

5

2

5

0

0

2,6

2

2

4

3

5

1

0

3,7

1

3

4

5

6

2

1

4,6

0

3

3

5

5

2

1

5,7

0

5

5

6

6

1

0

5,9

4

5

9

5

9

0

0

6,7

1

4

5

5

6

1

0

6,9

3

4

7

6

9

2

0

7,8

2

5

7

6

8

1

2

8,9

1

7

8

6

9

1

2

8.1.2. Побудова календарного плану

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

Таблиця 8.2

Задані потреби в ресурсах

Операція

Потреба (чол.)

1,2

0

1,3

2

1,5

5

2,4

0

2,6

2

2,5

3

Закінчення таблиці 8.2

Операція

Потреба (чол.)

3,7

3

5,9

3

6,7

6

6,9

1

7,8

4

8,9

2

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

На рис. 8.4 відображений календарний план та діаграма потреби в ресурсах на кожному інтервалі часу. Цей план складений у припущенні, що операції починаються у ранні терміни.

Рис. 8.4. Календарний план з діаграмою потреби в ресурсах

8.1.3. Імовірнісні фактори в календарному плануванні

Часто тривалості операцій точно визначити неможливо. Легше охарактеризувати їх тривалості часовими рамками. Будемо характеризувати тривалість кожної операції параметрами:

а  оптимістична оцінка тривалості;

bпесимістична оцінка тривалості;

m  найбільш ймовірна тривалість.

Гіпотези щодо ймовірнісних характеристик випадкової величини є наступними.

Математичне сподівання вираховується в припущенні, що ймовірність середньої тривалості операції в 2 рази менше, ніж ймовірність оцінки m

 

Дисперсія вираховується у припущенні, що для більшості розподілів 95% щільності знаходиться в межах 3 середніх квадратичних відхилень від математичного сподівання. Отже, різниця між b та а дорівнює 6 середніх квадратичних відхилень випадкової величини. Звідки:

.

Користуючись ймовірнісними характеристиками кожної операції можемо вирахувати ймовірність настання кожної події мережі раніше, ніж деякий директивний термін. В якості настання директивних термінів  зручно прийняти пізні терміни настання події у припущенні, що тривалість кожної з операцій буде найбільш ймовірною. Термін настання події є випадковою величиною . Математичне сподівання  цієї випадкової величини та дисперсію  визначають наступним чином.  Якщо подія і зв’язана з початковою подією лише одним шляхом, то матсподівання визначається як сума очікуваних тривалостей операцій, що належать цьому шляху, а дисперсія – сума дисперсій тих самих операцій. У випадку кількох  шляхів від початкової події до події і матсподівання та дисперсію обчислюють для шляху у якого найбільша сума очікуваних тривалостей операцій. Якщо для двох чи більше шляхів ці суми співпадають, то обираємо шлях з максимальною дисперсією.

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

де  – випадкова величина з нульовим матсподіванням та одиничною дисперсією;

.  

Значення  обчислюється за таблицею інтеграла Лапласа.

8.2. Порядок виконання роботи

  1.  Ознайомитись з теоретичними відомостями.
    1.  Згідно варіанту побудувати мережеву модель, яка складається з операцій А, В, С, ..., Р та задовольняє заданому в індивідуальному завданні 8.3.1 відношенню.
      1.  За заданими вихідними даними (п. 8.3.2) побудувати мережеву модель.
      2.  Побудувати мережеву модель і виконати її розрахунок для заданої програми, пов’язаної з купівлею автомобіля (п. 8.3.3).
      3.  Визначити критичні шляхи в мережі, яка задана варіантом програми в п. 8.3.4.
      4.  Розрахувати повний і вільний резерви часу операцій у задачі п. 8.2.5.
      5.  Прийняти, що для програми задачі п. 8.2.5 існують оцінки тривалості операцій (a, b, m). Знайти ймовірності того, що події мережі почнуться не пізніше своїх пізніх термінів.
      6.  Використовуючи задані варіантом індивідуального завдання дані щодо прямих витрат при нормальній та мінімальній тривалості операцій задачі п. 8.2.5, побудувати календарні графіки мінімальної вартості реалізації програм в проміжку від нормальної до мінімальної тривалості кожної програми.
      7.  Для заданих у варіанті значень операцій розрахувати мережу, зображену на рис. 8.5. методом календарного планування та подати розрахунок у вигляді табл. 8.1.

Рис. 8.5. Мережа до завдання 8.2.9.

  1.  Оформити звіт з практичної роботи

8.3. Варіанти індивідуальних завдань

  1.  Вихідні дані до п. 8.2.2.

Варіант

Відношення

1

А, В, С – початкові операції програми, які можна починати одночасно

2

Операції D, E, F починаються зразу по закінченню операції А

3

Операції I, G починаються після завершення B та D

4

Операція H починається після закінчення С та G

5

Операції K та L слідує за операцією I

6

Операція J слідує за операціями  E та  H

7

Операції  M та N слідують за F, але не можуть початися, поки не будуть завершені E та H

8

Операція O слідує за M та I

9

Операція P слідує за J, L, O

10

Операції  K, N, P є останніми  операціями програми

  1.  Вихідні дані до п. 8.2.3.

Варіант

Операція

Попередні операції

Тривалість (дні)

1

A

1

2

B

2

3

C

A

1

4

D

C

2

5

E

B, C

6

6

F

D

10

7

G

F

3

8

H

G

1

9

I

F

1

10

J

E, H

5

11

K

I

2

12

L

F, J

1

13

M

F

2

14

N

L, M

4

15

O

G, J

2

16

P

O

2

Продовження вихідних даних до п. 8.2.3

Варіант

Операція

Попередні операції

Тривалість (дні)

17

Q

I, P

1

18

R

P

7

19

S

I, N

7

20

T

S

3

  1.  Вихідні дані до п. 8.2.4.

Варіант

Операція

Попередні операції

Тривалість (дні)

1

A

3

2

B

A

14

3

C

A

1

4

D

C

3

5

E

C

1

6

F

C

2

7

G

D, E, F

1

8

H

G

1

9

I

H

3

10

J

H

2

11

K

I, J

2

12

L

K

2

13

M

L

4

14

N

L

1

15

O

B, M, N

3

  1.  Варіанти до п. 8.2.5.

Перша літера в прізвищі студента

Мережа

Рис.

А – М

(а)

8.6, а

Н – Я

(б)

8.6, б

а)

б)

Рис. 8.6. Варіанти мережі до п.8.2.5.

  1.  Вихідні дані до п. 8.2.7.

Оцінки тривалості операцій (a, b, m) для програми (а)

Операція

(a, b, m)

Операція

(a, b, m)

1,2

(5, 8, 6)

3,6

(3, 5, 4)

1,4

(1, 4, 3)

4,6

(4, 10, 8)

1,5

(2, 5, 4)

4,7

(5, 8, 6)

2,3

(4, 6, 5)

5,6

(9, 15, 10)

2,5

(7, 10, 8)

5,7

(4, 8, 6)

2,6

(8, 13, 9)

6,7

(3, 5, 4)

3,4

(5, 10, 9)

Оцінки тривалості операцій (a, b, m) для програми (а)

Операція

(a, b, m)

Операція

(a, b, m)

1,2

(1, 4, 3)

3,7

(12, 14, 13)

1,3

(5, 8, 7)

4,5

(10, 15, 12)

1,4

(6, 9, 7)

4,7

(8, 12, 10)

1,6

(1, 3, 2)

5,6

(7,11, 8)

2,3

(3, 5, 4)

5,7

(2, 8, 4)

2,5

(7, 9, 8)

6,7

(5, 7, 6)

3,4

(10, 20, 15)

  1.  Вихідні дані до п. 8.2.8.

Для програми (а)

Операція

Нормальна

Мінімальна

тривалість

вартість

тривалість

вартість

1,2

5

100

2

200

1,4

2

50

1

80

1,5

2

150

1

180

2,3

7

200

5

250

2,5

5

20

2

40

2,6

4

20

2

40

3,4

3

60

1

80

3,6

10

30

6

60

4,6

5

10

2

20

4,7

9

70

5

90

5,6

4

100

1

130

5,7

3

140

1

160

6,7

3

200

1

240

Для програми (б)

Операція

Нормальна

Мінімальна

Тривалість

Вартість

Тривалість

Вартість

1,2

4

100

1

400

1,3

8

400

5

640

1,4

9

120

6

180

1,6

3

20

1

60

2,3

5

60

3

100

2,5

9

210

7

270

3,4

12

400

8

800

3,7

14

120

12

140

4,6

15

500

10

750

4,7

10

200

6

220

5,6

11

160

8

240

5,7

8

70

5

110

6,7

10

100

2

180

  1.  Вихідні дані до п. 8.2.9.

Операція

Варіант

1

2

3

4

5

6

7

8

9

1,2

3

4

2

1

2

2

3

3

3

1,3

5

3

5

5

5

4

6

4

3

1,5

4

4

4

6

5

4

4

4

4

2,3

0

2

0

2

0

5

5

5

0

2,4

1

1

1

1

6

1

3

2

1

2,5

3

3

3

4

3

3

3

3

3

2,6

2

4

2

1

2

6

2

4

4

3,7

1

1

6

5

1

1

2

1

1

4,6

5

1

5

5

8

7

5

4

5

5,7

0

3

0

1

3

1

4

1

4

5,9

2

2

6

2

2

2

1

2

2

6,7

3

4

3

4

4

1

3

4

3

6,9

3

6

 2

2

2

3

2

2

3

7,8

5

3

4

5

3

2

5

2

2

8,9

1

1

2

6

1

1

1

1

1

8.4. Зміст звіту

  1.  Назва та мета роботи.
    1.  Короткі теоретичні відомості.
      1.  Умови задачі та її розв’язок.
      2.  Стислі висновки.

8.5. Контрольні запитання

  1.  Етапи мережевого планування та управління.
    1.  Правила побудови мережі.
      1.  Правила впорядкування операцій.
      2.  Зміст критичної операції в термінах теорії графів.
      3.  Послідовність побудови календарного плану.
      4.  Прийняті гіпотези, щодо ймовірнісних характеристик випадкової величини при визначенні тривалості операцій.

101

3

22

10

8

10

12

3

15

7

10

7

1

7

6

5

4

3

2

1

9

7

10

4

5

4

8

3

8

10

1

5

7

6

5

4

3

2

1

1

3

1

2

9

8

7

6

5

4

3

1

2

9

8

7

6

5

А

4

C

D

В


 

А также другие работы, которые могут Вас заинтересовать

40883. Класифікація електромагнітних явищ 165 KB
  Рівняння магнітостатики: рівняння електростатики: . Рівняння магнітостатики має місце і там де . Звідси тобто звідки одержуємо рівняння Лапласа: з урахуванням заряду Пуасона: без.
40884. Конституційне право України як наука і навчальна дисципліна 253 KB
  €œКонституційне право України як наука і навчальна дисципліна План Конституційне право України як наука: поняття предмет система науки джерела науки основні функції науки. Конституційне право України як навчальна дисципліна: поняття структура курсу основна характеристика. Джерела конституційного права України як галузі права: поняття основні вимоги до джерел види джерел. Література Основна до всіх тем Конституція України від 28 червня 1996 р Відомості Верховної Ради України.
40885. Затухання у металі, скін – шар 67 KB
  В металі хвиля затухає як . Глибина на якій хвиля спадає в раз називається скін – шаром. Ми не врахували те що існує також відбита хвиля у середовищі
40886. Конституція України - Основний Закон держави 180 KB
  Конституція України Основний Закон держави†План Поняття і загальна характеристика конституції як Основного Закону держави. Юридичні властивості й функції Конституції України. Основні етапи становлення Конституції України. Правова охорона Конституції України.
40887. Узагальнена плоска хвиля 284.5 KB
  Таким чином хвиля розповсюджується в багатьох напрямках: хвиля в напрямку Задача: Нехай хвиля падає під кутом до поверхні середовища знайти характеристики відбитої хвилі та заломленої.
40888. Основи конституційного ладу України 279.5 KB
  Механізм та основні функції Української держави. Метою цієї лекції є формування у студентів знань щодо основ конституційного ладу України який включає поняття державного і суспільного ладу; засвоєння ними понять “гарантії конституційного ладу Україн膓механізм держав膓принципи суспільного ладу†тощо. Проблеми та перспективи побудови правової держави в Україні Право України.: Інт держави і права ім.
40889. Рівняння Максвела для Т, ТЕ, ТМ хвиль 388 KB
  Т хвиля розповсюджується зі швидкістю світла . хвиля розповсюджується в напрямку – хвиля існує там де є розв’язок рівняння Лапласа електрика. Тому якщо існує електростатичне поле то може існувати і Т – хвиля.
40890. Прямокутний хвильовід 139.5 KB
  Для хвилі завдяки граничним умовам на стінках , а по певній координаті (там, де індекс = 0 ) це поле однорідне, тоді буде всюди, тобто цієї хвилі не буде.
40891. Хвильовий опір хвильовода 164 KB
  Рівняння для Т, ТЕ, ТМ хвиль різні. Щоб звести їх до одного виду, використовуючи потенціали , , де - електрична скалярна функція, - магнітна скалярна функція. Якщо для Т – хвилі завжди, то , а перетворюється в нуль завдяки .