Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем
Розглянуто задачі оптимізації розподілу робіт за етапами проекту створення ППС та вибору оптимального набору робіт для
 окремого етапу проекту. Запропоновано підхід до вирішення таких задач на основі методу „гілок та меж” та алгоритми вирішення.
 Дано обгрунтування оптимальності ріше...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1547 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем / І.А. Стрєлов, П.П. Ігнатенко // Проблеми програмування. — 2006. — N 2-3. — С. 263-268. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860219245709754368 |
|---|---|
| author | Стрєлов, І.А. Ігнатенко, П.П. |
| author_facet | Стрєлов, І.А. Ігнатенко, П.П. |
| citation_txt | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем / І.А. Стрєлов, П.П. Ігнатенко // Проблеми програмування. — 2006. — N 2-3. — С. 263-268. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| description | Розглянуто задачі оптимізації розподілу робіт за етапами проекту створення ППС та вибору оптимального набору робіт для
окремого етапу проекту. Запропоновано підхід до вирішення таких задач на основі методу „гілок та меж” та алгоритми вирішення.
Дано обгрунтування оптимальності рішень і скінченності алгоритмів.
Problems of distributing tasks among iterations of a software application development project and choosing optimal set of tasks for a single
iteration are examined. An approach and algorithms based on “branches and borders” method are proposed for these problems. Proofs of
solutions optimality and algorithms finiteness are given.
|
| first_indexed | 2025-12-07T18:17:50Z |
| format | Article |
| fulltext |
Методи та засоби програмної інженерії
УДК 681.3.06
МОДЕЛІ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ
ЩОДО СТРУКТУРИЗАЦІЇ РОБІТ ПРИ РОЗРОБЦІ
ПРИКЛАДНИХ ПРОГРАМНИХ СИСТЕМ
І.А. Стрєлов, П.П. Ігнатенко
Інститут програмних систем НАН України
03187, Київ, проспект Академіка Глушкова, 40,
тел.: +380 (44) 266 1540, факс: +380 (44) 266 6263
e-mail: ignat@isofts.kiev.ua
Розглянуто задачі оптимізації розподілу робіт за етапами проекту створення ППС та вибору оптимального набору робіт для
окремого етапу проекту. Запропоновано підхід до вирішення таких задач на основі методу „гілок та меж” та алгоритми вирішення.
Дано обгрунтування оптимальності рішень і скінченності алгоритмів.
Problems of distributing tasks among iterations of a software application development project and choosing optimal set of tasks for a single
iteration are examined. An approach and algorithms based on “branches and borders” method are proposed for these problems. Proofs of
solutions optimality and algorithms finiteness are given.
При застосуванні методики оцінювання економічних характеристик розробки або модифікації
прикладної програмної системи (ППС) [1], виникає необхідність у прийнятті керівництвом ряду рішень щодо
управління розробкою проекту [2].
У названій методиці авторами запропоновано комплексний підхід до оцінювання економічних
характеристик проектів розробки ППС, що поєднує методи FPA (Function Point Analysis, аналіз одиниць
функціональності) [3] та COCOMO (COnstructive COst MOdel, конструктивна модель вартості) [4].
Водночас прийняття організаційних рішень, тісно пов’язаних з одержанням необхідних економічних
характеристик у процесі проектування у методиці лишається без достатнього обгрунтування.
Важливими рішеннями, що суттєво впливають на тривалість та вартість розробки ППС є структуризація
робіт на етапи з урахуванням договірних вимог замовника проекту та обмежень щодо наявності в організації
необхідних ресурсів.
Для підтримки прийняття організаційних рішень у методиці запропоновано використовувати експертну
оцінку щодо розбиття проекту на підпроекти, що є підвищенням об’єктивності та зниження похибки оцінки за
рахунок того, що менші проекти, або легше піддаються оцінюванню, або вже мають добре відому та чітко
визначену оцінку.
У роботі пропонуються математичні моделі, що дозволяють обгрунтовано прийняти рішення щодо
структуризації робіт по створенню ППС, обгрунтовано розбивати великі складні задачі на підзадачі тощо.
1. Задача визначення складу робіт поточного етапу створення ППС
Нехай задані роботи }{ jR , nj ,1: , час виконання яких }{ jt , nj ,1: . T – загальний час U , який
призначений для виконання робіт щодо доопрацювання етапу проекту. При цьому Tt
i
i >>∑ . Задані також
}{ jC , nj ,1: , які визначають вартість (важливість) робіт }{ jR . Необхідно виконати на етапі U підмножину
робіт }{ jR з максимальною сумою }{ jC .
Формальна постановка задачі. Задані }{ jR , nj ,1: , }{ jt , nj ,1: , }{ jC , nj ,1: , T . При цьому
можна вважати 0>T , 0>jt , 0>jC . Введемо булеву змінну jx , що дорівнює 1, якщо робота jR
виконується на етапі U , та 0, в іншому випадку.
Серед усіх векторів jX , що задовольняють умовам
Txt
n
j
jj ≤∑
=1
, (1)
264
10 ∨=jx
(2)
необхідно знайти вектор jX , що доставляє функціоналу
∑
=
n
j
jj xC
1
(3)
максимальне значення. Це – задача про ранець [5].
Для її вирішення пропонується адаптивний алгоритм, що базується на ідеї методу „гілок та меж” в
модифікації А. Ленд і А. Дойг [6]. Його особливістю є використання ефективного прийому для вирішення
допоміжної задачі.
Опис алгоритму. Розглянемо модель
Знайти ∑
=
n
j
jj xC
1
max (4)
при обмеженнях Txt
n
j
jj ≤∑
=1
(5)
10 ≤≤ jx , (6)
де 0>T , 0>jt , 0>jC . Будемо називати цю задачу допоміжною, або r-задачею.
Її рішення може бути одержане таким чином. Якщо змінні jx записані в порядку співвідношення
j
j
T
C
:
n
n
T
C
T
C
T
C ≥≥≥ K
2
2
1
1 ,
то покладаємо:
=
1
1 ,1min
t
T
x ,
−=
2
11
2 ,1min
t
xtT
x ,
...
−
=
∑
−
=
j
j
k
kk
j t
xtT
x
1
1,1min .
Рішення цієї r-задачі вибираємо в якості оцінки („оцінки зверху”) функції-критерію вихідної задачі.
Позначимо i∆ – значення прогнозу функції-критерію задачі (1) – (3) на i -й ітерації алгоритму, { }i
jx –
краще зі знайдених рішень; )( 0
j
i xF – значення функціоналу, яке доставляє оптимальне рішення i -ї
допоміжної задачі (4)–(6).
На першій ітерації список задач, які підлягають рішенню містить одну допоміжну задачу (4)–(6). На
довільній ітерації i виконуються наступні кроки.
Крок 1. Перевірка: список допоміжних задач, які підлягають рішенню, пустий? Якщо так – крок 11,
ні – крок 2.
Крок 2. Вибрати i -ту допоміжну задачу і викреслити її із списку задач, що підлягають рішенню.
Методи та засоби програмної інженерії
265
Крок 3. Вирішити вибрану допоміжну задачу.
Крок 4. Перевірка: i
j
i xF ∆>)( 0 ? Якщо ні – крок 5, так – крок 6.
Крок 5. Прийняти ii ∆=∆ +1 , перехід на крок 1.
Крок 6. Перевірка: умови (2) виконуються? Так – крок 7, ні – крок 8.
Крок 7. Прийняти )( 01
j
ii xF=∆ + , { } { }0
jj xx = , nj ,1: , повернутися на крок 1.
Крок 8. Вибрати { } 100
0 ∨≠jx .
Крок 9. Добавити дві допоміжні задачі в список задач, які підлягають рішенню. Вони ідентичні i -й
допоміжній задачі, але в одній з них додано умову 10
0 =jx , а в іншій 00
0 =jx .
Крок 10. Прийняти ii ∆=∆ +1 , перехід на крок 1.
Крок 11. Кінець алгоритму.
Скінченність даного алгоритму є наслідком скінченності множини варіантів рішення задач (1)–(3).
Позначимо nn xxx ,,, 21 K=δ – довільне рішення розглядуваних задач, а ll xxx ,,, 21 K=δ –
фрагмент їх рішення ( nl < ). Для пропонованого алгоритму дійсні наступні твердження.
Твердження 1. Нехай )( 0
nδ∆ – значення функції-критерію оптимального рішення задачі (4)–(6), )( nF δ
– функція-критерій задачі (1)–(3). Тоді )()( 0
nnF δδ ∆≤ .
Для доказу цього твердження покажемо спочатку, що для будь-якого рішення nδ і фрагменту рішення
lδ , задовольняючого умови (2) задачі (1)–(3) виконується нерівність
{ }
∑+≤
0~
0)()(
jx
jjln xCFF δδ ,
де { }0~
jx – оптимальний розв’язок наступної допоміжної задачі:
∑
∉ lj
jj xC
δ
max (7)
при умовах
)( l
j
jj Txt
l
δ
δ
≤∑
∉
, (8)
10 ≤≤ jx . (9)
Нехай умови (2) виконуються для nδ , тоді
∑+=
s
sln TFF )()( δδ ,
де { } { }ln jjjjs δδ ∈∈= :\: .
З іншого боку, якщо умови виконуються лише для фрагменту рішення lδ , маємо:
∑
+=
+=
n
lj
jjln xCFF
1
)()( δδ .
Оскільки { }0~
jx забезпечує максимум рішення задачі (7)–(9) і { } injx δδ \~0 ∈ , то
{ }
∑∑ ≤
0~
0
jx
jj
s
s xCC .
Отже, твердження леми вірне, так як
266
{ }
∑+=∆
0~
0)()(
jx
jjln xCF δδ .
Твердження 2. Якщо на довільній ітерації i розглядуваного алгоритму список r-задач { }nxxx ,,, 21 K ,
які підлягають вирішенню, пустий, то { }i
jx – оптимальне рішення задачі (1)–(3), а відповідне йому ∆ –
максимальне значення функціоналу.
Справедливість твердження 2 випливає із коректності побудови в алгоритмі оцінок варіантів рішень
(твердження 1) і того очевидного факту, що описаний алгоритм охоплює всю множину варіантів рішень задачі
(1)–(3).
2. Загальна задача визначення складу робіт етапів створення ППС
Нехай задана сукупність всіх робіт { }jr , nj ,1: за виконанням проекту ППС з оцінками часу виконання
{ }jt , nj ,1: . При цьому множину робіт проекту необхідно розбити на m підетапів { }iE , mi ,1: , час
виконання яких визначено { }iT , mi ,1: .
Задана матриця ijC з елементами, які характеризують вартість виконання роботи j на етапі i .
Задана також матриця ijk з елементами, які характеризують коефіцієнти щодо часу виконання роботи j
на етапі i .
Як відомо, серед робіт { }jr , nj ,1: можуть бути роботи незалежні та такі, що виконуються за умови
виконання всіх попередніх робіт, згідно графа, яким описано план-графік цих робіт. Тобто, якщо ми хочемо
почати виконання не з незалежної роботи, а з роботи, яка стоїть у даний момент останньою у ланцюжці
залежних робіт, ми повинні за допомогою коефіцієнтів ijk забезпечити відповідний час для виконання цих
робіт, а за допомогою ijC забезпечити значення її вартості.
Формальна постановка задачі. Задані вектори { }jr , nj ,1: ; { }jt , nj ,1: ; { }iE , mi ,1: ; { }iT , mi ,1: ;
а також матриці ijC , mi ,1: , nj ,1: ; ijk , mi ,1: , nj ,1: .
Введемо змінну ijx , що дорівнює jt , якщо робота jr виконується на етапі iE , та 0, в іншому випадку.
Необхідно серед матриць ijx , які задовольняють умовам
j
i
ij tx =∑ , nj ,1: , (10)
i
i
ijij Txk ≤∑ , mi ,1: , (11)
0∨= jij tx , (12)
знайти матрицю ijx , яка доставляє мінімальне значення функціоналу
∑∑
i j
ijij xc . (13)
Умова (12) означає, що розрив виконання однієї роботи на різні етапи забороняється.
Задачі, що вирішуються за допомогою цієї моделі розподілу, мають наступну особливість: кількість
етапів значно менше кількості робіт ( nm << ). Це суттєво для запропонованого далі алгоритму, основаного, як
і для попередньої моделі, на ідеї методу „гілок та меж” [6].
Опис алгоритму. В запропонованому алгоритмі допоміжною задачею є:
Знайти ∑∑
i j
ijij xcmin (14)
при обмеженнях
Методи та засоби програмної інженерії
267
j
i
ij tx =∑ , nj ,1: , (15)
i
i
ijij Txk ≤∑ , mi ,1: , (16)
0≥ijx . (17)
При цьому допускаємо, що 0>iT , 0>it , 0>ijk , 0>ijc .
Це відома розподільча задача лінійного програмування (R-задача). Ефективність алгоритмів, заснованих
на ідеї методу „гілок та меж” у розглядуваній модифікації сильно залежить від наявності ефективного
алгоритму вирішення цієї R-задачі. Такий машинно-орієнтований алгоритм запропоновано в [7].
Використовуючи значення функціоналу оптимального рішення цієї допоміжної задачі в якості „оцінки
знизу” значення функціїї-критерії задачі (10)–(13), алгоритм її вирішення може бути описано наступним чином.
На першій ітерації алгоритму список задач, що підлягають вирішенню, містить одну допоміжну задачу
(14)–(17).
Позначимо i∆ – значення прогнозу функції-критерію задачі (10)–(13) на i -й ітерації;
i
ijx – краще із
знайдених рішень; )( 0
ij
i xL – значення функціоналу, яке доставляє оптимальний розв’язок рішення i -ї R-задачі.
На довільній ( i -й) ітерації алгоритму виконуються такі кроки:
Крок 1. Перевірка: список R-задач, які підлягають вирішенню, пустий? Так – крок 12, ні – крок 2.
Крок 2. Вибрати i -ту R-задачу і викреслити її із списку задач, які підлягають вирішенню.
Крок 3. Перевірка: вибрана R-задача має допустиме рішення? Так – крок 4, ні – крок 1.
Крок 4. Вирішити вибрану R-задачу, 0
ijx – її розв’язок.
Крок 5. Перевірка: )( 01
ij
ii xL>∆ + ? Так – крок 7, ні – крок 6.
Крок 6. Прийняти ii ∆=∆ +1 і перейти на крок 1.
Крок 7. Перевірка: умови (12) виконуються? Так – крок 8, ні – крок 9.
Крок 8. Прийняти )( 01
ij
ii xL=∆ + , зафіксувати 0
ijx , перейти на крок 1.
Крок 9. Вибрати 0
00
∨≠ jji dx .
Крок 10. Додати дві задачі до списку R-задач, які підлягають вирішенню. Вони ідентичні i -ій задачі, але
в одній з них додано умову jji dx =
00
, а в іншій – 0
00
=jix .
Крок 11. Прийняти ii ∆=∆ +1 і перейти на крок 1.
Крок 12. Кінець алгоритму.
Скінченність даного алгоритму витікає із скінченності множини варіантів рішень задачі (10)–(13).
Для нього дійсні наступні твердження.
Твердження 3. Нехай )( 0
ijx∆ – значення функції-критерію для оптимального рішення допоміжної задачі
(14)–(17). )( ijxL – функція-критерій задачі (10)–(13).
Тоді )()( 0
ijij xxL ∆≥ .
Справедливість того, що функція-критерій оптимального рішення запропонованої R-задачі є „оцінкою
знизу” для функції-критерію основної задачі може бути, так же як і в попередньому випадку строго доведена.
Не приводячи в цій роботі строгого доведення ми лише зауважимо, що справедливість твердження 3 зумовлена
рішенням з вибору допоміжної задачі (R-задачі).
Твердження 4. Якщо рішення основної задачі існує і список R-задач, які підлягають вирішенню, на i -му
кроці алгоритму пустий, то зафіксоване алгоритмом рішення 0x оптимальне, а відповідне йому ∆ –
мінімальне значення функціоналу )(xL .
Дійсно, за допомогою вибраної оцінки ∆ в алгоритмі відкидаються всі ті варіанти рішення, для яких
)( 0
ij
i xL більше чи дорівнює зафіксованому i∆ (кроки 5 - 6).
Обгрунтованість такого відсіву варіантів рішень дає твердження 3, з якого витікає також, що коли на i -й
ітерації алгоритму вирішені всі допоміжні задачі із списку задач та їх рішення задовольняють умові (12), то
розглядати варіанти, що лишилися, нема сенсу, оскільки всі вони будуть відкинуті на кроках 5-6.
Оптимум не буде досягнуто за допомогою описаного алгоритму лише в тому випадку, коли не існує
жодного допустимого рішення основної задачі (10)–(13).
268
Висновки
Оптимізація структуризації робіт щодо виконання проектів по створенню ППС з урахуванням
кваліфікації кадрового потенціалу організації є важливою складовою процесу керування розробкою.
Впровадження пропонованих методів підтримки прийняття рішень дозволяє більш точно прогнозувати
потребу в людських та часових ресурсів організації, що у галузі розробки ППС має велике значення. Внаслідок
цього можна точніше як планувати процеси виконання окремого проекту, так і узгоджувати між собою
розробку декількох проектів, які виконуються паралельно. Це дає змогу скорочувати цикли розробки ППС, що
є суттєвим для конкурентоспроможності підприємств у сучасних умовах.
1. Стрєлов І.А., Ігнатенко П.П. Підхід до оцінювання економічних характеристик проектних рішень при розробці, модифікації та
реінжинірингу програмних систем // Пробл. програм. – 2004. – № 1. – С. 38–51.
2. Исследование операций в 2-х т. Т.2 Модели и применения / Под ред. Дж. Моудера, С. Єлмаграби. – Пер. с англ. – М.: Мир, 1981. 677 с.
3. KPMG, 2001 – KPMG Consulting, Inc., Mark II Function Point Analysis Guide // www.kpmg.co.uk/kpmg/uk
4. CSE, 1999 – Center for Software Engineering, "COCOMO II Model Definition Manual", Computer Science Department, USC Center for
Software Engineering, 1999.
5. Вагнер Г. Основы исследования операций / Пер. с англ. – М.: Мир, 1972. – 2. – 488 с.
6. Land A.H., Doig A.G. An Automatic Metod of Solving Discrete Programming Problems. – Econometrica, 1960. – 28. - Р. 496 – 520.
7. Игнатенко П.П., Опанович М.И., Шкурба В.В. Использование списковых структур в распределительной задаче. В сб. Системотехника.
– Киев: ИК АН УССР, 1970. - № 2. - С. 15–36.
|
| id | nasplib_isofts_kiev_ua-123456789-1547 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:17:50Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Стрєлов, І.А. Ігнатенко, П.П. 2008-08-22T11:48:17Z 2008-08-22T11:48:17Z 2006 Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем / І.А. Стрєлов, П.П. Ігнатенко // Проблеми програмування. — 2006. — N 2-3. — С. 263-268. — Бібліогр.: 7 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1547 681.3.06 Розглянуто задачі оптимізації розподілу робіт за етапами проекту створення ППС та вибору оптимального набору робіт для
 окремого етапу проекту. Запропоновано підхід до вирішення таких задач на основі методу „гілок та меж” та алгоритми вирішення.
 Дано обгрунтування оптимальності рішень і скінченності алгоритмів. Problems of distributing tasks among iterations of a software application development project and choosing optimal set of tasks for a single
 iteration are examined. An approach and algorithms based on “branches and borders” method are proposed for these problems. Proofs of
 solutions optimality and algorithms finiteness are given. uk Інститут програмних систем НАН України Методи та засоби програмної інженерії Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем Decision support models for task structurization in application software development projects Article published earlier |
| spellingShingle | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем Стрєлов, І.А. Ігнатенко, П.П. Методи та засоби програмної інженерії |
| title | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| title_alt | Decision support models for task structurization in application software development projects |
| title_full | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| title_fullStr | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| title_full_unstemmed | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| title_short | Моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| title_sort | моделі підтримки прийняття рішень щодо структуризації робіт при розробці прикладних програмних систем |
| topic | Методи та засоби програмної інженерії |
| topic_facet | Методи та засоби програмної інженерії |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1547 |
| work_keys_str_mv | AT strêlovía modelípídtrimkipriinâttâríšenʹŝodostrukturizacíírobítprirozrobcíprikladnihprogramnihsistem AT ígnatenkopp modelípídtrimkipriinâttâríšenʹŝodostrukturizacíírobítprirozrobcíprikladnihprogramnihsistem AT strêlovía decisionsupportmodelsfortaskstructurizationinapplicationsoftwaredevelopmentprojects AT ígnatenkopp decisionsupportmodelsfortaskstructurizationinapplicationsoftwaredevelopmentprojects |