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

В


 

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

80189. Принципы построения радиоэлектронных систем локации и навигации 155 KB
  К радиотехническим системам обнаружения и измерения относятся также так называемые пассивные радиосистемы когда радиопередатчик в системе отсутствует а информация извлекается радиоприемным устройством из сигналов поступающих от каких либо естественных источников электромагнитных колебаний. Радиолокационные системы Радиолокация от лат. Основной целью радиолокации является установление связи между параметрами передающей приемной системы и характеристиками отраженного и рассеянного радиолокационной целью излучения с учетом их взаимного...
80190. Современные системы подвижной радиосвязи 373.5 KB
  Особенно быстрыми темпами как в мире так и у нас в России идет развитие сетей сотовой радиосвязи. По числу абонентов системы мобильной связи уже можно судить об уровне и качестве жизни в данной стране. Однако темпы роста абонентов мобильной связи в России почти 200 в год вселяют оптимизм.
80191. Явление вариантности форм родительного падежа множественного числа в современном русском языке 159.62 KB
  В данной работе при анализе языкового материала были использованы такие общенаучные способы исследования, как наблюдение и эксперимент. Основной общенаучный метод анализа – описательный. Наиболее распространенный способ научного исследования – это наблюдение. Под лингвистическим наблюдением в свою очередь понимаются правила и техника выделения из текста (или потока речи) того или иного факта и включение его в изучаемую систему.
80192. Методы анализа линейных цепей 136 KB
  Все электрические цепи состоящие из сопротивлений емкостей индуктивностей и соединительных проводов линейны. Анализ отклика линейной цепи на известное входное воздействие сводится при этом к известной в математике задаче решения линейного дифференциального уравнения nго порядка с постоянными коэффициентами. Порядок n этого уравнения в радиотехнике принято называть порядком линейной цепи системы.
80193. Нелинейные и параметрические цепи 143.5 KB
  Наиболее часто используют метод анализа нелинейных цепей основанный на линеаризации характеристик НЭ при фильтрации высших гармоник сигнала на выходе цепи. В результате первой операции в безынерционном НЭ происходит такое преобразование формы входного сигнала при котором в его спектре появляются новые гармонические составляющие. Вторую операцию осуществляет линейный фильтр выделяя нужные спектральные составляющие преобразованного входного сигнала. Кусочнолинейная аппроксимация характеристики Нелинейный резонансный усилитель мощности...
80194. Генерация сигналов. Модуляция и детектирование сигналов 138 KB
  Колебательной системой или устройством с самовозбуждением называют динамическую систему преобразующую энергию источника постоянного тока в энергию незатухающих колебаний причем основные характеристики колебаний амплитуда частота форма колебаний и т. Процесс получения переменных сигналов требуемой формы и частоты называют генерированием электрических колебаний. Автогенератор часто просто генератор устройство преобразующее энергию постоянного тока в энергию электрических колебаний требуемой частоты и формы. Автогенератор можно...
80195. Типы и основные характеристики линий связи 357.5 KB
  Типы и основные характеристики линий связи Принципы построения радиоэлектронных систем связи Любую техническую систему действие которой основано на непосредственном использовании высокочастотных электромагнитных колебаний радиодиапазона для сбора передачи извлечения обработки или хранения информации называют радиотехнической системой упрощенно радиосистемой. Линией связи называют физическую среду космическое пространство свободное пространство воздух в нейтральном или ионизированном состояниях земная поверхность морская вода...
80197. Элементная база линейных цепей 163.43 KB
  Таким образом анализируемая RС-цепь при малых τα может осуществлять линейную операцию дифференцирования поданного на нее сигнала. Чтобы определить частотный коэффициент передачи дифференцирующей цепи, запишем комплексную амплитуду тока