Метод аналізу й оцінки програм

1.2.2 Метод аналізу й оцінки програм

Методи сіткового планування - методи, основна мета яких полягає в тім, щоб скоротити до мінімуму тривалість проекту. Ґрунтуються на розроблених практично одночасно і незалежно методі критичного шляху МКП і методі оцінки і перегляду планів PERT (Program Evaluation and Review Technique). Перший метод розроблений у 1956 році для складання планів-графіків великих комплексів робіт з модернізації заводів фірми "Дюпон". Другий метод розроблений корпорацією "Локхид" і консалтинговою фірмою "Буз, Аллен энд Гамильтон" для реалізації великого проекту розробки ракетної системи "Поларис".

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

Описані вище методи CPM і PERT є класичними і спочатку використовувалися незалежно друг від друга. Зараз вони складають єдиний метод сітьового планування і керування, що включає наступні три етапи: структурне планування, календарне планування, оперативне керування планом.

Етап структурного планування починається зі складання переліку (упорядкованого) робіт, виконання яких приведе до досягнення мети проекту. Потім визначаються тривалості робіт і будується сітьовий графік, що є основою календарного планування.

1.3 Вітчизняний і закордонний досвід використання СУПС

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

Досягти реального скорочення термінів проектування при використанні локальних систем автоматизації неможливо. Відповідно до основної специфікації на створення інтегрованої системи коло розв'язуваних задач повинне охоплювати всі стадії проектування, починаючи від передконтрактної документації, генерації тривимірної моделі корпуса, оббудовування приміщень, мехчастини, трубопроводів і систем, электрочастини і т.і., випуску двох- і тривимірних робочих креслень, суднової звітної документації по всім спеціалізаціям, технологічну підготовку виробництва аж до видачі керуючих програм для верстатів із ЧПУ, а також вирішення задач по організації і керуванню виробництвом.

Комплексна (інтегрована) інформаційна система (КІС) — це сукупність технічних і програмних засобів підприємства, що реалізують ідеї і методи автоматизації. Комплексна автоматизація має на увазі переклад у площину комп'ютерних технологій всіх основних ділових процесів організації. Структура виробничого підприємства (об'єднання) дозволяє здійснити системний підхід у забезпеченні високого рівня взаємодії підрозділів на основі наскрізної комп'ютеризації всіх стадій створення судна шляхом розробки і впровадження інтегрованої системи автоматизованого проектування, технологічної підготовки, організації і керування суднобудівним виробництвом з використанням єдиної бази даних.

Уведення системи керування проектами (СКП) до складу КІС дозволяє здійснювати стратегічне планування і керування підприємством. Сучасні системи керування процесами дозволяють інтегрувати навколо себе різне програмне забезпечення, формуючи єдину інформаційну систему. Тим самим зважуються проблеми координації діяльності співробітників і підрозділів, забезпечення їхньою необхідною інформацією і контролю виконавської дисципліни, а керівництво одержує своєчасний доступ до достовірних даних про хід виробничого процесу і має засіб для оперативного прийняття і втілення в життя своїх рішень. І, що саме головне, отриманий автоматизований комплекс являє собою гнучку відкриту структуру, яку можна перебудовувати і доповнювати новими чи модулями зовнішнім програмним забезпеченням.

Прикладом вітчизняних розробок є складова частина інтегрованої системи – система нормування трудомісткості САНТ (розробник Г. І. Карпов).

Система автоматизованого нормування трудомісткості (САНТ) формує в єдиній базі дані нормативи трудомісткостей технологічних операцій у різних видах суднобудівного виробництва. В окремому випадку ці нормативи разом з розмірами (нормообразуючі показники) деталей корпусних конструкцій (САПР ТПП верфі) складуть основу автоматизованого розрахунку норм часу виконання технологічних операцій за допомогою гнучких виробничих модулів обробки деталей з листового і профільного прокату.

Інформаційні масиви САНТ у єдиній базі даних містять аналітичні залежності нормативів часу, упорядкованих по ключових реквізитах, а також необхідні зварювальні дані. Визначено ключові реквізити (позначення - технологічних операцій, нормативів часу, причин зміни трудомісткостей, коефіцієнтів серійності судна), що забезпечують однозначну ідентифікацію нормативів часу кожної технологічної операції, а також інформаційний взаємозв'язок із САПР ТПП верфі.

Основним вихідним масивом САНТ у єдиній базі даних є масив трудомісткостей технологічних операцій, структура якого забезпечує збереження і відновлення інформації на будь-яке серійне судно даного проекту з урахуванням усіх коректувань, починаючи з головного. Таким чином, дублювання інформації при переході з одного серійного судна на інше в масиві виключено. Структура масиву дозволяє по запиту автоматизовано проводити вибірку інформації про трудомісткості будь-яких робіт верфі, забезпечує інформаційний зв'язок з АСУ підприємств - будівельників судів.

У той же час як показав аналіз можливостей САПР реалізованих у вітчизняній суднобудівній промисловості, а також технічних можливостей апаратних засобів вітчизняного виробництва, необхідно орієнтуватися на закордонних постачальників апаратного і програмного забезпечення при розробці і впровадженні інтегрування системи на базі закуплених апаратних і програмних засобів, адаптованих до умов кожного суднобудівного підприємства (об'єднання) і використовуючих наявні власні розробки.

Досить популярною СКП є російське ПЗ Spider Projects. Проте ця програма має досить багато недоліків, що обмежує її застосування у суднобудівництві.

З зарубіжних СУП поширені Microsoft Project, Symantec Time Line, Open Plan, Primavera. Так в українському судобудівництві досить часто використовують Microsoft Project.

На базі аналізу ринку ПЗ СКП, виконаного консалтінговою компанією Gather, була складена порівняльна таблиця (табл. 2).

Таблиця 1 – порівняння MS Project, Primavera и Spider

Критерий оценки	Microsoft Project 2002 Professional	Primavera P3e	Spider Project
Планирование проекта
Интерфейс аналогичен MS Office	Да	Нет	Нет
Интерактивный самоучитель	Да	Нет	Нет
Трудоемкость разработки структур работ	Низкая	Высокая	Низкая
Более чем 1 связь между работами	Нет	Да	Нет
Планирование от "Объема" ("реалии управления в 80-х годах прошлого века")	Требуется знать методику использования	Нет	Да
Структуры ресурсов	Да	Да	Да
Мастера предоставления и оптизации ресурсов для проекта	Да	Нет	Нет
Профили загрузки	Да	Да	Нет
Разделяемые пулы (Управление ресурсами проектного подразделения в целом)	Да	Да	Нет
Управление портфелями проектов	Да	Да	Нет
Планирование затрат	Да	Да	Да
Сверхурочные затраты	Да	Да	Нет
Оценка влияния рисков через имитационное моделирование "а что если?"	Да	Да	Нет
Анализ вероятности окончания проекта по условиям	Нет	Нет	Да
Интерактивная оптимизация планов проекта	Да	Да	Нет
Автоматическая оптимизация без интерактивности	Да	Да	Да
Отслеживание и управление проектом
План/фактный анализ	Да	Да	Да
Профессиональная проектная статистика на базе промышленного OLAP-сервера	Да	Нет	Нет
Автоматический запрос о статусе работе исполнителям	Да	Да	Нет
Информирование о статусе работ топ-менджеров	Да	Да	Нет
Отслеживание объемов	Требуется знать методику использования	Нет	Да
Освоенный объем	Да	Да	Да
Коллективная работа
Работа на основе промышленной СУБД (SQL Server)	Да	Да	Нет
Web-доступ к проектной информации	Да	Да	Нет
Web-анализ состояния ресурсов	Да	Да	Нет
Поддержка мобильных средств класса Palm	Нет	Да	Нет
Взаимодействие с исполнителями	Да	Да	Нет
Средства для информирования высшего управленческого звена	Да	Да	Нет
Средства для принятия стратегических решений топ-менеджерами	Да	Да	Нет
Отслеживание запросов по контролю качества	Да	Нет	Нет
Интегрированная поддержка проектного документооборота	Да	Нет	Нет
Поддержка высшего руководства
Средства для информирования высшего управленческого звена	Да	Да	Нет
Средства для принятия стратегических решений топ-менеджерами	Да	Да	Нет
Оценки применимости
Оптимальное сочетание цена/качество	Да	Нет	Нет
Сеть внедренцев	Широкая	Узкая	Узкая
Консалтинговая поддержка	Широкая	Узкая	Узкая
"Сегмент успеха"	Лидерство в малых и средних компания	Ниша: решения свыше 350 раб. мест.	Компании с советскими методиками управления

1.4 Змістовна постановка задачі

На основі проведеного аналізу предметної області можна зрозуміти, що в ході курсової роботи для досягнення поставленої мети потрібно виконати три наступні підзадачі:

I. Розробка детермінованої моделі сітьового графіка, що дозволяє розрахувати часові параметри проекту та зобразити модель у виді діаграми Ганта, та проведення моделювання за отриманими початковими даними. Цю підзадачу можна розбити на такі кроки:

1. Розробити програмні структури для обраного представлення сітьового графа (СГ).

2. Розробити програмне забезпечення для топологічного аналізу СГ на наявність обривів та контурів.

3. Розробити програмне забезпечення для розрахунку критичного шляху, визначення ранніх і пізніх термінів настання подій, ранніх і пізніх термінів початку і закінчення робіт, повних і вільних резервів часу виконання робіт.

4. Результати розрахунків представити у виді таблиці.

5. Розробити програмне забезпечення для графічного представлення СГ у вигляді діаграми Ганта.

II. Розробка алгоритмічного та програмного забезпечення для статистичного моделювання сітьового графіка методом статистичних випробувань за отриманими початковими даними. Друга підзадача поділяється на два кроки:

1. Описати теоретичну суть та послідовність розрахунків імовірнісних характеристик параметрів проекту.

2. Навести алгоритми основної програми, структуру вхідних і вихідних даних.

III. Основні висновки по роботі та аналіз досягнутих результатів.

2 РОЗРОБКА ДЕТЕРМІНОВАНОЇ МОДЕЛІ СІТЬОВОГО ГРАФІКА І ПРОВЕДЕННЯ МОДЕЛЮВАННЯ

 

2.1 Розробка програмного забезпечення для моделювання детермінованої моделі

Розробка програмних структур для СГ

Маємо орієнтований граф G =(V, E), кожній дузі vàw цього графа відповідає невід’ємна ціна С [v, w]. Загальна задача знаходження найдовших шляхів полягає в знаходженні для кожної вершини впорядкованої пари вершин (v, w) любого шляху від вершини v до вершини w, довжина якого максимальна серед усіх можливих шляхів від v до w.

Існує прямий спосіб розв’язання цієї задачі, використовуючий алгоритм Флойда (R. W. Floyd). Для визначеності установимо, що вершини графа послідовно пронумеровани від 1 до n. Алгоритм Флойда використовує матрицю А розміру nхn, в якій обчислюються довжини найдовших шляхів. На початку А[i, j]=C[i, j] для усіх i≠j. Якщо дуга ià j відсутня, то C[i, j]=-∞. Кожний діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується n ітерацій. Після k-тої ітерації A[i, j] містить значення шляхів найменшої довжини з вершини i в вершину j, які не проходять через вершини з номером, більшим за k. Іншими словами, між кінцевими вершинами шляху i и j можуть знаходитися вершини, номера яких менше чи рівні k.

На k-тій ітерації для обчислення матриці А застосовується наступна формула:

A_k[i, j] = min(A_k-1[i, j], A_k-1[i, k] + A_k-1[k, j]).

Нижній індекс k позначає значення матриці А після k-тої ітерації, однак це означає, що існує n різних матриць, цей індекс використовується для скорочення запису.

Для обчислення A_k[i, j] проводиться порівняння вершини A_k-1[i, j] (тобто ціна от шляху від вершини i до вершини j без участі вершини k чи іншої вершини з більш високим номером) з величиною A_k-1[i, k] + A_k-1[k, j] (ціна шляху від вершини i до вершини k плюс шляху від вершини k до вершини j). Якщо шлях через вершину k дорожче, ніж A_k-1[i, j], то величина A_k[i, j] змінюється.

Рівності A_k[i, k] = A_k-1[i, k] и A_k[k, j] = A_k-1[k, j] означають, що на k-тій ітерації елементи матриці А, що стоять в k-тій строці и в k-м стовпці, не змінюються. Усі обчислення можливо проводити лише з однією копією матриці А.

Щоб встановити при необхідності найдорожчі шляхи, можна в алгоритмі Флойда ввести ще одну матрицю P, в якій елемент P[i, j] містить вершину k, отриману при знаходженні найбільшого значення A[i, j]. Якщо P[i, j] = 0, то найдовший шлях з вершини i в вершину j складається з однієї дуги ià j.

Модифікована версія алгоритму Флойда, що дозволяє відновити найдовші шляхи:

private void AlgorithmFloyda(double [,]C, int [,]P)

{

int i,j,k;

int nn = (int)Math.Sqrt(C.Length)-1;

double [,]A = new double[nn+1,nn+1];

for(i=1; i<=nn; i++)

for(j=1; j<=nn; j++)

{

A[i,j] = C[i,j];

P[i,j] = 0;

}

for(i=1; i<=nn; i++)

A[i,i] = 0;

for(k=1; k<=nn; k++)

for(i=1; i<=nn; i++)

for(j=1; j<=nn; j++)

if(A[i,k] + A[k,j] >A[i,j])

{

A[i,j]=A[i,k]+A[k,j];

P[i,j]=k;

}

}

 

Програма повинна виконувати топологічний аналіз СГ на існування обривів та контурів. Якщо у СГ існує i-та вершина, з якої не виходить жодна дуга-робота (тобто i-й рядок матриці містить лише від’ємні числа), то знайден обрив. Тоді вершина, що висить, видаляється з графа шляхом заміни i-го стовпця матриці числами, що символізують -¥. Повідомлення про відповідні дії будуть записуватися у вихідний файл. Аналіз на існування контурів буде проводиться під час знаходження максимального шляху між вершинами: СГ є топологічно відсортованим, тому виявлення зворотної дуги vàw (v>w) свідчить про наявність контуру. У цьому разі для попередження зациклювання виконання програми буде припинятися.

Розрахунок часових параметрів проекту буде виконуватися на основі наведеного алгоритму Флойда, що знаходить найдовші шляхи між парами вершин.

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

Розрахунок критичного шляху, визначення ранніх і пізніх термінів настання подій, ранніх і пізніх термінів початку і завершення робіт, повних и вільних резервів часу виконання робіт буде виконуватися на базі інформації, отриманої алгоритмом Флойда, за формулами, що наведенні в I розділі.

Результати розрахунків будуть записуватися до файлу у вигляді таблиць, що містять часові параметри СГ.

Також програма буде формувати графічне представлення СГ - діаграму Ганта. На діаграмі кожній роботі буде відповідати два часових параметра: безпосередньо тривалість роботи та її повний резерв.

Структура файлу вхідних даних: кожній роботі графа буде відповідати рядок, що складається з двох цілих та одного/двох дійсних чисел, вигляду

i j Назва роботи C_min C_max.

3 МОДЕЛЮВАННЯ СІТЬОВОГО ГРАФІКА МЕТОДОМ СТАТИСТИЧНИХ ВИПРОБУВАНЬ

3.1 Описання теоретичної суті методу

Системи сітьового планування і керування в загальному випадку застосовуються для комплексів робіт, тривалість більшості яких не має нормативів.

У суднобудівній промисловості до них відносяться різні роботи на передпроектній і проектній стадіях, науково-дослідницькі, дослідно-конструкторські й експериментальні роботи, а також роботи з виготовлення та іспиту нових експериментальних зразків.

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

1.             по однієї і тієї ж роботи оцінки даються декількома експертами;

2.             для робіт, що часто повторюються чи типових, установлюються найбільш імовірна t_н.і. чи нормативна тривалість t_норм, що у розрахунках сітьового графіка приймається за очікувану тривалість роботи t_оч;

3.             даються дві оцінки тривалості роботи:

·              мінімальна t_min, тобто при найбільш сприятливому збігу обставин;

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

4.             даються три оцінки тривалості:

·              мінімальна;

·              найбільш імовірна;

·              максимальна.

Машинна обробка інформації про ймовірносні параметри сітьові моделі зводиться до обчислення:

·              математичного сподівання і дисперсії тривалості всього комплексу операцій (L_кр), що описується даною сітьовою моделлю;

·              довірчих інтервалів, що утримують значення тривалості комплексу операцій при заданих значеннях надійності;

·              довірчої імовірності закінчення комплексу робіт зі створення об'єкта в директивний термін при заданих значеннях довжини довірчих інтервалів;

·              математичних сподівань і дисперсій ранніх і пізніх термінів здійснення подій сітьової моделі;

·              довірчих інтервалів, що утримують значення ранніх і пізніх термінів здійснення подій сітьової моделі при заданих значеннях надійності;

·              довірчих імовірностей здійснення подій сітьової моделі в запланований термін при заданих значеннях довжини довірчих інтервалів;

У наш час розв’язання перелічених задач здійснюється такими способами:

I.          зведенням імовірнісної моделі до детермінованого СГ, у якому математичні сподівання тривалості робіт приймаються за їхні детерміновані тривалості;

II.         дослідженням імовірнісної моделі методом статистичних іспитів (метод Монте-Карло).

У випадку зведення імовірнісної моделі до детермінованого СГ приймаються наступні допущення:

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

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

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

Внаслідок цього перше допущення не має теоретико-ймовірносного обґрунтування. При моделюванні за методом Монте-Карло створюється послідовність реалізацій СГ з випадковими тривалостями робіт. При цьому змінюється довжина критичного шляху та іноді список вершин, через які він проходить.

При моделюванні сітьового графіка методом статистичних випробувань (м. Монте-Карло) тривалості робіт реалізації СГ дорівнюють фіксованим значенням, отриманим з використанням статистичного моделювання по початковим даним.

Статистичне моделювання систем на ЕОМ є фактично сукупністю формальних процедур, засобами яких відтворюється на ЕОМ будь-які випадкові фактори (випадкові величини, випадкові події, випадкові функції з будь-яким розподілом). Вперше такі методи почали застосовувати для досліджень у галузі ядерної енергетики та військовій сфері наприкінці 40-х рр. XX ст.

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

1)             апаратний - найбільш складний, бо заснований на фізичному явищі;

2)             табличний - потребує додаткової пам`яті, бо заздалегідь будуються таблиці випадкових чисел;

3)             програмний - за допомогою спеціальних алгоритмів.

Останні два методи на відміну від першого генерують псевдовипадкові числа.

Існує програмний метод конгруентних генераторів, що дозволяє отримати числа з рівномірним законом розподілу. У ньому застосовується наступна формула:

де коефіцієнти a, b, c не можуть бути довільними. В цій роботі a=97, b=1113, c=131072.

Повний період циклу цього генератора буде отриманий в тому разі, якщо коефіцієнти будуть обиратися наступним чином:

C = 2^B , B- розрядність використовуємого комп’ютера. Повний період буде 2^B;

a - вибирається за формулою a = 1+4×k, де k - ціле число;

b - просте число відносно с (найбільший спільний дільник буде 1).

Рисунок 3 - Метод вилучення

Метод вилучення (рис. 3) дозволяє отримати випадкове число, якщо ми знаємо щільність розподілу f(x) випадкової величини Х. Його суть полягає в наступних діях:

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

·              потім ще одне - число Y, але на сегменті ;

·              ці два числа беруться як координати точки, якщо вона підпадає під криву f(x) (тобто в межах кривої щільності імовірності) , то перше число X і є випадковим числом з шуканим розподілом, якщо ні - знову генеруємо пари чисел.

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

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